（管理科学与工程专业论文）差异工件单机批调度的差分进化算法研究.pdf

摘要 摘要 调度问题是组合优化领域中的一类重要问题，在工业生产、柔性制造系统、 现代物流、计算机科学等领域有着非常广泛的应用。批调度问题是重要的一类现 代调度问题，它打破了经典调度问题中对机器的限制，即一台机器可以同时加工 多个工件而非仅仅一个工件。差异工件批调度问题是对传统批调度问题的进一步 扩展，即工件是有差异的，同一批中工件的总尺寸不能超过批的容量限制，因此， 包含在各个批中的工件数可能不同。这类问题比经典调度问题、传统批调度问题 更加复杂，但它更加接近实际工作环境，对此问题的研究具有重要的理论经济价 值。 本文首先介绍关于调度基本知识，接着从调度到经典调度，再到批调度，最 后引出差异工件批调度的介绍。并说明了差异工件批调度的研究现状。对差异工 件单机批调度问题的性质进行分析研究，给出了该问题的数学规划模型，并对已 有的若干启发式算法进行改进。 其次，本文介绍了差分进化算法的原理及背景，分析了该算法的特点以及在 解决连续性优化问题上的优势。同时，指出差分进化算法在解决具有离散特性的 调度问题上的劣势。针对调度问题的离散特性，本文重新设计了差分进化算法的 交叉操作和变异操作。并在算法核心思想不变的前提下提出具有新的迭代模式的 新差分进化算法。 接着，通过大量试验比较，确定了新差分进化算法的参数配置。利用与文献 中相同的方法产生若干种类算例，并对算法进行仿真实验。同时把本文所提的新 差分进化算法与经典文献中具有代表性的两个算法( 模拟退火算法和遗传算法) 进行比较，来检测新差分进化算法的性能。实验结果表明，与文献中以往算法相 比，差异工件单机批调度问题的新差分进化算法在仿真实验中具有更好的效果。 最后，在总结全文的基础上，对今后的研究提出了建议和展望。 关键词：调度经典调度批调度启发式算法差分进化算法组合优化 a b s t r a c t a b s t r a c t s c h e d u l i n gp r o b l e mi so d eo ft h em o s ti m p o r t a n tc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m s i ti so fg r e a ts i g n i f i c a n c ei ni n d u s t r i a lp r o d u c t i o n ，f l e x i b l em a n u f a c t u r i n g s y s t e m s ，m o d e ml o g i s t i c s ，c o m p u t e r s c i e n c ea n do t h e rr e s e a r c hf i e l d s b a t c h s c h e d u l i n gi so n e l 【i 1 1 do fi s s u et h a ti sd i f f e r e n tf r o mc l a s s i c a ls c h e d u l i n gp r o b l e m si n w h i c han u m b e ro fj o b sc a nb ep r o c e s s e ds i m u l t a n e o u s l yi no n em a c h i n e b a t c h s c h e d u l i n gp r o b l e m sw i t hn o n - i d e n t i c a lj o bs i z e s ，w h e r ej o bs i z e sa r en o tt h es a n l e ，i s a l li m p o r t a n te x t e n s i o ni nt h i sk i n do fs c h e d u l i n gp r o b l e m i ti sm 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 mb u tc l o s et or e a lm a n u f a c t u r i n gc i r c u m s t a n c e s t h e r e f o r e ， n o to n l yr e s e a r c hr e s u l t sb u ta l s oe c o n o m i cp r o s p e c ti sp r o m i s i n g i nt h i sp a p e r , w ef i r s ti n t r o d u c et h eb a c k g r o u n dk n o w l e d g eo fs c h e d u l i n g t h e n b a t c h s c h e d u l i n gi s s u e s a r el i s t e dw i t h a n a l y s i so f c u r r e n tr e s e a r c hr e v i e w m a t h e m a t i cm o d e li s p r o p o s e da n ds t u d i e d w ea l s op r o p o s e ds e v e r a l m o d i f i e d h e u r i s t i ca l g o r i t h m s t h i sp a p e ri n t r o d u c e st h eb a s i ci d e ao fd i f f e r e n t i a le v o l u t i o na l g o r i t h mw i t h d e t a i l e da n a l y s i so ft h ea d v a n t a g ew h i l ed e a l i n gw i t hc o n t i n u o u sc o m b i n a t i o n a l o p t i m i z a t i o np r o b l e m s m e a n t i m e ，d i s a d v a n t a g e si nh a n d l i n gd i s c r e t ep r o b l e m sa r e a l s oa n a l y z e d b a s e do nt h ed i s c r e t ec h a r a c t e r i s t i c so f 吐l i sk i n do fs c h e d u l i n g p r o b l e m s ，c r o s s o v e ra n dm u t a t i o no p e r a t i o n sa r er e d e s i g n e di nd i f f e r e n t i a le v o l u t i o n a l g o r i t h m an o v e ld i f f e r e n t i a le v o l u t i o na l g o r i t h mw i t hi t e r a t i o ns t r a t e g yi s a l s o p r o p o s e d al o to fe x p e r i m e n t sa r ei m p l e m e n t e dt od e t e r m i n et h ep a r a m e t e r si np r o p o s e d n o v e ld i f f e r e n t i a le v o l u t i o na l g o r i t h m s i m u l a t i o n sa r ec a r r i e do u tt o t e s tt h e e f f e c t i v e n e s so ft h ea l g o r i t h m s c o m p a r e dt or e p r e s e n t a t i v ea l g o r i t h m si nc l a s s i c a l s c h e d u l i n gs u c ha ss i m u l a t i o na n n e a l i n ga n dg e n e t i ca l g o r i t h m s ，t h ep e r f o r m a n c eo f n o v e ld i f f e r e n t i a le v o l u t i o na l g o r i t h mi sp r o v e dt ob eb e t t e r s u g g e s t i o n sa n df u t u r er e s e a r c ha r ep r e s e n t e di nt h el a s ts e c t i o n k e yw o r d s ：s c h e d u l i n g ，c l a s s i c a ls c h e d u l i n g ，b a t c hs c h e d u l i n g ，h e u r i s t i ca l g o r i t h m ， d i f f e r e n t i a le v o l u t i o na l g o r i t h m ，c o m b i n a t o r i a lo p t i m i z a t i o n 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名： 签字眺卫弘盟 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 囱公开口保密( 年) 作者签名：乌二以 签字日期：喜型翌阻 导师签名： 签字日期： 第1 章绪论 第1 章绪论 本章从最基本的调度问题概念入手介绍背景知识。接着，由于调度问题种类 繁多，所以首当其冲地介绍了调度问题统一的参数表示方法。基于此，本章从介 绍经典调度开始到介绍现代调度，再到批调度，最后引出本文所研究的差异工件 批调度。通过介绍计算复杂性等相关知识，来说明本文所研究的调度问题的困难 程度。进而，逐步解少了调度问题的研究现状。最后分析本文所研究的调度问题 的内容及意义，并简单介绍了论文的结构。 1 1 调度问题介绍 调度问题是组合优化一类问题的重要组成部分，在工业生产、柔性制造系统、 现代物流、计算机科学等领域有着非常广泛的应用。在工业生产中，如有效的调 度能使制造业增加产量、减少周转时间、减少在制品库存，最终减少生产费用。 然而调度问题很难求解，绝大多数调度问题都是n p h a r d 。正是由于调度问题的 实用性和难求解性，激发了国内外大量学者从事调度问题研究，成为推动调度问 题研究的原动力。 1 9 5 4 年j o h n s o n ( 1 9 5 4 ) 发表了第一篇关于调度的论文，从这篇文章问世以 来短短的半个世纪中世界已经发表调度文献两千多篇，其中绝大部分是在过去 1 0 年中发表的。从此以后调度问题研究成为发展最迅速、研究最活跃、成果最 丰硕、前景最诱人的学科领域之一。 1 1 1 调度问题概念及参数表示 调度的英文用词是s c h e d u l i n g ，也有称为安排时间表或排序( 唐国春等， 2 0 0 3 ) ，是在一定的约束条件下对工件和机器时间进行分配和安排次序，使某一 个或某一些目标达到最优。其中，工件是被加工的对象，是要完成的任务；机器 是提供加工的对象，是完成任务所需要的资源。 由于调度问题约束条件的不同改变，可以产生不同的调度问题，所以调度问 题种类繁多。但处理机、任务或作业和目标函数是组成调度问题的三要素。本文 采用唐恒永和赵传立在文献( 2 0 0 2 ) 中的表述，对调度问题的三要素作一介绍。 1 、处理机 只有一个处理机的调度问题称为单( 处理) 机( s i n g l ep r o c e s s o r , s i n g l em a c h i n e ) 第1 章绪论 调度问题，否则称为多( 处理) 机调度问题。在多处理机调度问题中，如果所有的 处理机都具有相同的功能，称它们为同类机或平行机( p a r a l l e lp r o c e s s o r s ) 同类机按处理的速度又分为三种类型：如果所有的处理机具有相同的速度， 称之为同速机( i d e n t i c a lp r o c e s s o r s ) ：如果处理机的速度不同，但每个处理机的速 度都是常数，不依赖被加工的任务，称它们为恒速机( u n i f o r mp r o c e s s o r s ) ；如果 处理机的速度依赖被加工的任务，它们被称为变速机( u n r e l a t e dp r o c e s s o r s ) 多处理机的另一种情况是多类型机( d e d i c a t e dp r o c e s s o r s ) 。多类型机指的是坍 个处理机具有不同的功能。在多处理机环境中，被加工的任务需要在不同的处理 机上加工。在这种情况下，把任务( t a s k ) 称为作业( j o b ) 。设有作业集 j = 以，以，以) ，每个作业，有甩，道工序( o p e r a t i o n ) 五，互，“，瓦工序指的是 作业在某处理机上被加工的这部分任务。 如果每个作业需要在每个处理机上加工，即疗，= 聊，j = 1 ，2 ，甩而且每个作 业的工序也相同，即在处理机上加工的顺序相同，把这种多类机的环境称为刚顷 序作业或流水作业( f l o ws h o p ) 如果每个作业需要在每个处理机上加工，每个作 业有自己的加工顺序，称之为异顺序作业( i o bs h o p ) 如果每个作业需要在每个处 理机上加工，每个作业可按任意顺序加工，把它称为自由顺序作业或开放作业 ( o p e ns h o p ) 。在多处理机中，还有一种更复杂的情况，这就是柔性流水作业 ( f l e x i b l ef l o ws h o p ) ，它是流水作业和平行机的推广。在柔性流水作业中，有s 类 处理机，第，类有s ，个平行机，每个作业有j 道工序，每道工序需要在每类平行 机中的一个处理机上加工，且每个作业的加工顺序相同。 为了方便起见，把同顺序作业、异顺序作业、开放作业和柔性流水作业通称 为车间调度。处理机的各类型和环境总结如图( 1 1 ) 所示： 单处理机 i 同速机 同类机( 平行机) 恒速机 i 变速机 f 同顺序作业( 流水作业) 多类机( 车间作业) 同顺序作业 i 自由顺序作业( 开放作业) 柔性流水作业 图1 1 处理机分类 2 、任务和作业 调度问题中的约束条件，主要指的是任务和作业的性质以及它们在加工过程 中的要求和限制。下边的数据描述了任务的一些性质。 2 第1 章绪论 任务的加工时间向量是p ，= ( a ，岛，一，) ，其中乃是任务乃的处理机只 上所需的加工时间。对同速机有只，= p j ，f = l ，2 ，m ，对恒速机有 助= p 岛，f - - - 1 ，2 ，m 其中p ，是标准的加工时间( 一般是速度最慢的处理机的 加工时间) ，勿是处理机只的速度因子。在车间作业的调度问题中，作业，的加 工时间向量是乃= ( a ，仍，助) ，其中既是工序乃在对应的处理机上的加工时 间。 到达时间( a r r i v a lt i m e ) 或者准备时间( r e a d yt i m e ) ，是任务正已经准备好可 以被加工的时间。如果所有的任务的准备时间相同，取，= 0 ，_ ，= 1 ，2 ，z 工期 ( d u ed a t e ) d ，表示对任务正限定的完工时间。如果不按期完工，应受到一定的惩 罚。绝对不准许延误的工期称为截至期限( d e a d l i n e ) 。优先因子w ，是一个权，它 表示任务z 相对于其他任务的重要程度。 任务被加工时的一个重要约束是可中断( p r e e m p t i v e ) 或不可中断 ( n o n - p r e e m p t i v e ) 。如果调度问题中，每一个任务在加工时的任一时刻都可以暂停 加工，加工该任务的处理机可去加工任何其他任务，以后可在任何时间在任意处 理机上从新继续加工，这种调度问题称之为可中断调度。任何任务都不允许中断 的调度问题称为不可中断调度。 3 、目标函数 用c = ( c l ，c 2 ，g ) ，表示任务的完工时f 司( c o m p l e t i o nt i m e ) ，要极小化的目 标函数总是完工时间c ，的函数。在调动问题中，目标函数主要有下面几种。 制造跨度( m a k e s p a n ，s c h e d u l i n gl e n g t h ) 定义为l = m a x q ，它等于最后 一个工件被加工完任务的完工时间，小的制造跨度意味着处理机有高的利用率。 平均加权流时间( m e a nw e i g h t e df l o wt i m e ) 是 ，= _ 弓_ = l j - - i 其中c = q 一0 是任务巧的流时间，它等于任务在系统中等待时间与加工时间的 和。在计算机系统中，作业或进程的流时间称为周转时间，所以平均加权流时间 也称为平均加权周转时间。把平均加权流时间进行变形，即 f = _ 弓= e 一巧o ( 1 2 ) = l，。lj = l j - - i罩1= l 式( 1 1 ) 中的第一项的分母和第二项都是常数，极小化，相当于极小化加权总完工 时间( t o t a lw e i g h t e dc o m p l e t i o nt i m e ) ，即 c = 叶q ( 1 3 ) 3 第1 章绪论 当m = l ，_ ，= l ，2 ，以时，加权总完工时间就是总完工时间( t o t a lc o m p l e t i o nt i m e ) ， 即 一 c = c j ( 1 4 ) ；l 最大延误( m a ) 【i m 眦l a t e n e s s ) 定义为k = m a x ) ，其中l = q 一乃是任务 z 的延误时间( 1 a t e n e s s ) 。加权总误工( t o t a lw e i g h t e dt a r d i n e s s ) 是 d = w f d f ( 1 5 ) _ jj 、7 其中q = m a x q 一嘭，0 ) = m a x l ，0 ) 是任务弓的误工时间。 加权误工任务数( w e i g h t e dn u m b e ro ft a r d yt a s k s ) 是 u = e w y j ( 1 6 )、， 其中 = l 器 m 7 ， 是对任务z 误工的单位惩罚。 不同的约束可以得到不同的调度问题，所以调度问题种类繁多。为了系统的 简化表示调度问题，1 9 7 9 年g r a h a m 、l a w l e r 、l e n s t r a 和r i n n o o yk a n 等( 1 9 7 9 ) 提出用三参数来描述调度问题。下面简单介绍一下目前通用的三参数口l i 厂表 示法( 唐恒永等，2 0 0 2 ) 。 ( 1 ) 、口域表示机器的数量、类型和环境，主要有： 1 ( s i n g l ep r o c e s s o r ) - 指只有一台机器，此类问题成为单机问题。 p ( i d e n t i c a lp a r a l l e lp r o c e s s o r s ，同速机) ：指所有的机器都具有相同的速度； o ( u n i f o r mp a r a l l e lp r o c e s s o r s ，恒速机) ：指机器的速度不同，但每个机器 的速度都是常数，不依赖于被加工的工件： r ( u n r e l a t e dp a r a l l e lp r o c e s s o r ，变速机) ：指机器的速度依赖于被加工的工 件： p 、q 、r 类机器统称为平行机，记机器的数量为m ，则上述三类平行机问 题依次表示为砌、跏、r m f ( f l o ws h o p 机器模型，流水作业) ：指工件需要在所有机器上加工，且每 个工件在所有机器上的加工序列相同； j ( j o bs h o p 机器模型，异序作业) ：指工件需要在所有机器上加工，且每个 工件有自己的加工序列； 4 第1 章绪论 o ( o p e ns h o p 机器模型，自由作业) ：指作业需要在所有机器上加工，而每 个工件在所有机器上的加工序列可以任意； 记机器的数量为m ，则上述三类车间调度问题依次表示为f m 、砌、o m 。 ( 2 ) 、域表示工件的性质、加工要求和对加工的限制等约束条件，它可同时 包含多项，也可为空，如r t 、p m t n 、p r m u 分别表示工件有到达时间、工件加工 时允许中断、车间调度中工件按排列方式加工。 ( 3 ) 、厂域表示目标函数。常见的目标函数有：制造跨度( m a k e s p a n ) c m 。、 加权完工时间和罗w ，c ，、最大延误数l 。等。本论文仅研究目标函数为制造跨 度的调度问题，这类也是实际生产生活中最常见的一类问题。 1 1 2 经典调度问题与现代调度问题 调度问题可分为经典调度( c l a s s i c a ls c h e d u l i n g ) 和现代调度( m o d e m s c h e d u l i n g ) 。根据l a w l e re l ，l e n s t r ajk ，r i n n o o y k a n ah g 和s h m o y sd b ， 1 9 8 9 年的观点( 1 9 8 9 ) ，经典调度问题有如下四个基本假设： ( 1 ) 资源的类型。机器是加工工件所需的一种资源经典调度假设，一机器在 任何时刻最多只能加工一个工件；同时还假设，一个工件在任何时刻至多在一台 机器上加工。 ( 2 ) 确定性经典调度假设决定调度问题的一个实例的所有( 输入) 参数都是事 先知道的和完全确定的。 ( 3 ) 可运算性经典调度是在可以运算、可以计算的程度上研究调度问题，而 不去顾及诸如如何确定工件的交货期，如何购置机器和配备设备等技术上可能发 生的问题。 ( 4 ) 单目标和正则性经典调度假设调度的目的是使衡量排法好坏的一个一维 目标函数的函数值为最小，而且这个目标函数是工件完工时间的非降函数这就 是所谓正则目标。 符合以上四个假设我们就称之为经典调度，而现代调度正是对以上假设的 突破得到。比如对假设一的突破可以有成组分批调度、同时加工调度、不同时开 工调度和资源受服调度等；对假设二的突破可以有可控调度、随机调度、模糊调 度和在线调度等；对假设三的突破可以有人员调度和智能调度等：对假设四的突 破可以有多目标调度、准时调度和窃时调度等。 唐国春等在其著作现代排序论( 2 0 0 3 ) 里，通过系统的归纳总结，将现 代调度分为1 0 种现代调度模型，分别为成组分批调度( s c h e d u l i n gw i t hb a t c h i n g a n dl o t ，s i z i n g ) 、同时加工调度( b a t c hs c h e d u l i n g ) 、不同时开工调度( s c h e d u l i n gw i t h n o n s i m u l t a n e o u sm a c h i n ea v a i l a b l et i m e ) 、资源受限调度( r e s o u r c e c o n s t r a i n t 第1 章绪论 s c h e d u l i n g ) 、可控调度( c o n t r o l l a b l es c h e d u l i n g ) 、随机调度( s t o c h a s t i cs c h e d u l i n g ) 、 模糊调度f f u z z ys c h e d u l i n g ) 、在线调度( 0 n 1 i n es c h e d u l i n g ) 、多目标调度 ( m u l t i c r i t e r i as c h e d u l i n g ) 、准时调度( j i t s c h e d u l i n g ) 、窗时调度( d u ew i n d o w s s c h e d u l i n g ) 。 1 1 3 批调度与差异工件批调度问题 批调度( b a t c hs c h e d u l i n g ) 问题是重要的一类现代调度问题，它打破了经典 调度问题假设( 1 ) 的限制，即一台机器可以同时加工多个工件而非仅仅一个工件。 w e b s t e r 和b a k e r ( 1 9 9 5 ) 区分了三类批调度：( 1 ) b u m i n 型，参阅b r u c k e r pe ta l ( 1 9 9 8 ) ，一个批次的加工时间等于该批次中所有工件的加工时间的最大者， 又称为平行分批调度；( 2 ) s w i i 型，参阅a l b e r sse ta l ( 1 9 9 3 ) ，一个批次的加工 时间等于该批次中所有工件的加工时间之和，并且当一个新批开始时，有一个安 装时间s ，此类问题又称为继列分批调度问题；( 3 ) c o n s t a n t 型，参阅文献a h m a d i jhe ta 1 ( 1 9 9 2 ) ，一个批次的加工时间是一个常数，与该批次中所包含的工件无 关。 我们研究b u r n i n 型。这一类问题起源于大规模集成电路生产过程中的燃烧 操作调度问题。集成电路生产的最后一个阶段是燃烧操作，将芯片放在板子上然 后放入烤箱烘烤，烘烤过程中出现问题的芯片就被淘汰。每个芯片有一个预定的 燃烧时间，经受住这段时间烘烤的芯片被视作合格产品。芯片的燃烧时间与它的 类型和( 或) 客户的要求有关。由于芯片在烤箱中的停留时间可以大于它的燃烧时 间，因此可将不同的产品作为一批同时放入烤箱进行烘烤。这样，一个批次的加 工时间就是该批次中所有产品的燃烧时间的最大者。将烤箱视为批机器，燃烧操 作调度问题就是将所有的n 个工件进行分批，然后在机器上安排加工，使得某个 目标函数最优。 批调度问题又可区分为工件具有相同尺寸和工件具有不同尺寸两类问题。在 第一类问题中，工件没有大小之分，机器的容量定义为可同时加工工件的个数； 如相同类型的集成电路生产过程中的燃烧操作等。在第二类问题中，每个工件有 其特定的容量需求，同一批中工件的总尺寸不能超过批的容量限制，因此，包含 在每一批中的工件个数可能不同；如不同种类集成电路生产过程中的燃烧操作、 金属加工业的热处理工序等。从工件尺寸的角度来讲，前者可以称为同类工件的 批调度问题，而后者可以称为差异工件的批调度问题。差异工件批调度问题的例 子还有很多，如陶瓷烧制、港口货物装卸、汽车货运等，它更贴近实际生产生活 中的问题。目前，关于第一类问题已有相当多的文献研究，而在差异工件批调度 问题上的研究较少。 6 第1 章绪论 批调度问题要远远复杂于经典调度问题，它可以看作是由分批和批的加工两 个子问题组成的。分批子问题即是在满足批容量约束的前提下把工件分为多个批 次；批加工子问题是在工件分批后，安排这些批在机器上加工，此时可以把一个 批看作一个工件，这样，第二个子问题即是经典调度问题( 与经典调度不同的是， 这里批的加工时间是不确定的，它由第一个子问题的解给出) 。 而差异工件批调度问题的研究具有重要的理论经济价值。它进一步扩展了经 典调度理论，在经典调度的基础上结合了空间约束，提供了新的研究方向。而且， 它有着广泛的实际应用背景，如在芯片集成制造系统中，生产调度决策好坏直接 决定了半导体芯片工业的效率和对客户需求的响应速度，并且该工业在整个经济 发展中扮演了重要角色，而预烧工序通常又是半导体制造企业进行有效生产调度 的关键之一。这是因为预烧工序相对于其它工序，它的加工时间特别长，并且它 发生在制造过程的末端，几乎没有可能通过后续工序的挖潜来补偿预烧工序的延 迟，因此该工序对按期交货有直接影响。而且相对于其它的制造业来说，半导体 制业的设备费用十分昂贵，因此资源有效使用就显得更为关键。通过对本课题的 研究可以对工业生产中的瓶颈给予帮助。 下文中，如不特别声明，同类工件批调度问题简称为批调度问题。 1 2 计算复杂性与n p 类问题 组合优化问题( 唐国春等，2 0 0 3 ) ，( b r u c k e rp ，2 0 0 1 ) ，( c a r e ymre ta l ， 1 9 9 7 ) ，( 孙世杰，1 9 9 1 ) 的难易程度是针对一些有代表性的问题而言的。所谓问 题是指需要回答的一般性的提问，通常含有若干个参数或自由变量。若给定所有 参数具体的值后，便可得到问题的一个实例，即一个最优化问题，就是这个问题 的一些实例的集合。如对于问题l i ，i g 。，当工件个数n ，以及各工件的加工时 间p ，、到达时间，等情况都确定之后，就得到问题1lr ，ic m 。的一个实例。某一 组合最优化问题的任一实例能否被实际有效的解决决定了其难易程度。 实例用计算机表示出来所占用的存储单元数，定义为实例的大小( 或输入规 模) 。当计算机每执行一次初等运算( 包括算术运算、比较和转移) ，需要一个单 位时间，一个算法在计算机上执行所需要的时间定义为其执行初等运算的次数。 对于所有规模为，l 的输入，算法的行为可能不同，我们把其中最坏的行为定义为 算法关于规模为n 的复杂性。因此算法复杂性是输入规模的函数。 8 0 年代以后，调度问题的研究引入了计算复杂性理论。计算复杂性理论认 为，当算法的复杂性被输入规模的多项式界定时，该算法为多项式算法，这样的 算法是可以接受的，也是实际有效的，一般认为这样的算法为好的算法。 7 第1 章绪论 一个组合最优化问题通常有三种提法( 徐连诚，2 0 0 6 ) ：最优化形式、计值 形式、判定形式。我们按问题的复杂性把最优化问题分类。一个组合最优化问题 的判定形式可描述为：给定一个组合最优化问题m i n f ( x 1s t x x ，问是否存 在可行解，使得了f ( x 0 1 三? 这里x 是有限集，上为整数。即判定问题是需要 用“是 或“否 来回答的问题类。 一般我们根据判定问题的复杂性把最优化问题分类。用p 表示多项式时间算 法所能解决的判定问题类，即尸类是相对容易解决的最优化问题，它们有有效算 法。对于n p 类问题并不要求它的每个实例都能用某个算法在多项式时间内得到 回答，而只要求，如果x 是问题的答案为“是 的实例，则存在对z 的一个简短 证明( 其大小以x 的长度的多项式为界) ，使得能在多项式时间内检验这个证明 的真实性。由上述可见，有p 脚。 设a l 和a 2 都是判定问题，称a l 在多项式时间内归结为a 2 ，当且仅当a i 有多项式时间的算法，并且岛是多次的以单位费用把a 2 的算法一用作子程序 的算法，把l 叫做a 1 到a 2 的多项式归结。 如果给定任意符号串x ，可以在( x 的) 多项式时间内能构造出符号串y ， 使x 是a l 的回答为“是”的实例当且仅当y 是a 2 的回答为“是”的实例，则称 判定问题a l 多项式地变换到另一个判定问题a 2 。 判定问题a 脚称为是n p 完备( n p c o m p l e t e ，简记为n p c ) 的，如果所 有其它的n p 问题都能多项式归结到a 。此时，判定问题a 所对应的由最优化形 式描述的问题称为是n p 难的( n p h a r d ) 。 1 3 调度问题研究现状 差异工件批调度问题是经典调度问题的扩展。其研究问题涉及生产运作管 理、数学规划、动态规划、算法分析和设计、计算数学、概率论、随机过程等众 多学科。 调度问题因其在生产管理中的重要性，半个多世纪以来一直是研究热点之 一，其研究成果非常丰富。因此，下面列出与本研究课题相关的一些研究成果， 仅介绍目标函数为制造跨度c 眦和( 加权) 完工时间和z c , ( z w , c , ) 的经典调度 问题、批调度问题和差异工件批调度问题的研究成果。 除1 1 节介绍的记号外，下文还出现的几个记号说明：砌( b ) 表示平行批机 器，批机器的容量为b ：五( 骂，色) 表示两阶段的f l o ws h o p 批调度问题，第一阶 段机器的批容量为墨，第二阶段机器的批容量为暖。若域中含s ，则表示差异工 件，此时批机器中一次至多可加工的工件总尺寸小于等于机器容量b ；否则批机 8 第1 章绪论 器中一次至多可以加工b 个工件。 1 3 1 经典调度问题 单机调度问题1 i i 罗w ，c ，由加权最短处理时间w s p t ( w e i g h t e ds h o r t e s t p r o c e s s i n gt i m e ) 分派规则可以求得最优解，但问题l l l z w j c , 已是n p 难的 ( l e n s t r ajke ta l ，1 9 7 7 ) 。对于问题1i i w ，c ，h a l le ta 1 ( 1 9 9 7 ) 给出了性能 比为3 + e ( e 0 1 的确定性在线算法；g o e m a n se ta 1 ( 2 0 0 1 ) 给出了性能比为1 6 8 5 3 的随机在线算法；另一方面，a f r a t ie ta 1 ( 1 9 9 9 ) 则给出了该问题的多项式时间 近似策略p t a s ( p 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 ) 算法，即性能比可任意 接近于l 。 问题p l ic 嗽是强n p 难的( g a r e ye ta l ，1 9 7 5 ) ，h o c h b a u m 和s h m o y s 1 9 设 计了该问题的p t a s 算法，这是调度问题p t a s 算法研究的一个突破。问题p l c 。 的l p t ( 1 0 n g e s tp r o c e s s i n gt i m e ) 分派规则的性能比为4 3 1 3 m ，且这个界是紧的； 而对于问题尸l i 气，l p t 分派规则是3 2 的近似算法( h o c h b a u m ，1 9 9 5 ) 。 对于问题尸l i c f ，可以使用最短处理时间s p t ( s h o r t e s t p r o c e s s i n g t i m e ) 优 先规则获得最优解；同时，变速机问题尸l | c ，可由二部图匹配( b i p a r t i t e m a t c h i n g ) 方法在多项式时间内求得其最优解( h o r n ，1 9 7 3 ) 。但对于问题 pl i w ，c ，即使只有两台机器情况，已是n p 难的( l e n s t r ajke ta l ，1 9 7 7 ) 。对 于平行机调度问题p l ，i c ，c h e k u r ie ta l ( 1 9 9 7 ) 运用抢占式单机松弛算法获 得性能比为3 1 m 的近似算法。对于问题r l i w ，c ，h a l le ta 1 ( 1 9 9 7 ) 基于 线性规划给出了性能比为1 6 3 的近似算法，而s k u t e l l a ( 2 0 0 1 ) 基于半正定规划 松弛设计了性能比为2 的近似算法。另一方面，a f r a t ie ta l ( 1 9 9 9 ) 则给出了问 题e l 乃i m q 、砌i _ i q 的p t a s 算法。 问题f 2 1 1 c 腻、d 2 1o p 2 1 c i ( o p 为作业的最大工序数) 、0 2 1 1 c , , 分别可在 o ( n l o g n ) 、o ( n l o g n ) 、o ( n ) 时间内求得最优解( j o h n s o n ，1 9 5 4 ) ，( j a c k s o n ，1 9 5 6 ) ， ( g o n z a l e ze ta l ，1 9 7 6 ) 。当m 3 时，问题f r a i l 、j m l ic 嘣是强n p 难的( g a r e y e ta l ，1 9 7 6 ) ，但问题o m l lc 。是否是强n p 难仍然是个开放问题。问题f r ai lc a 、 j m l l c i 、o m i f 已有p t a s 算法( j a n s e ne ta l ，2 0 0 3 ) ，( h a l lla ，1 9 9 8 ) ， ( s e v a s t i a n o ve ta l ，1 9 9 8 ) 。问题f 2h lc 斌是强n p 难的( l e n s t r ae ta l ，1 9 7 7 ) ， p o t t s ( 1 9 8 5 ) 给出了性能比为5 3 的启发式算法；h a l l ( 1 9 9 4 ) 基于j o h n s o n 算法 设计了该问题的p t a s 算法。g o n z a l e z 和s a h n i ( 1 9 7 8 ) 首先给出了问题f m i i c ， 的基于s p t 的启发式算法，性能比为m ；s m u t n i c k i ( 1 9 9 8 ) 证明了问题 砌i p r m u w ，c f 的基于w s p t 的启发式算法的性能比也为所。h o o g e v e e n 和 k a w a g u c h i ( 1 9 9 9 ) 证明了问题f 2 l iy c ，的基于s p t 的启发式算法的性能比为 9 第1 章绪论 2 p ( 口+ p ) ，口为所有2 n 个工序中最小的处理时间，b 为所有2 聆个工序中最大的 处理时间：赵传立、张庆灵和唐恒永( 2 0 0 2 ) 证明了如果作业权重具有一致权因 子，那么1 6 j 题f 2i i c j 的基于w s p t 的启发式算法的性能比也为2 f l ( a + f 1 ) 。 f i s h k i ne ta 1 ( 2 0 0 3 ) 提供了问题咖i d p 肛，：fi _ q 的p t a s 算法( 为常数) 。 1 3 2 批调度问题 问题1 ( o o ) i i c o 、l ( 1 ) i i c 眦是平凡问题。而对于b ( 2 b 刀) 的问题i ( b ) i i c m ， b r u c k e re ta 1 ( 1 9 9 8 ) 给出了s p t 批最优调度算法，时间复杂性为 m i l l d ( 刀l o g 厅) ，d ( 疗2 b ) 。对于问题l ( 口) j ，p ，= p l c m ，i k u r a 和o i m p l e ( 1 9 8 6 ) 给 出了求最优解的有效算法。对于问题l ( o o ) i l c 眦，虽然l e e 和u z s o y ( 1 9 9 9 ) 提 供了时间为o ( 刀2 1 的求最优解算法，但p o o n 和z h a n g ( 2 0 0 0 ) 给出了时间为 o ( n l o g n ) 的求最优解算法。对于强n p 难的问题l ( b ) i i 气，b r u c k e r e ta l ( 1 9 9 8 ) ， l e e 和u z s o y ( 1 9 9 9 ) 对该问题的几种特殊情况分别给出了多项式时间和伪多项 式时间的算法：而l i u 和y u ( 2 0 0 0 ) 证明了问题l ( 引l q 。的贪心启发式算法性 能比为2 ，并且证明了问题1 ( 2 ) 1 吩 o ， ic 咄是n p 难的，给出了问题l ( 2 ) i _ r ：ic 眦在 不同到达时间数目固定情况下的伪多项式时间算法。 对于问题l 一) 罗c 。，b m c k e r e t a l ( 1 9 9 8 ) 给出了后向动态规划( b a c k w a r d d y n a m i cp r o g r a m m i n g ) 算法，时间复杂性为o ( n l o g n ) ；而对于的问题 l ( b ) | | e c ，( 2 b 盯) ，他们也给出了后向动态规划算法，时间复杂性为d f 门叫乒o l 。 当只有历m ：j j 薯b s ， ( 2 1 3 ) 重复此过程，直至所有工件都安排到了批中。 s t e p 3 ：以任意顺序在机器上加工批。 此算法从批的角度考虑，试图在生成批时，同时考虑工件的加工时间和工件 尺寸，虽然如此，但它把工件的加工时间和工件的尺寸放在了同样的约束地位， 这样可能造成最小加工时间的工件和最大加工时间的工件同一批，致使批的负载 均衡率较大。 5 、其他 记算法f f ( f i r s t - f i t ) 为：选择列表中的第一工件，把它放入有足够剩余空 间容纳该工件的编号最小的批中；如果这样的批不存在，则为此工件创建一个新 批。重复此过程，直至所有工件都加入到了批中。 ( 1