（运筹学与控制论专业论文）工件加工时间可变的现代排序问题.pdf

摘要 排序问题是一类重要的组合优化问题在经典排序问题中，通常假设工件的加工时 间为常数但在许多实际问题中，工件的加工时间可能与其开工时间、所用资源或所排 位置有着某种联系，由此产生一些现代排序问题这些现代排序问题比经典排序问题更 为复杂，绝大多数都是n p 一难问题对这些n p - 难问题，讨论它的近似算法，并给出算 法的最坏情况界很有必要；考虑实际应用的需要，研究现代排序问题存在多项式算法的 情况也很有必要，这些问题的多项式算法一方面可以对某些问题给出求解方法，另一方 面还可以为解决其它问题提供近似算法本文研究工件加工时间可变的现代排序问题， 主要在如下几个方面傲了一些工作： 1 工件加工时间是开工时间的增加函数的排序问题 ( a ) 最大完工时间单机排序问题对于一般模型中工件具有有跟森林约束和有串 并有向图约束的极小化最大完工时问单机问题分别给出了最优算法 ( b ) 加权完工时间和单机排序问题对增长率与基本加工时间相关且工件具有有 跟森林约束和有串并有向图约束的的单机问题进行研究，分别给出了最优算法 ( c ) 流水作业排序问题对机器问满足优势关系的不等待或无空闲问题进行研 究，目标函数分别为最大完工时间、加权完工时间和与最大延误，对它们分别给出了 最优算法 2 工件加工时间是开工时间的减少函数的排序问题 ( a ) 单机排序问题研究递减率与基本加工时间相关的单机问题，对最大完工时 间问题、加权完工时间和问题、工件具有平行链约束的加权完工时间和问题、最大费 用问题与最大延误问题分别给出了最优算法 ( b ) 流水作业排序问题对两台机器极小化最大完工时间问题，证明了利用j o h n s o n 规贝4 可以求得最优排序对工件各工序基本加工时间均相等的流水作业问题进行 了研究，并对某些情况给出了明确结论 8 加工时间可控的单机可控排序问题 首先，研究加工时间一般可控的排序问题，目标函数分别为极小化完工时间和、 完工时间偏差和与压缩费用的线性组合，等待时间和、等待时间偏差和与压缩费用的 线性组合，提前时间、延误时间、工期与压缩费用的线性组合。所有这些闯题都可转 化为指派问题，从而多项式时间可解其次，研究加工时间离散可控的排序问题，对 几类多目标问题进行了转化 4 具有学习效应的排序问题 对单机问题，研究了几类多目标问题，它们都可转化为指派问题，从而多项式时 间可解对流水作业问题，用反例说明在工件引入学习效应后经典的j o h n s o n 规则 对两台机器最大完工时间问题不是多项式最优算法，从而用j o h n s o n 规则作为它的 近似算法，分析了它的最坏情况界对m 台机器最大完工时间与完工时间和情况， 分别给出了近似算法并分析了它们的最坏情况界同时对某些特殊情况给出了多项 式算法 关键词：排序，单机，流水作业，线性加工时间，有跟森林，串并有向图，最坏情况界， 最优算法，恶化工件，可控加工时间，学习效应 l i a b s t r a c t s c h e d u l i n gi s a ni m p o r t a n tc o m b i u 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 c a l s c h e d u l i n gi t i sa s s u m e dt h a tt h ep r o c e s s i n gt i m e so fj o b sa r ec o n s t a n tv a l u e s h o w e v e r ， t h e r ea r em a n ys i t u a t i o n sw h e r et h ep r o c e s s i n gt i m eo ft h ej o bd e p e n d so ni t ss t a r t i n g t i m e ，i t sr e s o u r c e a l l o c a t i o no ri t s p o s i t i o ni n t h es e q u e n c e f r o mt h i s ，t h em o d e r n s c h e d u l i n gp r o b l e m se m e r g e d t h em o d e r ns c h e d u l i n gp r o b l e m sa r em o r ec o m p l e xt h a n c l a s s i c a ls c h e d u l i n gp r o b l e m s ，m o s to fw h i c ha r en p h a r dp r o b l e m s 。f o rt h e s en p h a r d p r o b l e m s ，i ti sn e c e s s a r yt 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 e b o u n d sa r ea n a l y z e d c o n s i d e r i n gt h er e q u i r e m e n to fp r a c t i c a la p p l i c a t i o n ，t h ec a s e so f m o d e r n s c h e d u l i n gp r o b l e m s w h i c ha r ep o l y n o m i a lt i m e a l g o r i t h m sa r ea l s on e c e s s a r y o n o 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 no t h e r s i d et h ea 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 t h i sp a p e rc o n s i d e r sm o d e r ns c h e d u l i n gj o b sw i t hv a r y i n g p r o c e s s i n gt i m e s ，t h em a i n c 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 l l o w s ： 1 c h a p t e r2 j o bp r o c e s s i n gt i m eb e i n gai n c r e a s i n gf u n c t i o no ft h e s t a r t i n gt i m e s c h e d u l i n gp r o b l e m s ( a ) m a x i m u mm a k e s p a ns 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 s f o rt h eg e n e r a l m o d e lw i t hr o o t e df o r e s tp r e c e d e n c ec o n s t r a i n t sj o b so rs e r i e s p a r a l l e ld i g r a p h s j o b s ， t h eo p t i m a la l g o r i t h m sa r ep r e s e n t e d ， ( b ) t h ew e i g h t e ds u mo fc o m p l e t i o nt i m e ss 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 s f o rt h es p e c i a lm o d e lo ft h eb a s i c p r o c e s s i n gi sr e l a t e dt oi n c r e a s i n gr a t ew i t hr o o t e d f o r e s tp r e c e d e n c ec o n s t r a i n t sj o b so rs e r i e s p a r a l l e l d i g r a p h sj o b s ，t h eo p t i m a la l g o - r i t h m sa r ep r e s e n t e d ( c ) f l o ws h o ps c h e d u l i n gp r o b l e m s t h ec a s e sw h e r et h em a c h i n e ss a t i s f y i n g s o m ed o m i n a n c er e l a t i o n sa n dn o - w a i to rn o - i d l ea r ed i s c u s s e d ，a n ds o m es o l u t i o n s a r eg i v e n 2 c h a p t e r3 j o bp r o c e s s i n gt i m eb e i n gad e c r e a s i n gf u n c t i o no ft h e s t a r t i n gt i m e 8 c h 8 d u l i n gp r o b l e m s f o rt h ec a s eo ft h eb a s i c p r o c e s s i n gi s r e l a t e dt o d e c r e a s i n g r a t e ： ( a ) 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 s o p t i m a la l g o r i t h m sa r ep r e s e n t e dr e 一 8 p e c t i v e l yf o rs i n g l em a c h i n e s c h e d u l i n go fm i n i m i z i n gt h em a k e s p a n w e i 9 1 1 t e ds l l r no f l u c o m p l e t i o nt i m e s ，w e i g h t e ds u m o fc o m p l e t i o nt i m e so fc h a i n sp r e c e d e n c ec o n s t r a i n t s ， m a x i m u mc o s ta n dm a x i m u ml a t e n e s s ( b ) f l o ws h o ps c h e d u l i n gp r o b l e m s f o r t w o - m a c h i n ef l o ws h o ps c h e d u l i n gp r o t ) _ l e n lt om i n i m i z et t i em a k e s p a n 。i ti sp r o v e dt h a tt h eo p t i m a ls c h e d u l ec a l lb eo b t a i n e d b yj o h n s o n sr u l e t h e c a s e sw h e r et h eb a s i cp r o c e s s i n gt i m e so fo p e r a t i o n sa r ee q u a l f o re a c hj o b ，a n ds o m es o l u t i o n sa r eg i v e n 3 c h a p t e r4 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 r o l l a b l ep r o c e s s i n gt i m e s f i r s t w ec o n s i d e rt h eg e n e r a lc o n t r o l l a b l ep r o c e s s i n gt i m e sp r o b l e m 妤jc o n c e i l t r a t eo nt h r e eg o a l ss e p a r a t e l y ，n a m e l y , m i n i m i z i n gac o s tf l m c t i o nc o n t a i n i n gt o t a l c o m p l e t i o nt i m e ，t o t a la b s o l u t ed i f f e r e n c e si nc o m p l e t i o nt i m e sa n dt o t a lc o n l p r e s s i o nc o s t ；m i n i m i z i n gac o s tf u n c t i o nc o n t a i n i n gt o t a l w a i t i n gt i m e ，t o t a la b s o l u t e d i f f e r e n c e si nw a i t i n gt i m e sa n dt o t a lc o m p r e s s i o nc o s t ；m i n i m i z i n gac o s tf u n c t i o n c o n t a i n i n ge a r l i n e s s ，t a r d i n e s s ，d u ed a t e sa n dc o m p r e s s i o n s t h ep r o b l e mi sm o d e l l e d a sa na s s i g n m e n tp r o b l e mr e s p e c t i v e l y , a n dt h u sc a r lb es o h e dw i t ht h ew e l l k n o w n a l g o r i t h m s s e c o n d ，w ec o n s i d e rt h ed i s c r e t e l yc o n t r o l l a b l ep r o c e s s i n gt i m e sp r o b 1 e m s w ec o n s i d e rs o m em u l t i c r i t e r i as c h e d u l i n g t h ep r o b l e m sa r em o d e l l e da 8a l l a s s i g n m e n tp r o b l e m 4 c h a p t e r5 s c h e d u l i n gp r o b l e m sw i t hal e a r n i n ge f f e c t f o rs i n g l em a c h i n es c h e d u l i n g w ec o n s i d e rs o m em u l t i c r i t e r i a s c h e d u l i n g ，t h e p r o b l e m sa r em o d e l l e da sa na s s i g n m e n tp r o b l e m f o rf l o ws h o ps c h e d u l i n g a n e x a m p l ei s c o n s t r u c t e dt os h o wt h a tt h ec l a s s i c a lj o h n s o n sr u l ei sn o tt h eo p t i m a l s o l u t i o nf o rt h et w o - m a c h i n ef l o w s h o ps c h e d u l i n gt om i n i m i z em a k e s p a nw i t hal e a r n i n ge f f e c t i no r d e rt os o l v et h em a k e s p a nm i n i m i z a t i o np r o b l e mi nt h et w o - m a c h i i l e f l o ws h o ps c h e d u l i n g ，w es u g g e s tj o h n s o n sr u l ea sah e u r i s t i ca l g o r i t h i n f o rw h i c i l t h ew o r s t c a s eb o u n di sc a l c u l a t e d ，f o rt h em m a c h i n e ah e u r i s t i c a l g o r i t h mw i t h w o r s t - c a s eb o u n dmf o rm a k e s p a no rt h es u mo f c o m p l e t i o nt i m e sc r i t e r i ai sg i v e n f u r t h e r m o r e ，ap o l y n o m i a la l g o r i t h mi sp r o p o s e df o rs o m es p e c i a lc a s e s k e yw o r d s ：s c h e d u l i n g ，s i n g l em a c h i n e ，f l o ws h o p ，l i n e a rp r o c e s s i n gt i m e s r o o t e d f o r e s t ，s e r i e s - p a r a l l e ld i g r a p h s ，w o r s t c a s eb o u n d o p t i m a la l g o r i t h m ，d e t e r i o r a t i l l g j o b c o n t r o l l a b l ep r o c e s s i n gt i m e ，l e a r n i n ge f f e c t 1 绪论 本章首先简要地介绍了排序问题的由来及现代排序问题的特征，然后介绍了 现代排序的概况，概述了本文研究的内容以及取得的主要结果 1 1 概述 排序问题( s c h e d u l i n gp r o b l e m s ) 也称调度问题，是组合优化中的一个重要分支其 所研究的问题是利用一些机器或资源，最优地完成一批给定的工件或任务在执行这些 工件或任务时需要满足某些限制条件，如工件的到达时间、工件完工的限定时间、工件 的加工顺序、资源对加工的影响等等，最优的完成是指使目标函数达到最小，而目标函 数通常是对加工时间长短，机器利用率高低的描述排序问题最早起源于机器制造业， 现在已逐渐发展成为运筹学、系统科学、控制科学、管理科学和计算机科学等多个学科 领域的交叉学科，广泛应用于工程技术和经济管理的各个领域作为一门应用科学，它 在作业安排、制造工厂的最优设计、交通枢纽的排序及工程进度的控制等方面有着深刻 的实际背景和广阔的应用前景 例1 1 机械加工 一个机械加工车间要加工一批机器零件，每一个零件都具有相同的工序，即按相同 的顺序在几个不同的机床上加工，但每个零件在每个机床上的加工时间可能不同如何 安排加工顺序才能以最短的时间加工完所有的零件? 这是一个流水作业排序问题 例l - 2 进程排序 在计算机多道程序操作系统中，并行执行多个进程；在宏观上同时执行多个进程， 在微观上在任何时刻c p u 只能执行一个进程进程的到达时间是不同的，怎样排序这些 进程才能使c p u 的利用率最高或进程的平均周转时间最短? 这也是一个排序问题 例1 3 机场排序 在一个飞机场。有几十个登机门，每天有几百架飞机降落和起飞登机门的种类和 大小是不同的，班机的机型和大小也是不同的一些登机门安放在能容纳大型飞机的地 方，小登机门只能容纳小型飞机飞机按时刻表降落和起飞，由于天气和机场的其它原 大连理工大学博士学位论文：工件加工时间可变的现代排序问题 因，时刻表也有很大的随机性当飞机占有登机门时，到达的旅客下飞机，出发的旅客 上飞机，飞机要接受诸如加油、维护和装卸行李等服务如果飞机在下一个机场不能按 时降落，此时为了节省燃料，飞机不能起飞，登机时间推迟，飞机需要占有一个登机门 而其它的飞机不能使用机场的排序人员需要制订一个可行的方案，把登机门分配给降 落的飞机，使机场的利用率最高或晚点起飞的飞机最少，这也是一排序问题，在这里飞 机被看成是被加工的工件，登机门当作机器，机场的规定是约束条件 由于排序领域内许多早期的工作是在制造业推动下发展起来的，所以在描述排序问 题时很自然地会使用制造业的术语尽管现在排序问题在许多非制造业已取得了许多相 当有意义的成果，但是制造业的术语仍然在使用因而往往把资源( r e s o u r c e s ) 称为机器 ( m a c h i n e s ) ，把任务( t a s k s ) 称为工件( j o b s ) ，有时工件可能是由几个先后次序约束相互联 系着的基本任务( e l e m e n t a r yt a s k s ) 所组成这种基本任务称为工序( o p e r a t i o n s ) 排序 中“机器”和“工件”已经不是机器制造业中的“机床”和“机床加工的零件”，已经从 “机床”和“零件”等具体事物中抽象出来，是抽象的概念排序中的机器可以是数控机 床、计算机c p u 、机场跑道等，工件可以是零件、计算机终端、降落的飞机等困此， 排序问题中，工件是被加工的对象，是要完成的任务机器是提供加工的对象，是完成 任务所需要的资源排序是指在一定的约束条件下对工件和机器按时间进行分配和安排 次序。使某一个或某一些目标达到最优排序是安排时间表的简称这里工件和机器可 以代表极其广泛的实际对象 1 2 经典排序问题与现代排序问题 在排序问题中，机器的数量和种类、工件的顺序、到达时间、完工限制、资源的种类和 性能是错综复杂的，很难用精确的数学描述给出般的排序问题的定义经典排序问题按 静态( s t a t i c ) 和动态( d y n a m i c ) 、确定性( d e t e r m i n i s t i c ) 和非确定性( n o n d e t e r m i n i s t i c ) 可分为四大类下面介绍静态确定性排序问题的有关知识，这是了解和研究现代排序问 题的基础 1 2 1 经典排序问题的定义 通常用下面的方式描述排序问题： 给定礼个工件的工件集，= 如，山： m 台机器的机器集m = 她，a 如， k ； s 种资源的资源集r = f r l ，月2 ，风) 排序问题指的是在一定条件下为了完成各个工件，把a ，中的机器和月中的资源分 配给j 中的工件，使目标函数达到最优， 2 第1 章绪论 排序问题基本上由机器的数量、种类和环境，以及工件的性质和目标函数所组成 机器 只有一台机器的排序问题称为单机( s i n g l em a c h i n e ) 排序问题，否则称为多机排序 问题 在多机排序问题中，如果所有的机器都具有相同的功能，则称它们为平行机( p a r a l l e l m a c h i n e s ) 平行机按加工速度叉分为三种类型如果所有的机器都具有相同的速度，称 之为同速机( i d e n t i c a lm a c h i n e s ) 如果机器的速度不同，但每台机器的速度都是常数， 不依赖被加工的工件，则称为恒速机( u n i f o r mm a c h i n e s ) ，如果机器的加工速度依赖于被 加工的工件，则称为变速机( u n r e l a t e dm a c h i n e s ) 多机问题的另一种情况是多类型机( d e d i c a t e dm a c h i n e s ) ( 也称串联机，车间作业) 多 类型机指的是机器具有不同的功能在多类型机环境中，被加工的工件需要在不同的机 器上加工通常情况下，每个工件有多道工序，每道工序需要在不同的机器上加工 如果每个工件需要在各个机器上加工，且各个工件在各机器上的加工顺序都相同， 则称为流水作业( 也称同顺序作业或f l o ws h o p ) 如果每个工件需要在各个机器上加工，但各个工件有自己的加工顺序，则称为异序 作业( 也称j o bs h o p ) 如果每个工件需要在各个机器上加工，但各个工件的加工顺序任意，则称为开放作 业( 也称自由顺序作业或o p e ns h o p ) 工件 排序问题中的约束条件，主要指的是工件的性质以及它们在加工过程中的要求和限 制下面的数据描述工件的一些性质 ( 1 ) 加工时间 加工时间( p r o c e s s i n gt i m e ) 、服务时间( s e r v i c et i m e ) 或执行时间( e x e c u t i o nt i m e ) 都是指工件以在机器m 上加工所需的时间，通常用p 巧来表示对同速机有p ”= p j ， ( = 1 ，2 ，m ) ，对恒速机有p o = 岛魄，( 1 = 1 ，2 ，m ) ，其中乃是标准的加工时间 ( 一般是速度最慢的机器的加工时间) ，吼是机器尬的速度因子 ( 2 ) 准备时间 准备时间( r e a d yt i m e ) 、释放时间( r e l e a s et i m e ) 或到达时间( a r r i v a lt i m e ) 都是指工 件西可以开始加工的时间，用q 表示如果所有工件的准备时间都相同，取o = 0 ，0 = 1 ，2 ，礼) ( 3 ) 等待时间 等待时间( w a i tt i m e ) 是指工件如的等待时间，用表示，其中= g n 3 大连理工大学搏士学位论文：工件如工时闯可变的现代排序问题 ( 4 ) 工期和截止工期 工期( d u ed a t e ) 南也称交货期，是对工件弓限定的完工时间如果不按时完工，应 受到一定惩罚如果所有工件的工期均相同，则称为公共工期( c o l _ i l i i l o nd u ed a t e ) 绝对 不允许延误的工期称为截止工期( d e a d l i n e ) ( 5 ) 权 权( w e i g h t ) 表示工件相对于其它工件的重要程度 加工工件时的一个重要限制是可中断( p r e e m p t i v e ) 和不可中断( n o n 。p r e e m p t i v e ) 一个工件在加工过程中，如果可以被别的工件抢先而中断加工，并稍后在原来机器或其 它机器上继续加工，这种性质称为可中断加工任何工件都不允许中断加工的问题称为 不可中断排序问题加工工件时的另一个重要限制是工件之间的优先约束( p r e c e d e n c e c o n s t r a i n t s ) 工件间的优先约束是工件集上的一个偏序关系一正一 意味着必须加工 完以才能加工以，如果工件集中至少有两个工件受到优先约束的限制，称工件是相关 的否则，称为无关的一般用一个称为优先约束图的有向图来表示工件间的优先约束 关系在有向图中，用节点对应工件，弧对应偏序关系，始点为正，终点为 的弧对应 五一易，称 为以的前驱，以为 的后继图1 2 1 是优先约束图的例子 图1 2 1 优先约束图 目标函数 对于给定的一个排序”，用0 ( ”) 表示工件占的完工时间极小化的目标函数是完 工时间q ( 霄) 的函数主要有下面几种 ( 1 ) 最大完工时间 最大完工时间( m a k e s p a n ) ( 也称时间表长) 定义为 e k “= m a x g 它等于最后一个被加工完工件的完工时间 4 第1 章绪论 ( 2 ) 加权完工时间和 加权完工时间和( w e i g h t e ds l mo fc o m p l e t i o nr i m e s ) 是 当权相同时，加权完工时间和化为完工时间和( s u mo fc o m p l e t i o nt i m e s ) q = e g ( 3 ) 最大延误 最大延误( m a x i m u ml a t e n e s s ) 定义为 l 。= m a x l j 其中l j = c j d j 是工件以的延误时间 ( 4 ) 最大延迟 最大延迟( m a x i m u mt a r d i n e s s ) 定义为 t m a x = m a x t j 其中乃= m a x l j ，0 是工件占的延迟时间 ( 5 ) 误工工件数 误工工件数( n u m b e ro ft a r d yj o b s ) 是 u j = ， j = l 其中 = h8 至乏 ( 6 ) 总等待时间 总等待时间( t h et o t a lw a i t i n gt i m e s ) 是 e = j = l ( 7 ) 完工时间的总绝对差 5 g u 。烈 | | c ， u 奎垄望三查堂簦主兰堡垒茎：三壁垫三堕里亘銮塑塞垡塑! 至旦! i 一 完工时间的总绝对差( t h et o t a la b s o l u t ed i f f e r e n c e si nc o m p l e t i o nt i m e s ) 是 nn t a d c = l g 钳 = 1j = i ( 8 ) 等待时间的总绝对差 等待时间的总绝对差( t h et o t a la b s o l u t ed i f f e r e n c e si nw a i t i n gt i m e s ) 是 nn t a d w = i 啊一 l = lj = i 其中w j = c ，一p ，是工件五的等待时间 对于排序w = 【j - ，也，厶】，工件易的完工时间记为0 ( ”) ，工件乃的延误记 为l ，( 7 r ) ，工件以的延迟记为正( 丌) ，j = 1 ，2 、扎排序”的最大完工时间记为 c m a , x ( t r ) 一r n a x g ，( 若第一个工件开始加工的时间为t o ，排序”的最大完工时间也记 为c m a x ( t o j l ，五，厶) ) 排序丌的加权完工时间和记为q g ( ”) ，排序”的最大延 误记为上一( 霄) ，排序7 r 的最大延迟记为b 。协) 在不引起混淆的情况下，上述记号分 别简记为g ，岛，巧，c m 。，屿g ，l 。和了二。 1 2 2 排序问题的分类 机器、工件和目标函数三要素组成了排序问题机器的数量、种类和环境有近十种 情况，工件和资源的约束条件更是错综复杂，再加上度量不同指标的目标函数，形成了 神类繁多的排序模型目前国际上通常使用三参数表示法 4 8 1 表示摊序问题 三参数表示法由三个域a ，y 组成 口域表示机器的数量、种类和环境 1 ：单机 p r o ：m 台同速平行机 q m ：m 台恒速平行机 r m ：m 台变速平行机 f m ：m 台机器，流水作业 j m ：m 台机器，异序作业 o r e ：m 台机器，自由作业 卢域表示工件的性质、加工要求和限制，资源的种类、数量和对加工的影响等约柬 条件它可以同时包含多项，可能的项主要有： 0 ：工件有不同的准备时间如果口域中不出现r ，说明r ，= 0 ( j = i 2 n ) 6 墨! 皇堡堡一 p r m p ：工件加工时允许中断如果j 域中不出现p r m p ，表示工件加工时不允许中 断， p r e c ，c h a i n s ，t r e e ：表示工件的相关性，分别表示一般优先约束，平行链优先约束和 树型优先约束如果口域中不出现这些项，表示工件是无关的 p r m u ：这个约束只可以出现在流水作业环境中，表示工件按通过第一台机器的顺序 始终不变地通过所有机器。 n o w a i t ：这个约束只可以出现在流水作业环境中，表示被加工的工件不允许在两 台相邻的机器间等待 n d i d l e ：这个约束只可以出现在流水作业环境中，表示加工工件的机器不允许在两 个相邻的工件间空闲 1 域表示要优化的目标函数 作为一个组合最优化问题，排序问题的优化目标是一个一维实数目标函数分为正 则函数与非正则函数 正则目标函数分为两类：使最大的费用最小( n l i n m a xc r i t e r i a ) 和使总的费用和最小 ( m i n s u mc r i t e r i a ) 主要有 c k a x ：最大完工时间 g ，奶g ：完工时间和，加权完工时间和 l 。a x ：最大延误 ! m 。：最大延迟 u j ：误工工件数 非正则的目标函数通常是 t a d c = ：1 ：ii c i g i ：完工时间的总绝对差 t a d w = 墨。= 一嵋：等待时间的总绝对差 1 2 3 排序问题的求解 由于机器、工件和目标函数都是有限的，绝大部分排序问题都是从有限个可行解中找 出一个最优解，使目标函数达到最小因此排序问题是一类组合最优化问题在排序问题 中，把可行解称为可行排序( f e a s i b l es c h e d u l e ) ，最优解称为最优排序f o p r i m a ls c h e d u l e l 一个可行排序是一个顺序( s e q u e n c e ) 或排列( p e r m u t a t i o n ) 按照这个顺序，在给定的机 器上加工所有的工件，满足问题所要求的各种条件和限制 最优排序是可行排序中使给定目标函数达到最小的排序 由于绝大多数排序问题是n p 一难问题，其最优解往往很“难”找到，而且在实际应用 中只需找到满足一定要求的启发式解和近似解因此排序问题的研究主要有两个方向 7 大连理工大学博士学位论文：工件加工时间可变的现代排序问题 一个是对可船的p 问题，寻求多项式时间最优算法( 又称为有效算法，简称多项式算法 或最优算法) 来得到问题的最优解，或者对n p 一难问题在特殊情况下寻求有效算法，也 就是研究n p 一难问题的可解情况二是设计性能优良的启发式算法和近似算法当然无 论是启发式算法还是近似算法都应该是多项式时间算法实际上n p 难问题的可解情况 的多项式时间最优算法往往可以作为n p 一难问题本身的启发式算法和近似算法衡量算 法的“优良”程度有三种方法：数值算例计算、最坏情况分析和概率分析这三种方法各 有优点，也各有不足之处在理论分析( 最坏情况分析和概率分析) 之前进行大量的算例 计算是非常有用的方法一则可以对理论分析给出估计和提供思路，再则可以与已有的 算法进行实际比较；最坏情况分析是分析算法在最坏情况下的性态；概率分析是分析算 法的“平均”性态居前理论上用的最多的是算法的最坏情况分析 对于目标函数，为最小的优化问题，记j 是这个优化问题的一个实例，p 是所有 实例的全体；并记，( ) 是实例，的最优目标函数值( 即最优值) ，知( ，) 是算法日的目标 函数值如果存在一个实数r ( r21 ) ，对于任何i p 有 乏塑 o ，j = l ，2 ，礼。尹，称为五的基本加工时间，为大于零的常 数，称为工件易的增长率( 递减率) ，( t ) 是单调增加函数，称为开工时间函数 若，( t ) = t ，称为线性加工时间排序问题若，( t ) 是非线性函数，称为非线性加工 时间排序问题若增长率( 递减率) q 与基本加工时间p j 成比例( q ，= k p ， ，称为增长率 ( 递减率) 与基本加工时间相关否则，称为增长率f 递减率) 与基本加工时间无关 线性加工时间单机排序问题l j p ，+ d ，t i c m a x 由g u p t a 和g u p t a 4 9 1 b r o w l l e 和 y e c h i a l i 1 9 分别独立提出 b r o w n e 和y e c h i a l i 考虑工件的基本加工时间是随机变量 的情况，目标函数为极小化最大完工时间的数学期望在这种情况下，工件，的基本加 1 0 一一 篁! 童堕堡一一 _-_，-v-、，-一 工时间记为随机变量x j 若工件的开工时间为t ，则其加工时间为局+ c b t b r o w n e 和1 r e c h i a l i 指出，对于问题1 f 玛+ 0 。f g ，若给定的排序为7 r = j i l l ，_ ，i 1 ，排 在第j 个位置的工件的完工时间为 jj c b = x 吲i - 1 ( 1 + 。) ( 1 1 3 1 ) = 1k = i + i 由式( 1 3 1 ) 进一步得出结论，把工件按e ( 玛) 不减顺序排列即得最优排序其中， e ( x ，) 是随机变量x ，的数学期望对于工件的基本加工时间是确定量的情况，g u p t a 和 g u p t a 4 9 】给出类似的结论，即把工件按胁o f 不减顺序排列即得最优排序g l a z e b r o o k 在文献【4 5 中研究了工件具有优先约束的问题1 i x ，+ a j t ，p r e c i c k a x ，给出了一个理论上 的结果 如果工件有准备时间，则问题变得复杂了c h e n g 和d i n g 在文献【3 0 中研究了问 题l | p j4 - ，q l c 鲁a x 和1 慨+ q t ，r j o ，r l c k 。证明了问题1 慨+ q ，r jc c k “是强 n p 一难的，而问题1 峙+ 哟，r 3 o ，r l c k 。至少是n p 一难的 对于工件有工期限制的情况，c h e n g 和d i n g 3 2 作了详细研究证明了问题1 扔+ o ，z ，由l c m a x 是强n p 一难的在此基础上进一步得出，问题1 慨+ t ，嘭i q 和1 i 聊+ n ，d , l l 。均为强n p 一难的对于工件增长率相同的情况，证明了问题l l p j + a t ，也ie 岛 与i p j + o ，d , i c r m 。等价并对问题1 p ，+ a t ，如( g 给出了复杂性为o ( 矿) 的动态规 划算法对同题l 协+ 耐，而i 三。a x 给出了复杂性为0 ( 扎6l o g n ) 的最优算法 尽管极小化最大完工时间的单机问题1 j p ，+ o ，t l c k 。存在多项式算法，但其它目标 函数的问题却相当复杂对于极小化加权完工时间和问题1 b + a 3 t iew j q ，b a c h m a n 和j a n i a k 7 】等证明了问题是n p 一难的而问题1 旧+ t iew j g 是未解决的o p e n 问 题大多数文献均研究其特殊情况对于工件增长率相同的情况，c h e n g 和d i n g 3 2 1 对问题1 b + o ，由 g 给出了复杂性为o ( 扎5 ) 的动态规划算法 m o s h e i o v 对问 题1 b + t l 叻q 分别研究了工件基本加工时间相同和工件增长率相同的两种特殊情 况在文献 97 中，m o s h e i o v 考虑基本加工时间相同的情况，对于问题1 l p + a ，t le w j e ， 证明了最优排序具有关于增长率的v 型性质，即在最优排序中，排在增长率最小的工件 前面的工件按增长率不增排列，而排在其后的工件按增长率不减排列对于另一种特殊情 况，问题l 协+ q f g 则更为复杂如果权与基本加工时间成比例，m o s h e i o v 1 0 0 】 证明了问题t i p ，+ q t l e j q 问题的最优排序具有关于基本加工时间的a 型性质，即在 最优排序中，排在基本加工时间最大的工件前面的工件按基本加工时间不减排列，而排 在其后的工件按基本加工时间不增排列在此基础上，给出了复杂性为o ( n l o g n ) 的多 项式算法 对于极小化最大延误问题，c h e n g 和d i n g 3 2 j 证明了问题l