（系统分析与集成专业论文）两类加工时间可变的排序问题.pdf

! ! ! ! 堡土塑盔堂亟堂焦鲨塞 ! 摘要 排序问题是一类重要的组合最优化问题在经典排序问题中，通常假设工件 的加工时间是固定的常数，然而在许多实际问题中，工件的加工时间可能与工件分 配到的资源、开工时间或所排的位置有着某种联系，由此产生了一些新的排序这 些新的排序问题比经典排序排序问题更为复杂，绝大多数问题是n p 一困难问题 对这些n p 一困难问题，讨论它的近似算法，并进行最坏情况分析很有必要；由于 实际生活的需要，讨论这些排序问题存在多项式可解的情况也很有必要这些多 项式算法，一方面可以为某些问题给出求解方法；另一方面还可以为解决其它问 题提供近似算法在本文中，我们研究了两类工件加工时间可变的排序问题，主要 做了以下两个方面的工作： 第一部分，加工时间与资源分配有关的单机排序，这是一个与资源约束有关 的准时排序问题工件分配到的资源越多，其加工时间就会越少所有的工件具有 共同的交货期，是个需要决策的变量目标函数是极小化包含提前惩罚、延误惩罚 和工期惩罚的总惩罚函数求解这类问题实际上就是找出最优的排列、每个工件 的最优资源分配量以及最优交货期，使得目标函数最小我们主要考虑了两种情 况第一种情况是工件的加工时间是它所得到的资源量的非线性递减函数；第二 种情况是工件的加工时间是它所得到的资源量的线性递减函数我们分析了最优 性条件，尽管这个问题的一般情况的算法复杂性未知，我们探讨了多项式时间可 解的情况，并给了有效算法 第二部分，加工时间是开工时间的简单线性关系的平行机排序，目标函数是 极小化最大完工时间这个问题是n p 一困难的，我们利用了划分的思想，对两台 机器的排序问题，我们提供了一个有效的近似算法一全多项式逼近算法，并把这 个结果推广到机器数目固定的多台机器的平行机问题上， 关键词： 排序；可控加工时问；准时排序；共同交货期；资源约束；恶化工件 ! ! ! ! 至上连盘堂亟堂焦迨塞 ! ! a b s t r a c t s c h e d u f i n gi sa ni m p o r t a n t , c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m i nt h ec l a s s i e ms c h e d u l i n gs t u d i e s ，j o bp r o c e s s i n gt i n m sa r et r e a t e da sc o n s t a n tp a r a m e t e r s h o w e v e r ，i nm a n yp r a c t i c a ls i t u a t i o n s ，t h ep r o c e s s i n gt i m eo faj o bc a nb ec o n t r o l l e db yt h ea m o u n to fr e s o u r c ea l l o c a t e d 、i t ss t a r t i n gt i m eo ri t sp o s i t i o ni nt h e s e q u e n c e f r o mt h i s ，t h en e ws c h e d u l i n gp r o b l e m se m e r g e d t h en e ws c h e d u l i n g p r o b l e m sa r em o r ec o m p l e xt h a nt h ec l a s s i c a ls c h e d u l i n gp r o b l e m s ，a n dm o s to f t h es c h e d u l i n gp r o b l e m sa r en p h a r d f o rt h e s en p h a r dp r o b l e m s ，i ti sn e c e s s a r y t h a ta p p r o x i m a t i o na l g o r i t h m sa r eg i v e n ，a n dt h ew o r s t c a s eb o u n d sa r ea n a l y z e d f o rt h er e q u i r e n m n to fp r a c t i c a ls i t u a t i o n s ，i ti sa l s on e c e s s a r yt oc o n s i d e rt h ec a s e s o fp r o b l e m sw h i c ha r ep o l y n o m i a lt i m ea l g o r i t h m s o nt h eo n es i d et h ep o l y n o - m i a lt i m ea l g o r i t h m sc a nb eu s e dt os o l v es o m ep r o b l e m s ，o nt h eo t h e rs i d et h e a l g o r i t h m sc a nb ec o n s i d e r e da sa p p r o x i m a t i o na l g o r i t h m so fo t h e rp r o b l e m s i n t h i sp a p e r ，w ec o n s i d e rt w os c h e d u h n gp r o b l e m sw i t hv a r y i n gp r o c e s s i n gt i m e s ：t h e m a i nc o n t r i b u t i o n sc a nb es u m m a r i z e da sf o i l o w s ： i nt h ef i r s tp a r t ( c h a p t e r2 ) ，s i n g l em a c h i n es c h e d u l i n gp r o b l e m sw i t hc o n t i n u o u sr e s o u r c e sf l a ed i s c u s s e di nt h ec o n t e x to ft h ec o m m o nd u e d a t ep r o b l e m i naj u s t i n - t i m ep r o d u c t i o ne n v i r o n m e n ti nt h es c h e d u l i n g ，t h ej o b p r o c e s s i n g t i m e sc a nb ec o n t r o l l e db yac o m m o nl i m i t e dc o n t i n u o u sa n dn o n r e n e w a b l er e s o u r c e i ns u c hc a s e s ，e a c hj o bh a sap r o c e s s i n gt i m et h a ti sad e c r e a s i n gf u n c t i o n o ft h ea m o u n to fr e s o u r c ea l l o c a t e dt ot h ec o r r e s p o n d i n gj o b t h ep r o c e s s i n gt i m e d e c r e a s e sa st h er e s o u r c ec o n s u m p t i o ni n c r e a s e s a l lj o b sh a v eac o m m o nd u e d a t e ，a n dt h ed u ed a t ei sad e c i s i o nv a r i a b l e t h ep r o b l e m sa r et of i n da no p t i m a l c o m b i n a t i o no fd u e - d a t e s c h e d u l ea n dr e s o u r c ea l l o c a t i o nt om i n i m i z et h es u mo f d u e d a t e ，e a r l i n e s sa n dt a r d i n e s sp e n a l t i e st w ov e r s i o n so ft h ep r o b l e m sa r ea d - d r e s s e d i nt h ef i r s to n et h ep r o c e s s i n gt i m ei sac o n v e xn o n l i n e a rf u n c t i o no ft h e 一一一 ! ! ! ! 生土渔太堂亟堂焦迨塞! ! ! r e s o u r c ea l l o c a t e dt ot h ej o b ：w h e r e a si nt h es e c o n do n ei ti sal i n e a rf u n c t i o n t h e c o m p u t a t i o n a lc o m p l e x i t yo ft h eg e n e r a lp r o b l e m sr e m a i no p e nq u e n s t i o n s ，b u tw e p r e s e n ta n da m a l y z es o m es p e c i a lc a s e st h a ta r es o l v a b l eb yu s i n gp o l y n o m i a lt i m e a l g o r i t h m s i nt h es e c o n dp a r t ( c h a p t e r3 ) ：w ec o n s i d e rap a r a l l e lm a c h i n es c h e d u l i n gp r o b - l e mi nw h i c ht h ep r o c e s s i n gt i m eo faj o bi sas i m p l el i n e a rf u n c t i o no fi t ss t a r t i n t i m e t h eo b j e c t i v ei st om i n i m i z em a k e s p a n t h ep r o b l e mi sn p h a r de v e nf o rt w o m a c h i n e sb yp r o c e d u r ep a r t i t i o n ，ah i l l yp o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e f o rt h ep r o b l e mo fs c h e d u l i n g 礼d e t e r i o r a t i n gj o b so nt w oi d e n t i c a lm a c h i n e si s p r e s e n t e d f u r t h e r m o r e ，w eg e n e r a l i z et h er e s u l tt ot h ec s , s eo faf i x e dn u m b e ro f r o a c h i n e s k e yw o r d s ：s c h e d u l i n g ；c o n t r o l l a b l ep r o c e s s i n gt i m e ；j u s t i n t i m es c h e d u l _ i n g ；c o m m o nd u ed a t e ；r e s o u r c ec o n s t r a i n t ；d e t e r i o r a t i n gj o b 原创性声明 本人声明：所呈交的论文是本人在导师的指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果， 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意 签名：例乏不 日期：加刃年月莎日 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论 文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容 保密的论文在解密后应遵守此规定 签名玩引墨荦导师籍名 日觏t “年石其f b 拣印蔟 2 0 0 6 年上海大学硕士学位论文 第一章绪论 排序问题( s c h e d u l i n gp r o b l e m s ) 是一类重要的组合最优化问题，也是运筹学 研究的一个非常活跃的分支排序问题最早起源于机器制造业，后来被广泛地应 用于计算机系统、运输调度、生产管理等领域从普通的生产部门的计划安排、人 员调度，学校课程表的制定，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的 理论和算法 1 1 排序问题 排序问题是一类利用一些处理机、机器( m a c h i n e s ) 或资源( r e s o u r c e s ) 最优地 完成一批给定的任务或作业的组合最优化问题在执行这些任务或作业时要满足 某些限制条件，如任务或作业的到达时间、完工的限定时间、任务的加工顺序、 资源对加工时间的长短、处理机的影响等最优地完成指的是使目标函数达到最 小，而目标函数通常是对加工时间的长短、处理器的利用率的描述对于排序问 题，我们一般采用下面的方式来描述： 给定含有n 个任务的任务集j = 以如，厶 m 台处理机的集合p = p 1 ，p 2 ，p m ) 和8 种资源的资源集r = r 1 ，r 2 ，r 。) 排序问题指的是在一定条件下，为了完成各项任务，把尸中的处理机和r ( 如 果有) 中的资源分配给t ，中的任务，使目标函数最优 排序问题基本上是由处理机的数量、种类与环境，以及任务或作业的性质和 目标函数所组成处理机的数量、种类和环境有近十种情况，任务或作业和资源的 约束条件更是错综复杂，再加上度量不同指标的目标函数，形成了种类繁多的排 序类型为了简化排序问题的表示，我们用g r a h a m1 1 3 1 等人首先使用的三参数记 号来描述排序问题的类型 三参数记号由三个域组成：l 卢l7 它们具有下边的含意： ! ! ! ! 生土星盔堂亟主堂鱼迨塞 ! o l 域表示处理机的数量、类型和环境，它可以为 i ：单处理机，通常称单机( s i n g l em a c h i n e ) 只有一个处理机的排序问题称 为单机排序问题 f m ：m 台同速机( i d e n t i c a lm a c h i n e s ) ，是指所有的处理机具有相同的功能， 且具有相同的速度 q 。：m 台恒速机( u n i f o r mm a c h i n e s ) ，是指m 台机器具有相同的功能，但 是机器的速度不同，每台机器的速度都是固定的常数，不依赖被加工的任务 。：m 台变速机( u n r e l a t e dm a c h i n e s ) ，m 台机器具有相同的功能，处理 机的加工速度依赖被加工的任务 在多处理机排序问题中，所有的处理机具有相同的功能，称为平行机( p a r a l l e l m a c h i n e s ) 以上的同速机、恒速机和变速机均是平行机 ：m 台机器，流水作业( f l o ws h o p ) 0 。：m 台机器，开放作业( o p e ns h o p ) l ，。：m 台机器，异顺序作业( j o bs h o p ) f f s ：m 台机器，柔性流水作业( f l e x i b l ef l o ws h o p ) 启域表示任务或作业的性质、加工要求和限制，资源的种类、数量和对加工的 影响等约束条件它可以包含多项，可能的项主要有： q ：任务有不同的准备时间( r e a d yt i m e ) 或称到达时间( a r r i v et i m e ) 如果卢 域不出现q ，说明r d = 0 ，j = 1 ，2 ：，n s j k ：表示任务易和任务 之间的安装时间( s e t u pt i m e ) 如果卢中不出现 s j k ，则所有的安装时间都是零 p r m p ；加工时可中断( p r e e m p t i v e ) 如果卢中不出现p r m p ，表示加工时间不 可中断( n o n p r e e m p t i v e ) 7 域表示要优化的目标函数，它可以是 c 。：时间表长( m a k e s p a n ) 或称为最大完工时间它等于最后一个工件的 完工时间用g 表示任务五的完工时间，则g 。= m a x g ) ! ! ! ! 生土塑丕堂亟主望焦堡塞i g ，g ：总完工时间( t o t a lc o m p l e t i o nt i m e ) ，加权总完工时间( t o t a l w e i g h t e dc o m p l e t i o nt i m e ) 屿b ：加权流时间( t o t a lw e i g h tf l o wt i m e ) ，弓= g o 是任务易的流 时间 l 。“最大延误( m a x i m u ml a t e n e s s ) l 。= m a x 岛) 其中岛= g 一呜 是任务 的延误时间 ，屿屿：误工任务数，加权误工任务数( w e g h t e dn u m b e ro f t a r d yt a s k s ) 当0 吗时，= 1 ；当c j 呜时，u j = 0 它是对任务易误工的单位 惩罚，其中d ，表示任务山的工期( d u ed a t e ) ，限定完工时间 例如lr j ，p r m pl q 表示一个单机、可中断的排序问题任务有不同 的准备时间，极小化的目标函数是加权总完工时间 焉| | c 。表示一个任务集无关、不可中断、极小化时间表长的同速机排序 问题 排序问题产生的背景是机器制造，早期的工作在描述排序问题时自然地会使 用制造业的术语现在的排序问题已被广泛地应用到更多的领域，制造业的术语 仍然在使用，如把任务称为工件( j o b s ) ，把资源称为机器( m a c h i n e s ) ，而现在的排 序问题中的工件和机器已不仅仅代表原来的具体意义，已从原来的具体事物中抽 象出来了比如在机场调度中，工件可以是飞机，而登机门当作机器，机场的规定 是约束条件，机场的调度人员需要制定一个可行的方案，把登机门分配给降落的 飞机，使飞机场的利用率最高或晚点起飞的飞机最少病人到医院诊断病情，病人 被当成工件，医生被看作机器等等因此在排序论中工件是被加工的对象，是要完 成的任务；机器是提供加工的对象，是完成任务所需要的资源安排时间表是在 一定的约束条件下对工件和机器按时间进行分配和安排次序，使某一目标达到最 优排序是安排时间表的简称 排序问题是一类组合最优化问题由于排序问题中的机器、工件都是有限的， 绝大部分排序问题是从有限个可行解中找出个最优解，使目标函数达到最优 在排序问题中，我们把可行解称为可行排序( f e a s i b l es c h e d u l e ) ，最优解称为最优排 ! ! ! ! 生土塑太堂亟堂焦堡塞! 序( o p t i m a s c h e d u l e ) 最优排序是使目标函数达到最优的可行排序在排序问题 中，由于绝大多数问题是n p 一困难问题，其最优解往往很难找到，而且在实际应 用中往往也没有必要去找最优解，只需找到满足一定要求的启发式解或近似解 因此排序问题的研究主要有两个方向一是对p 问题，即可解问题，寻找多项式 时间算法，也就是有效算法来得到问题的最优解，或者对n p 一困难问题在特殊情 况下寻找有效算法，也就是研究n p 一困难问题的可解情况二是设计性能优良的 启发式算法和近似算法当然，无论是启发式算法还是近似算法都应该是多项式 时间算法实际上，n p 一困难问题可解情况的多项式时间算法往往可以作为n p 一 困难问题本身的启发式算法和近似算法 1 2 现代排序问题 排序的理论部分可分为经典排序和现代排序现代排序是非经典的，是新型 的排序，其特征是突破经典排序的基本假设经典排序有四个基本假设： ( 1 ) 资源的类型机器是加工工件的所需要的一种资源一台机器在任何时刻 最多只能加工一个工件；而且一个工件在任何时刻至多在一台机器上加工突破 了这个假设，形成的的现代排序有成组分批排序、同时加工排序、不同时加工排 序、资源受限排序等 ( 2 ) 确定性排序问题的一个实例的所有参数都是事先知道的和完全确定的 作为这个假设的突破，有可控排序、在线排序、随机排序、模糊排序等现代排序 ( 3 ) 可运算性经典排序是在可以运算、可以计算的程度上研究排序问题而不 去顾及如如何确定工件的交货期、如何购置机器和配置设备等技术上可能发生的 问题，若考虑实际应用中有关的情况和因素，就是应用排序问题 ( 4 ) 单目标和正则性，经典排序假设排序的目标函数只有一个，而且这个目标 函数是工件完工时间的非降函数，这就是所谓正则目标作为这个假设的突破， 有多目标排序、准时排序和窗时排序等现代排序 现代排序是相对于经典排序而言的，其特征是突破了经典排序了某一基本的 假设随着实际情况的研究，现代排序问题也层出不穷，唐国春等最近出版的专著 ! ! ! ! 至土鳖盍堂亟堂焦迨塞1 3 4 系统地介绍了发展较为完备的近十种现代排序问题 1 3 排序问题的研究概况 排序问题的研究开始于二十世纪五十年代，普遍认为1 9 5 4 年j o h n s o n 的论文 1 7 1 是经典排序的第一篇，在此后的半个世纪中全世界已经发表文献2 千多篇， 其中包括排序专著和教材4 0 余种早期的工作主要围绕着整数规划、分枝定界法 和动态规划等其他组合最优化问题的方法来研究问题如果排序问题具有多项式 算法，从实际应用角度，问题已经解决然而很多重要的排序问题是n p 一困难问 题的随着复杂性理论的研究，由于实际问题的需要，人们开始对n p 一困难问题 建立了大量的有效的启发式算法近年来，随着计算机科学的发展，许多现代优化 设计方法如模拟退火算法、禁忌搜索算法、遗传算法和人工神经网络等被用来解 决排序问题 在排序问题的研究过程中，一方面是求解方法的多样性发展，另一方面是现 代问题模型的不断产生由于许多实际问题的出现，经典排序问题的基本假设不 断被突破，形成了大量的现代排序问题在2 0 世纪8 0 年代以前，对于排序问题 的研究主要集中一些经典模型上近十多年来，出现了许多新模型这两者的差异 主要表现在加工方式和目标函数上，从而也表现在解决问题的方法上 在实际生产管理中，工件的加工时间往往不是固定不变的，它可能与开工时 间有关，可能与分配到的附加资源有关，也可能与所排的位置有关工件加工时间 为变量的问题是一类重要的新型排序问题在经典排序中，工件延误是要受到惩 罚的，而提前是理所当然的而实际生活中提前也会带来损失，也会付出代价准 时( j u s t i n t i m e ) 排序是对交货期提前和延误都要受罚，都要付出代价的现代排序 问题，在准时排序中研究比较深入的是工件具有共同交货期的情况 1 4 本文的主要工作 本文所做的主要工作是研究了两类加工时间可变的排序问题第二章主要考 虑了工件的加工时间与资源分配有关的可控排序，给定一台机器和n 个需要加工 ! ! ! ! 生土竖盔堂亟堂焦堡塞 ! 的工件 以，以，厶) ，工件的加工时间a = ，( ) ，其中甄是分配到任务五的资 源量，i = 1 ，2 ，礼资源总量是给定的一数目b 我们在准时生产的环境里考 虑这个问题，所有工件具有共同的交货期d ，是个需要事先决策的变量，我们的目 标函数是( n e i ( o - ) + 卢正( 口) + 7 d ) 其中o 、卢分别是提前和延误的单位惩罚， 而，y 用来标度交货期d 越早越好的单位惩罚我们考虑了加工时间是资源分配数 量的非线性函数和线性函数两种情况，分析了最优性条件，并对多项式可解的情 况给出了有效算法第三章考虑了加工时间是开工时间的简单线性函数关系的平 行机排序问题，目标函数是极小化最大完工时间，我们给出了两台机器时n p 一困 难性的证明，提供了一个有效的近似算法一全多项式时间逼近算法，并把这个结 果，进一步推广到机器数目固定的平行机问题 2 0 0 6 年上海大学硕士学位论文 7 第二章加工时间与资源分配有关的可控排序 2 i 引言 在经典排序中，工件的参数，例如工件的加工时间、交货期和准备时间等是固 定的常数然而，在实际生产管理中，这些量的大小除了受机器这个因素的影响以 外，还与厂房、人力、设备、仓库等附加资源有关改变和控制机器以外的资源可 以改变和控制工件参数的大小，这时工件的参数就不是固定不变的了对改变和 控制工件的加工时间、交货期和准备时间等这一类排序问题称为可控排序本章 主要考虑两类加工时间可控的排序问题 这类加工时间可控问题最早是由v i c h s o n 础，洲】和v a nw a s s e n h o v e 等人【酣】 提出的 v i c h s o n l 3 z5 研究了目标函数是极小化加权完工时间与流的费用和的单 机排序，当加工费用是加工时间的线性函数时，提供了一个启发式算法d e n i e l s 和s a r i n 儿】研究了所有工件具有共同的资源分配量的单机模型，加工时间是资源 分配量的线性函数，并为延误工件数与消耗的总资源量的关系曲线提供了理论依 据 c h e n g b 等在这个模型的基础上，证明了当延误的工件个数满足一定的约束 时，极小化资源消耗总量的排序问题是n p 一困难的，并且给出一个拟多项式时间 的动态规划算法p a n w a l k a r 和p m j a g o p a l a n 弱1 研究了具有共同交货期的加工时 间可控的单机排序问题，把原问题转化为一指派问题，并给出了一0 ( n 3 ) 算法 j a n i a k i t ) 研究了加权总流时间费用的单机排序问题，在总资源数量的限制下，指 出这个问题的计算复杂性是公开问题。后来，h o o g e v e e n 和w o e g i n g e r 1 4 考虑了 目标函数是资源与加权流时间的花费总和时，证明这个问题是n p 一困难的l e e 和l e 铲圳考虑了连续不可恢复资源约束排序问题，对几种特殊情况给出了有效算 法s h a b t a y 和k a a p i ( 3 0 研究了加工时间是资源分配量非线性函数的单机排序 问题，目标函数是极小化加权流时间，虽然这个问题的计算复杂性还没有解决， 但是给出了一些多项式时间可解的情况 资源分配量的线性函数的资源约束问题 唐恒永、赵传立 3 5 考虑了加工时间是 目标函数是极小化最大完工时间时，给 出了一多项式时间算法；对目标函数是加权总完工时间的情况，指出复杂性没有 解决，后来赵传立等人 3 6 】给出了这个问题的最优解的两个性质，证明了该问题 ! ! 堕生土塑太堂亟堂焦迨塞! 是n p 一困难的 在经典排序中，把工件延误作为目标函数是因为工件的延误要带来损失，而 对工件提前视为理所当然，既不必付出代价，也不会带来收益然而，实际生活中 提前也会带来损失，也会付出代价比如，对装运上船的货物来说，在装运日之 后到达，推迟开船，要予以罚款，但在装运日之前到达码头，要支付仓库费和保险 费，也是要支付费用准时( j u s t i n - t i m e ) 排序是对交货期提前和延误都要付出代 价的排序问题在准时排序中研究得比较深入的是工件具有共同交货期( c o r l l l r l o r l d u e d a t e ) 的情况实际生活中，具有共同交货期的例子有很多，比如，在生产过程 的不同阶段，公司需要决定合适的集装时间，一个长的交货期会延误生产过程， 而不切实际的短的交货期会使部分产品不能完成，而对等待集装的产品又要交付 一定的储藏费用 3 一个鞋匠会对顾客交待某个合适的等待时间m 太长的交货 期不能成买卖交易，太短的交货期，做工不好又会使顾客不满所有的这些情况表 明如何确定一个合适的共同交货期非常重要 本章我们在准时生产环境中讨论工件加工时间依赖于分配给该工件的资源数 量的排序问题下面我们给出问题的一般描述： 设有一台机器，儿个需要被加工的工件 ，也，厶) 相互独立，所有的工 件0 时可达，并且每一个工件在加工过程中不允许中断机器在任何时刻最多只 能加工一个工件在这些工件加工之前，给定了一类连续可分的不可恢复资源， 它的总数目限制是常数b 工件五的加工时间的大小忱依赖于分配给该工件的 资源的数量x 。，工件 分配到的资源数量越多，那么它的加工时间就越小，它们 的函数关系为p 。= ，( 戤) ，是个递减函数这里要求所有的工件具有共同的交货 期d ，是个需要我们事先决策的变量我们的目标函数是( a 最( 一) + _ 臼正( 一) + 7 d ) ， 这里的o - = ( a ( 1 ) ：一( 2 ) ，a ( n ) ) 是一序列，一( j ) 表示序列o - 的第j 个位置 最( 一) = m a x o ，d g ( 一) ) 是工件。五的提前时间，露( a ) = m a x o a ( 一) 一毋是 工件以的延误时间n ，口和1 分别表示提前、延误和交货期的单位惩罚 我们 要做的工作就是为了使目标函数最小，来确定最优的序列o + 、最优的资源分配z + 和最优的交货期d + 对这个问题我们用三参数记号表示为1p i = ，( 甄) ，坠。x 。茎 b i ( 血最( 口) + _ 臼正( 口) + 7 d ) 垫! ! 生塑盘堂亟堂笪监塞! 2 2 最优性条件 定理2 2 1 ( 【5 ) 存在一个最优序列，这个最优序列在任何两个工件的加工之问， 机器不空转 定理2 2 2 对于任何一个给定的序列口和资源分配z ，必然存在一个最优的交货 期d 4 等于c k ( ) ，其中k 是大于等于( n p 一礼7 ) ( 血+ 卢) 的最小的整数，而且确 定前k 个工件不会延误 证明：我们首先来证明对于任何一个给定的序列a 和资源分配。，d + 等于某一工 件的完工时间 假设给定一序列o - 和d 满足g ( ，) d g ( 什1 ) ，设f 是相应的目标函数值 如果令。一d g o ) 和y = g ( j + 1 ) 一d 用f 7 和f ”分别来表示d = c o ( j ) 和 d = g ( j 十1 ) 的目标函数值，那么 和 ( 2 2 1 ) f ”= f v ( n j ) z + j 。+ n y y( 2 2 2 ) 因此，如果( n j ) z 墨j a + n 1 ，我们得到f 7 曼f 否则，就有f ” f 这就 暗含着任何一个给定的序列口，d + 等于某一个工件的完工时间设d + = c o ( k 1 ，把 2 = g 0 ( k ) 一g 一1 ) 和y = c a ( k + 1 ) 一c 0 ( ) 分别带入( 2 21 ) 式和( 2 2 2 ) 式，我 们可以得到 等k 等+ ， 所以d + = o ，那么对于前k 个工件不会延误 口 我们令总的惩罚函数为f ( a ，口，z ) = ( 蜀( 口) + 卢互( o ) + 7 d ) ，把d = g ( k ) p 。( 1 ) + m ( 2 ) + + p 。( ) 带入，我们可以得到 r ( d ，o - ，2 7 ) n 1 ) + n t ) p 。( 。) + e 卢( 咒一i + 1 ) p 。“ t = k + 1 k 日 ! ! ! ! 生土鲞太堂亟堂鱼迨塞! ! 令 u ，： o 一1 a + 他7 1 k o ( n j + 1 ) j 3 ，k + 1 j 茎n 这里“。表示一个工件被安排在一个序列的第j 位置时所产生的位置权( p o s i t i o n a l w e i g h t ) 那么 f ( d ，o - ，z ) = w i p 。( i ) + w i p ，( 。) = u 船( 。) ( 2 2 3 ) 我们称一个序列口= ( o - ( 1 ) ，口( 2 ) ，一( 礼) ) 是v 一型( v - s h a p e ) 的，如果不存在 i j 0 我们的问题用三参数表示就 是1p i = a i + b i x i ，圣1 x i bl ( e + 卢正+ 7 d ) 我们来确定最优的序列o - + 、最优的资源分配矿和最优的交货期d + ，使我们 的目标函数达到最小 定理2 3 1 对于任何一个最优的序列盯+ ，最优的资源分配z ；= ( x a 。( 。) ，z ；，z ；( 。) ) 必然满足：】z 施1 = b 证明：假如最优资源分配z ；不满足警。z = b 那么坠，z 茎b ，还剩 有一定数量的资源根据肌= o 。+ 魄轧的结构，我们知道对工件五分配的资源 数量越多，那么它的加工时间就会越小我们把剩有的资源分配给工件五，那么 它的工件的加工时间进一步减少，由( 2 23 ) 式可知目标函数值会更小，那么与z ： 是最优资源分配矛盾 口 那么我们的目标函数可以这样表示 m 。i n f ( d ，正z ) 2 唧州) = 耋小一罴) s t z 。( 。) ( 2 3 4 ) ( 2 3 5 ) 该问题的算法复杂性还是一个没有解决的问题，但对于任意的序列，我们有下面 的结论 垃 u 。日n 卜 。m目 j j = ! ! ! ! 生土塑太堂亟堂焦堡塞! ! 定理2 3 2 问题1 p i = a i + 玩z 。，鍪1 x isbl ( a 最+ 卢正+ 7 d ) ，对于任意一 个给定序列o - = ( 一( 1 ) ，一( 2 ) ，：盯( 竹) ) ，存在唯一的最优资源分配。+ 证明：这是一个非线性函数的最值问题，f ( d 口，z ) 是z 的凸函数，满足k o h n - t u c h e r 条件，最优解是唯一的即对于一个序列盯，存在一个相应的最优的资源 分配 我们利用非线性规划的拉格朗日( l a g r a n g e ) 乘子法来获得最优解 拉格朗日函数是 nn l ( x l ，。2 ，- 一、z 。，a ) = ( 咄n 。( i ) + w i b ，( i ) x 。( 。) ) + a ( z 。一b ) ( 2 36 ) t = 1i = 1 a 是拉格朗日乘子 o l ( x 1 ，x 2 ，一，z 。，a ) a a o l ( x l ，x 2 ：，z 。，a ) 如。 由( 2 3 7 ) 式和( 2 38 ) 式可知 x 。一b = 0( 2 3 7 ) w i b 。( 。) z + a = 0 ，v i = 1 ，2 ，n ( 2 3 8 ) ( 2 3 9 ) 那么我们可以得到最优解是 磕旷誊溉b ，江，n 皿。 而且把( 2 37 ) 和( 2 3 1 0 ) 带入( 2 3 4 ) 式 我们可得到目标函数的最优值 f = 屿n ，( ，) + ( b 。o ) ) 2 b ( 2 3 1 1 ) 对这个问题，我们探讨多项式可解的情况 挲 f a ! ! ! ! 生土星盔堂亟堂焦迨塞! ! 情况1 ，当b i = b 时，对每一个i = 1 ，2 ，有a = 吼+ b x 。，这样目标 函数简化成 ( p 1 ) 霉乎f ( d ，a ，z ) ：n 咄。州) + 妻詈妥 ( 2 - 3 4 n ) i = 1 i = 1 山口n i n s t x o ( i ) = b z 口( 。) 0 o = 1 对于这种情况，下面的算法可以得到最优序列、最优资源分配和最优交货期 算法1 ( 1 ) 计算k = 笔署 ，位置权，其中1 曼jsk 时，屿= 0 1 ) a + 礼7 k + 1 j 几时，“。= ( 他一j + 1 ) f l ( 2 ) 把a i 取值最大的那个工件放在屿最小的那个位置上，然后再从剩下的工 件中选出a 。取值最大的那个工件，放在剩下的位置中位置权u ，取值最小的那个 位置上，依此类推，这样排列下去，得到一个序列一( a ( 1 ) ，a ( 2 ) ，一( n ) ) ( 3 ) 计算。) = 赤b ，i = 1 ，2 ， ，n - 接着计算p 娟) = 昨) + b z 州) ，j = 1 ：2 ，：n 这样得到一个资源分配z = ( x a ( 1 ) ，。( 2 ) ，。( 。) ) ( 4 ) 计算d ：叁1 p o ( i ) 算法1 的第2 步需要o ( n l o g n ) 的时间去完成，那么算法1 的时间复杂性为 0 ml o g 礼) 定理2 3 3 算法1 得到的序列o - 、资源分配z 和交货期d 分别是问题俨) 的最 优序列、最优资源分配和最优交货期 证明：根据定理2 3 2 的证明过程，我们知道，算法1 产生的z = ( z 。( 1 ) ，z 。( 2 ) ，一，z 。( 。) ) 是对应于序列盯的最优资源分配类似于定理2 3 2 的证明过程，这时的目标函数 最小值为 f = w j a ，( ，) + ( 、屿6 ) 2 b( 2 3 1 2 ) j = lj = 1 通过这个式子的结构，我们知道等式的右端的第二项是一个常数，要使上式取值 最小，只要使得第一项的取值最小即可，算法1 的第二步可以获得最小值所以 序列口是最优序列由定理2 2 2 可知，算法1 得到的d 也是最优交货期口 一 ! ! ! ! 生土塑太堂亟堂垡迨塞卫 情况2 ， 函数简化成 当，：o 时，对每一个i = 1 ，2 ，n ，有a = n + b i x ，这样目标 ( p 2 ) m 。i n f ( d ，岬) = 妻i = 1 哪+ 。o i b ( 0 。 ( 23 4 6 ) z = l“、。j s t z ，( 。) = b z ，( i ) 0 江1 ，2 ， ( 2 3 5 ) 2 = 1 算法2 ( 1 ) 计算k = r ! 生a + 型f 1 ，位置权，其中1s j k 时，屿2u 一1 ) o + n 7 ， k + 1 j 礼时，u j ：( n j + 1 ) 卢 ( 2 ) 把b i 取值最大的那个工件放在屿最小的那个位置上，然后再从剩下的工 件中选出b i 取值最大的那个工件，放在剩下的位置中位置权屿取值最小的那个 位置上，依此类推，这样排列下去，得到一个序列口( 口( 1 ) ，a ( 2 ) ，o ( 礼) ) ( 3 ) 计算。一( 。) = e 三x 了。i b 雨o ( i ) 霖b ，i = 1 ，2 ，n 接着计算p