（管理科学与工程专业论文）差异工件批调度问题研究与算法设计.pdf

摘要 摘要 调度问题是组合优化领域中的一类重要问题，在柔性制造系统、现代物流、 计算机科学等领域有着非常广泛的应用。批调度问题是重要的一类现代调度问 题，它打破了经典调度问题中对机器的限制，即一台机器可以同时加工多个工 件而非仅仅一个工件。差异工件批调度问题是对传统批调度问题的进一步扩展， 即工件是有差异的，同一批中工件的总尺寸不能超过批的容量限制，因此，包 含在各个批中的工件数可能不同。这类问题比经典调度问题、传统批调度问题 更加复杂，但它更加接近实际工作环境，对此问题的研究具有重要的理论经济 价值。 首先，本文分析了差异工件批调度问题中的两个约束条件( 工件加工时间 约束和工件尺寸约束) 对问题的解的影响，从而引申出两个启发式概念( 批的 利用率和批的负载均衡律) 。并基于它们构造了几个启发式规则算法，并分析了 它们与以往文献中的启发式规则算法的关系，以及其中一些算法的最差性能比。 其次，鉴于蚁群优化算法在求解离散优化问题上的优越性，本文研究了蚁 群优化算法在求解差异工件批调度问题中的应用。引入批的利用率和批的负载 均衡率作为启发式信息，构造了差异工件单机批调度问题的蚁群优化算法。并 对各种编码下的蚁群算法的搜索空间的规模进行了分析，分析了搜索空间与问 题解空间的关系。结果表明，与以往算法相比，差异工件单机批调度问题的蚁 群优化算法在实际应用中具有更好的效果。 最后，在总结全文的基础上，对今后的研究提出了建议和展望。 关键词：调度；批机器；启发式算法；算法性能分析；蚁群优化算法；组合优化 a b s t r a c t ab s t r a c t s c h e d u l 抽gp r o b l 锄i s0 n eo ft h em o s ti i i l p o r t 锄tc o m b i n a t o r i a lo p t i i l l i z a t i o n p r o b l e m s i t i s v e d ，i m p o r t 锄t i nf l e x i b l e m 彻u f a c t u r i n gs y s t e m s ，m o d e m l o g i s t i c s ，c o m p u t e rs c i e n c ea n do t i l e rf i e l d s n o to n l yo n ej o bb u tan u m b e ro f j o b sc 觚 b ep r o c e s s e ds i m u l 锄e o u s l yb yab a t c hm a c h i n e ，s 0b a t c hs c h e d u l i n gp r o b l e mi so n c o ft h em o s ti m p o r t 锄tm o d e ms c h e d u i i n gp r o b l e m s b a t c hs c h e d u l i n gp r o b l e mw i t h n o n - i d e n t i c a lj o bs i z e s ，i nw h i c ht h ej o b sa r en o n - i d e n t i c a li ns i z e ，i sa ne x t c n s i o no f b a t c h s c h e d u l i f l gp r o b j 锄 n i sp r o b l e mj sm o r e c o m p l i c 砷葩 t h 锄c l 觞s i c a l s c h e d u l i n gp r o b l e m 锄dc l a s s i c a lb a t c hs c h e d u l i n gp r o b l e m ，b u ti tp r e s s e sc l o s et ot l l e r e a le n v i r o n m e n ta n d l er e s e 砌lo ni th 懿i m p o r t 锄ts i g n i f l c 觚c ei nt l l e o 巧踟d e c o n o m y f i r s t ，t h e d i s s e r t a t i o nr c s e a r c h e st h er c l a d o nb e 眦e nt w oc o n d i t i o n a l c o n s t r a i n t s ( t h ep r o c e s s i n gt i m ec o n s 柏i n to fj o b s 锄dt h es i z ec o n s 觚i i l to fj o b s ) 锄dt h es o l u t i o no f b a t c hs c h e d u l i l l gp r o b l 锄w 曲n o n i d e n t i c a lj o bs 胁s n e nt h e c o n c e p to fu t i l i z a t i o nr a t i oa n dl o a db a l a n c er a t i oo fab a t c hw 硒p r o p o s e d f 0 r m i n i m i z i n gm a k e s p 觚f o rs c h e d u l i l l gj o b sw i t hn o n - i d e n t i c a ls i z c so nas i n g l eb a t c h p r o c e s s i n gm a c h i n e ，t h ed i s s 雠a t i o ne x p l o r e san u m b e ro f h e u r i s t i ca l g o r 弛m sb a s e d o nt h eu t i l i z a t i o nr a t i oa 1 1 dl o a db a l a n c er a t i oo fab a t h ，觚dp a n i a l l ys t u d i e st h ew o r s t c a s ea 1 1 a l y s i so f t h e s eh e u r i s t i ca l g o r i m m s 1 1 l e n ，t h ed i s s e r t a t i o nc o n s i d e i sb a t c hs c h e d u l i n gp r o b l e mw i t hn o n i d e n t i c a lj o b s i z e su s i n g 锄tc o l o n yo p t i m i z a t 沁na l g o r i t t 眦s 1 w o 觚tc o l o n yo p t i m i z a t i o n a 1 9 0 r i t h m sw e r ep r o p o s e d c o m p a r e dw i t ht h e 仃a d i t i o n a la n tc o l o n yo p t i m i z a t i o n a i g o r i t h m ，t h e yi n t r o d u c en e wh e u r i s t i ci n f o n l l a t i o nt h a ti su t i l i z a t i o nr a t i oa i l dl o a d b a l a n c er a t i oo fab a t c hf o rn l i s p r o b l e m c 0 m p u t a t i o n a lr e s u l t ss h o wt h a tt h e y s i 印i f i c a n t l yo u 印e r f o mo t h e ra 1 9 0 r i t h m sa d d r e s s e di ni i t e r a t u r e t | i e s er c s u n ss h o w t h a tt h e ya r em o r ee f f b c t i v ea n de 塌c i e n tm e t h o df o rs o l v i n gs c h e d u l i n gp r o b l e m st o m i n i m i z em a k e s p a no nas i n g l eb a t c hp r o c e s s i n gm a c h i n ew i t l ln o n i d e n t i c a lj o b s i z e s i i f i n a l i y t h ed i s s e r t a t i o ns u m su pt h eo v c r a nw o 呔s ，a n dg i v e ss o m er e s e a r c 置i p r o p o s a l so f t h ek e yp o i n t so nm ei s s u ei nt 1 1 ec o m i n gs t a g e k e y w o r d s ： s c h e d u l i n g ； b a t c h p r o c e s s i n gm a c h i n e s ； h e u r i s t i ca l g o r i t ； a l g o r i t l l ma n a l y s i s ；a n tc o l o n yo p t i m i z a t i o n ；c 0 m b i 彻r t o r i a lo p t i l n i z a t i o n i u 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：咝 绷年多r 砑日 第1 章绪论 第1 章绪论 调度问题是组合优化领域中的一类重要问题，在柔性制造系统、现代物流、 计算机科学等领域有着非常广泛的应用。求解调度问题是困难的，绝大多数调 度问题都是n p 难的甚至是强n p 难；但有效的调度系统可以使现代商业领域增 加产出、减少周转时间、减少库存，最终减少生产成本、增加利润和客户满意 度，所以调度系统性能的好坏对这些行业的高效运作有着重要的影响。 本章首先对调度问题中的概念及符号做了简单描述，然后介绍了本论文研究 的具体问题差异工件批调度问题，以及相关调度问题的研究现状；最后简述了 本论文的研究动机、结果和本论文的结构。 1 1 调度问题概念 调度问题是指作业或任务如何占用有限资源的决策过程，其目标是使某一函 数最优，而目标函数通常是对加工时间的长短、资源利用率的描述。调度问题 是一类重要的组合优化问题。 本文研究机器调度问题，是指如何分配工件( 作业) 在机器上进行加工处理， 以使某一目标函数最优。工件( 作业) 在机器上加工时可能需要满足一定约束 条件，如工件的到达时间、工件的加工顺序、工件加工时是否允许抢占、机器 对工件加工时间的影响等等。 为便于叙述，本文使用通用的三元组符号口i l 厂来描述调度问题的类型f l 】， 即从机器、工件和目标函数三个要素来描述调度问题。 ( 1 ) 、口域表示机器的数量、类型和环境，主要有： l ( s i n g l ep r o c e s s o r ) ：指只有一台机器，此类问题成为单机问题。 尸( 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 ，同速机) ：指所有的机器都具有相同的速度； q ( u n i f o m lp a m 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 眦e s s o r ，变速机) ：指机器的速度依赖于被加工的工件； p 、q 、r 类机器统称为平行机，记机器的数量为埘，则上述三类平行机问题 依次表示为砌、m 、砌 第l 章绪论 f ( f l o ws h o p 机器模型，流水作业) ：指工件需要在所有机器上加工，且每个 工件在所有机器上的加工序列相同； ，( j o bs h o p 机器模型，异序作业) ：指工件需要在所有机器上加工，且每个 工件有自己的加工序列； d ( o p e ns h o p 机器模型，自由作业) ：指作业需要在所有机器上加工，而每 个工件在所有机器上的加工序列可以任意； 记机器的数量为m ，则上述三类车间调度问题依次表示为砌、j 渤、o m 另外还有柔性车间调度，相关定义见文献【l 】。 ( 2 ) 、域表示工件的性质、加工要求和对加工的限制等约束条件，它可同时 包含多项，也可为空，如r f 、p m t n 、p m u 分别表示工件有到达时间、工件加工 时允许中断、车间调度中工件按排列方式加工。 ( 3 ) 、y 域表示目标函数。常见的目标函数有：制造跨度( m a k e s p a n ) g 瞰、 加权完工时间和罗w ，c ，、最大延误等。本论文仅研究目标函数为制造跨 度的调度问题，这类也是实际生产生活中最常见的一类问题。 1 2 差异工件批调度问题 1 2 1 经典调度问题与现代调度问题 调度问题有经典调度( c l a s s i c a ls c h e d u l i n g ) 和现代调度( m o d e ms c h e d u l i n g ) 之 分。根据e l a w l e r 等1 9 9 3 年的观点【2 】，经典调度问题有如下四个基本假设： ( 1 ) 资源的类型：一台机器在任何时刻最多只能加工一个工件，一个工件在 任何时刻最多只能被一台机器加工； ( 2 ) 确定性：调度问题的一个实例所需的任何输人参数都是事先知道的、完 全确定的i ( 3 ) 可运算性：经典调度是在可以运算的程度上研究调度问题，而不去顾及 诸如如何确定工件的交货期、如何购置机器和设备等技术上可能发生的问题； ( 4 ) 单目标和正则性：经典调度假设调度的目标是使衡量排法好坏的一个一 维目标函数的函数值最优，此目标函数是任何工件完工时间的非减函数( 称为 正则函数) 。 唐国春等在其著作现代排序论里【3 】，详细介绍了发展较为完备的1 0 种 现代调度模型，其中成组分批调度( s c h e d u h n gw i t hb a t c h i n g 觚dl o t s i z i n d 、同时 2 第l 章绪论 加工调度( b a t c hs c h e d u l i n g ) 、不同时开工调度( s h e d u l i n gw i t hn o n s i i i l u l t a - n e o u s m a c h i n ea v a i l a b l et i m e ) 和资源受限调度s o u r c e _ c o n s t m i n ts c h e d u l i n g ) 打破了假 设( 1 ) 的限制：可控调度( c o n t r o l l a b l es c h e d u l i n 曲、随机调度( s t o c h a s - t i cs c h e d u l i n 曲、 模糊调度( f u z 巧s c h e d u l i n g ) 和在线调度( o n - l i n es c h e d u i i n g ) 打破了假设( 2 ) 的限制； 多目标调度( m u l t i c m r i as c h e d u l i n 曲、准时调度( 儿t s c h e d u l i n g ) 和窗时调度( d u e w i n d o w ss c h e d u l i l l g ) 打破了假设( 4 ) 的限制。 1 2 2 批调度与差异工件批调度问题 批调度( b a t c hs c h e d u l i n g ) 问题是重要的一类现代调度问题，它打破了经典 调度问题假设( 1 ) 的限制，即一台机器可以同时加工多个工件而非仅仅一个工件。 w 曲s t e r 和b a k e r 【4 】区分了三类批调度：( 1 ) b u m i n 型( 参阅 5 】) ，一个批次 的加工时间等于该批次中所有工件的加工时间的最大者，又称为平行分批调度： ( 2 ) s u m 型( 参阅【6 】) ，一个批次的加工时间等于该批次中所有工件的加工时间 之和，并且当一个新批开始时，有一个安装时间s ，此类问题又称为继列分批调 度问题；( 3 ) c o n s t a n t 型( 参阅文献【7 】) ，一个批次的加工时间是一个常数，与 该批次中所包含的工件无关。 我们研究b u r n i n 型。这一类问题起源于大规模集成电路生产过程中的燃 烧操作调度问题。集成电路生产的最后一个阶段是燃烧操作，将芯片放在板子 上然后放入烤箱烘烤，烘烤过程中出现问题的芯片就被淘汰。每个芯片有一个 预定的燃烧时间，经受住这段时间烘烤的芯片被视作合格产品。芯片的燃烧时 间与它的类型和( 或) 客户的要求有关。由于芯片在烤箱中的停留时间可以大于它 的燃烧时间，因此可将不同的产品作为一批同时放入烤箱进行烘烤。这样，一 个批次的加工时间就是该批次中所有产品的燃烧时间的最大者。将烤箱视为批 机器，燃烧操作调度问题就是将所有的刀个工件进行分批，然后在机器上安排 加工，使得某个目标函数最优。 批调度问题又可区分为工件具有相同尺寸和工件具有不同尺寸两类问题。在 第一类问题中，工件没有大小之分，机器的容量定义为可同时加工工件的个数； 如相同类型的集成电路生产过程中的燃烧操作等。在第二类问题中，每个工件 有其特定的容量需求，同一批中工件的总尺寸不能超过批的容量限制，因此， 包含在每一批中的工件个数可能不同；如不同种类集成电路生产过程中的燃烧 操作、金属加工业的热处理工序等。从工件尺寸的角度来讲，前者可以称为同 3 第l 章绪论 类工件的批调度问题，而后者可以称为差异工件的批调度问题。差异工件批调 度问题的例子还有很多，如陶瓷烧制、港口货物装卸、汽车货运等，它更贴近实 际生产生活中的问题。目前，关于第一类问题已有相当多的文献研究，而在差 异工件批调度闯题上的研究较少。 批调度问题要远远复杂于经典调度问题，它可以看作是由分批和批的加工两 个子问题组成的。分批子问题即是在满足批容量约束的前提下把工件分为多个 批次；批加工子问题是在工件分批后，安排这些批在机器上加工，此时可以把 一个批看作一个工件，这样，第二个子问题即是经典调度问题( 与经典调度不 同的是，这里批的加工时间是不确定的，它由第一个子问题的解给出) 。 而差异工件批调度问题的研究具有重要的理论经济价值。它进一步扩展了经 典调度理论，在经典调度的基础上结合了空间约束，提供了新的研究方向。而 且，它有着广泛的实际应用背景，如在芯片集成制造系统中，生产调度决策好 坏直接决定了半导体芯片工业的效率和对客户需求的响应速度，并且该工业在 整个经济发展中扮演了重要角色，而预烧工序通常又是半导体制造企业进行有 效生产调度的关键之。这是因为预烧工序相对于其它工序，它的加工时间特 别长，并且它发生在制造过程的末端，几乎没有可能通过后续工序的挖潜来补 偿预烧工序的延迟，因此该工序对按期交货有直接影响。而且相对于其它的制 造业来说，半导体制业的设备费用十分昂贵，因此资源有效使用就显得更为关 键。通过对本课题的研究可以对工业生产中的瓶颈给予帮助。 下文中，如不特别声明，同类工件批调度问题简称为批调度问题。 1 3 计算复杂性与n p 类问题 组合优化问题( 【3 】【8 】【9 】【1 0 】) 的难易程度是针对一些有代表性的问题而言的。 所谓问题是指需要回答的一般性的提问，通常含有若干个参数或自由变量。若 给定所有参数具体的值后，便可得到问题的一个实例，即一个最优化问题，就 是这个问题的一些实例的集合。如对于问题l 蚓g 露，当工件个数玎，以及各工 件的加工时间办到达时间吩等情况都确定之后，就得到问题1 蚓g 脚的一个实例。 某一组合最优化问题的任一实例能否被实际有效的解决决定了其难易程度。 实例用计算机表示出来所占用的存储单元数，定义为实例的大小( 或输入规 模) 。当计算机每执行一次初等运算( 包括算术运算、比较和转移) ，需要一个单 4 第l 章绪论 位时间，一个算法在计算机上执行所需要的时间定义为其执行初等运算的次数。 对于所有规模为，z 的输入，算法的行为可能不同，我们把其中最坏的行为定义 为算法关于规模为捍的复杂性。因此算法复杂性是输入规模的函数。 8 0 年代以后，调度问题的研究引入了计算复杂性理论。计算复杂性理论认 为，当算法的复杂性被输入规模的多项式界定时，该算法为多项式算法，这样 的算法是可以接受的，也是实际有效的，一般认为这样的算法为好的算法。 一个组合最优化问题通常有三种提法( 【l o 】) ：最优化形式、计值形式、判定 形式。我们按问题的复杂性把最优化问题分类。一个组合最优化问题的判定形 式可描述为：给定一个组合最优化问题m i n 厂( x ) j j x x ，问是否存在可行解 和，使得了舰) 三? 这冁有限集，三为整数。即判定问题是需要用“是”或 “否”来回答的问题类。 一般我们根据判定问题的复杂性把最优化问题分类。用p 表示多项式时间算 法所能解决的判定问题类，即尸类是相对容易解决的最优化问题，它们有有效 算法。对于朋t 类问题并不要求它的每个实例都能用某个算法在多项式时间内得 到回答，而只要求，如果x 是问题的答案为“是”的实例，则存在对x 的一个简 短证明( 其大小以x 的长度的多项式为界) ，使得能在多项式时间内检验这个证 明的真实性。由上述可见，有尸胛 设a l 和a 2 都是判定问题，称a l 在多项式时间内归结为a 2 ，当且仅当a i 有多项 式时间的算法毛，并且是多次的以单位费用把a 2 的算法用作子程序的算法， 把弓叫做a l 到a 2 的多项式归结。 如果给定任意符号串x ，可以在( x 的) 多项式时间内能构造出符号串y ，低 是a i 的回答为“是”的实例当且仅当) ，是a 2 的回答为“是”的实例，则称判定问 题a l 多项式地变换到另一个判定问题a 2 ， 判定问题a 俨称为是p 完备( n p c o m p l e t e ，简记为p c ) 的，如果所 有其它的胛问题都能多项式归结到a 。此时，判定问题a 所对应的由最优化形 式描述的问题称为是尸难的( n p h a r d ) 。 1 4 调度问题研究现状 差异工件批调度问题是经典调度问题的扩展。其研究问题涉及生产运作管 理、数学规划、动态规划、算法分析和设计、计算数学、概率论、随机过程等 5 第l 章绪论 众多学科。 调度问题因其在生产管理中的重要性，半个多世纪以来一直是研究热点之 一，其研究成果非常丰富。因此，下面列出与本研究课题相关的一些研究成果， 仅介绍目标函数为制造跨度g 懈和( 加权) 完工时间和c ，( w ，c ，) 的经典调 度问题、批调度问题和差异工件批调度问题的研究成果。 除1 1 节介绍的记号外，下文还出现的几个记号说明：砌( 功表示平行批机器， 批机器的容量为曰；足l ，历) 表示两阶段的f l o ws h o p 批调度问题，第一阶段机器 的批容量为b 1 ，第二阶段机器的批容量为岛。若4 域中含毋则表示差异工件，此时 批机器中一次至多可加工的工件总尺寸小于等于机器容量召；否则批机器中一次 至多可以加工b 个工件。 1 4 1 经典调度问题 单机调度问题ll l 罗w ，c ，由加权最短处理时间w s ”( w e i 曲t e ds h o r t e s t p m c e s s i n gt i m e ) 分派规则可以求得最优解，但问题1i ，：，l q 已是朋哪的【1 2 】。 对于问题1ioi w ，c ，h a l le ta 1 【1 3 】给出了性能比为3 + 占( g o ) 的确定性在线算 法；g o e m a i l se ta 1 1 4 】给出了性能比为1 6 8 5 3 的随机在线算法；另一方面，a 矗i a t i e ta 1 1 5 】则给出了该问题的多项式时间近似策略p t a s ( p o l y n o m i a lt i m e a p p r o x i m a t i o ns c h e m e ) 算法，即性能比可任意接近于l 。 问题刚c r 瑚。是强p 难的 1 6 】，h o c h b a u m 和s h m o y s 1 7 】设计了该问题的p t i a s 算法，这是调度问题p t a s 算法研究的一个突破。问题尸l i 的l p t ( 1 0 n g e s t p f o c e s s i n gt i m e ) 分派规则的性能比为4 3 一l 3 所，且这个界是紧的；而对于问题 p ill ，l p t 分派规则是3 2 的近似算法【1 8 】。 对于问题尸i | c ，可以使用最短处理时间s p t ( s h o n e s tp r o c e s s i n gt i m e ) 优 先规则获得最优解：同时，变速机问题只j i 乏：c ，可由二部图匹配( b i p a r t i t e m a t c h i n g ) 方法在多项式时间内求得其最优解【1 9 】。但对于问题p l l _ 0 ，即 使只有两台机器情况，已是n p 难的【1 2 】。对于平行机调度问题p i o | c ，c h e k u r i e ta l 【2 0 】运用抢占式单机松弛算法获得性能比为3 1 朋的近似算法。对于问题 r i ，：，i w ，c ，h a l le ta i 【1 3 】基于线性规划给出了性能比为1 6 3 的近似算法，而 s l ( u t e l l a 【2 1 】基于半正定规划松弛设计了性能比为2 的近似算法。另一方面，a 胁i c t a l 【1 5 】则给出了问题尸i ，i w ，c ，、砌i ，l w f c ，的p t a s 算法。 j 。一 jjj 1 一 jj 问题，2 i i 、- ，2 i 叩2j c 傩( 印为作业的最大工序数) 、d 2 l l c 嘣分别可 6 第l 章绪论 在d ( 玎l o g 刀) 、d ( 刀l o g 疗) 、d ( 疗) 时间内求得最优解【2 2 】【2 3 】【2 4 】。当历3 时，问 题砌i | o 、咖| i c 懈是强n p 难的【2 5 】，但问题锄f | 是否是强n p 难仍然是 个开放问题。问题砌l | 、砌i i c 眦、锄f f c 懈已有p 1 a s 算法【2 6 】【2 7 】【2 8 】。 问题f 2 l r ，lc m 。是强n p 难的【1 2 】， p 嘣s 【2 9 】给出了性能比为5 3 的启发式算法； h a l l 【3 0 】基于j o l l i l s o n 算法设计了该问题的p 1 a s 算法。g o i l z a l e z 和s a l l l l i 【3l 】首先给 出了问题砌0 y c 。的基于s p t 的启发式算法，性能比为m ；s m u t l l i c k i 【3 2 】证明了 问题砌im 甜iy w ，c ，的基于w s p t 的启发式算法的性能比也为所。h 0 0 9 e v e e n 和k a w a g u c h i 3 3 】证明了问题f 20y c ，的基于s p t 的启发式算法的性能比为 2 ( 口+ 纠，口为所有2 ”个工序中最小的处理时间，为所有2 行个工序中最大 的处理时间；赵传立、张庆灵和唐恒永 3 4 】证明了如果作业权重具有一致权因子， 那么问题f 20 y w ，c ，的基于w s p t 的启发式算法的性能比也为2 纠( 口+ 动。 f i s h k i ne ta 1 【3 5 】提供了问题咖i 叩，oi w ，c f 的p t a s 算法( 为常数) 。 1 4 2 批调度问题 问题1 ( o o ) i | 、1 ( 1 ) 0c 眦是平凡问题。而对于b ( 2 曰 刀) 的问题 1 ( b ) 0 ，b m c k e re ta 1 3 6 】给出了s p t 批最优调度算法，时间复杂性为 m i n d ( 疗l o g 行) ，d ( 拧2 肛) 。对于问题l ( b ) i ，：，p ，= p i c 眦，i l ( u m 和g i m p l e 【3 7 】给出 了求最优解的有效算法。对于问题l ( ) i ，l c o ，虽然l e e 和u z s o y 【3 8 】提供了时 间为d ( 胛2 ) 的求最优解算法，但p o o n 和z h 锄g 3 9 】给出了时间为d ( 疗l o g 刀) 的求最 优解算法。对于强n p 难的问题1 ( b ) i ，：，ic 僦，b r u c k e r e ta l 【3 6 】，l e e 和u z s o y 【3 8 】对 该问题的几种特殊情况分别给出了多项式时间和伪多项式时间的算法；而l i u 和 y u 【4 0 】证明了问题l ( b ) loi 的贪心启发式算法性能比为2 ，并且证明了问题 1 ( 2 ) io o ，r ) i 是n p 难的，给出了问题l ( 2 ) ioic 螂在不同到达时间数目固 定情况下的伪多项式时间算法。 对于问题1 ( 1 l i y c ，b m c k e re ta 1 【3 6 】给出了后向动态规划( b a c i ( w a r d d y n 锄i cp r o g m m m i n g ) 算法，时间复杂性为d ( 刀l o g ”) ：而对于的问题 l ( b c ，( 2 召 刀) ，他们也给出了后向动态规划算法，时间复杂性为 d f 行口【肛1 ) 。当只有所( m 6 = o 8 2 ，s 1 的平均负载均衡 率为( o 8 1 + l + o 4 1 + 1 + 1 ) 5 = o 8 4 4 ，大于s 2的平均负载均衡率 1 2 第2 章差异工件批调度问题的启发式算法 ( o 4 0 + 1 + 0 5 6 + 1 + l + 1 ) 6 = o 8 2 6 ；但s l 的最大完工时间为6 4 ，大于s 2 的最大完 工时间6 2 ，即方案s l 劣于方案s 2 如何更好地综合利用批的利用率和批的负载 均衡率来衡量一个批的好坏以及一个调度方案的优劣，有待进一步研究。 2 3 启发式算法概念 启发式算法( h e u r i s t i ca l g o r i t l 姗) 是凭直观和经验给出的算法，它不考虑所 得解与最优解的偏离程度。其描述性定义如下【n 】： 定义2 3 ：基于直观或经验构造的算法，在可接受的花费( 时间、空间) 下，给 出待解组合优化问题的每个实例的一个可行解，该可行解与最优解偏差事先不 一定可以预计。 定义2 4 ：启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保 证该解的可行性与最优性，无法描述该解与最优解的近似程度。 启发式算法的优点：( 1 ) 有可能比简化数学模型解的误差小；( 2 ) 对有些难 题，计算时问可接受；( 3 ) 可用于某些最优化算法( 如分支定界算法) 之中的 估界；( 4 ) 直观易行；( 5 ) 速度较快；( 6 ) 程序简单，易修改。 启发式算法的不足：( 1 ) 不能保证求得全局最优解；( 2 ) 解的精度不稳定， 有时好有时坏；( 3 ) 算法设计与问题、设计者经验、技术有关，缺乏规律性；( 4 ) 不同算法之间难以比较。 启发式算法的分类：( 1 ) 一步算法：如对差异工件单机批调度问题，令每个 工件单独为一批，则得到此问题的一个可行解。( 2 ) 改进算法( 迭代算法) ：如 差异工件单机批调度问题的l p l 下f 算法( 见2 4 1 节) 。( 3 ) 数学规划算法：如动 态规划、分枝定界等算法。 ( 4 ) 解空间松弛法：如拉格朗日松弛、半定松弛等 方法。( 5 ) 现代优化算法：8 0 年代初兴起的一类算法，如禁忌搜索( t a 【b us e a r c h ) 、 模拟退火( s i m u l a t e d 舳n e a l i n g ) 、遗传算法( g e n e t i ca 1 9 0 一t h m s ) 、神经网络( n e u r a i n e t w o r k s ) 、蚂蚁算法( a n t a l g o r i t h m ，群体( 群集) 智能，s w a 眦i n t e i l i g e n c e ) 等。( 6 ) 其他算法：多种启发式算法的集成，如遗传算法加模拟退火的混合算 法等。 1 3 第2 章差异工件批调度问题的启发式算法 2 4 差异工件单机批调度问题的启发式算法 2 4 1 经典调度规则算法 l 、算法l p t f f ( l o n g e s tp r o c e s s i n gt i m e f i 飓tf i t ) 【4 7 1 ： s t e p l ：按工件加工时间非增序排列工件； s t e p 2 ：选择列表中的第一工件，把它放入有足够剩余空间容纳该工件的编 号最小的批中；如果这样的批不存在，则为此工件创建一个新批。重复此过程， 直至所有工件都加入到了批中。 s t e p 3 ：以任意顺序在机器上加工批。 该算法从工件的角度考虑，一方面使工件分成的批数尽可能少，另一方面又 使工时较长的工件尽可能的分在一批中，直观上应该有较好的性能指标。 相对于l i y l 下f 算法，有如下的l p l 几f 算法： 算法l p t l f ( l o n g e s tp r o c e s s i n gt i m e l a s tf i d ： s t e p l ：按工件加工时间非增序排列工件； s t e p 2 ：选择列表中的第一工件，把它放入有足够剩余空间容纳该工件的编 号最大的批中；如果这样的批不存在，则为此工件创建一个新批。重复此过程， 直至所有工件都加入到了批中。 s t 印3 ：以任意顺序在机器上加工批。 该算法从工件的角度考虑，一方面使工件分成的批数尽可能少，另一方面 试图使加工时间接近的工件尽可能的分在批中。 2 、算法l p t b f ( l o n g e s tp r o c e s s i n gt i m e b e s tf i t ) 【5 l l ： s t e p l ：按工件加工时间非增序排列工件； s t e p 2 ：选择列表中的第一工件，把它放入有足够剩余空间容纳该工件且此 剩余空间最小的批中( 如果这样的批有多个，则放入产生最早的那个批中) ；如 果这样的批不存在，则为此工件创建一个新批。重复此过程，直至所有工件都 加入到了批中。 s t e p 3 ：以任意顺序在机器上加工批。 该算法从工件的角度考虑，单从批的利用率方面来对工件安排批次，试图 最小化批数及最小化批总剩余空间。易见，l m f 求得的解的平均批利用率大 于等于由l p t f f 求得的解的平均批利用率。 罩、算法l p t l b ( l 仰g e s tp m c e s s i n gt i m e l a s tb a t c h ) 【5 0 1 ： 1 4 第2 章差异工件批调度问题的启发式算法 s t e p l ：按工件加工时间非增序排列工件； s t e p 2 ：选择列表中的第一工件，将其放入最后一个批中；若放不下，则为 此工件创建一个新批。重复此过程，直至所有工件都加入到了批中： s t e p 3 ：以任意顺序在机器上加工批。 该算法从工件的角度考虑，算法保证了各个批中的工件按加工时间是不跳 跃的连续的，试图使得批的均衡率尽可能大。 4 、算法s k p ( s u c c 皓s i v ek h a p s a c kp m b l e m ) 【5 1 1 ： s t e p l ：按工件加工时间非增序排列工件； s t e p 2 ：选择列表中的第一个工件建立新批，不妨设此工件为五，易知，m 是 当前未调度工件中加工时间的最大值；此时，此新建批可以看出是一个m b 的 矩阵，未调度的工件河以看成是研研的矩阵块，为了求当前批中的其他工件， 需要求解如下一个0 1 背包问题： m a ) ( 乙蝇a j 而j _ - - 一 t s 1 s t x l s b s f j 重复此过程，直至所有工件都安排到了批中。 s t e p 3 ：以任意顺序在机器上加工批。 此算法从批的角度考虑，试图在生成批时，同时考虑工件的加工时间和工件 尺寸，虽然如此，但它把工件的加工时间和工件的尺寸放在了同样的约束地位， 这样可能造成最小加工时间的工件和最大加工时间的工件同一批，致使批的负 载均衡率较大。 5 、其他 记算法f f ( f i r s t f i t ) 为：选择列表中的第一工件，把它放入有足够剩余 空间容纳该工件的编号最小的批中；如果这样的批不存在，则为此工件创建一 个新批。重复此过程，直至所有工件都加入到了批中。 ( 1 ) 算法d e c r - f f ( d e c r e a s i n gs i z e f i r s tf i d 【4 7 】： s t e p l ：按工件尺寸非增序排列工件； s t e p 2 ：运用f f 算法； s t e p 3 ：以任意顺序在机器上加工批。 ( 2 ) 算法s p t f f ( s h o r t e s tp r o c e s s i n gt i m e f f ) 【4 7 】： 1 5 第2 章差异工件批调度问题的启发式算法 s t e p l ；按工件加工时间非减序排列工件： s t e p 2 ：运用f f 算法； s t e p 3 ：以任意顺序在机器上加工批。 ( 3 ) 算法p i a i f f 4 7 】： s t e p l ：按b 非减序排列工件； s t e p 2 ：运用f f 算法； s t e p 3 ：以任意顺序在机器上加工批。 ( 4 ) 算法l p s f f ( l a 唱e s tp r o c e s s i n gt i m e s i z el h t i o f f ) 【5 0 】： s t e p l ：按b a 非增序排列工件； s t e p 2 ：运用f f 算法； s t e p 3 ：以任意顺序在机器上加工批。 2 4 2 基于批剩余率与批均衡率的启发式规则算法 设当前已存在所个批，记厂二例工乍移未安排批) 为当前未安排批的工件集合， 对任意的七 1 ，m ) ，记舻协j + ，且s 乜b ) 表示批七中可以再安排的工 件集合；对任意的f ，定义q = 后i 七 l ，聊) 且( 甄) + 名b ) 表示有足够 剩余空间容纳工件f 的批集合 基于2 2 节中定义的批的利用率和批的负载均衡虑，构造如下的四种u l b ( u t i l i z a t i o nr a t i o 舭dl o a db a l 锄c er a t i o ) 算法。 算法u l b1 ： s t 印1 ：按工件加工时间非增序排列工件，令m = l ，缈。= ； s t e p 2 ：选择列表中的第一工件，设其编号为，若吼= 矽，则令研= 肌+ l ，蛾= 0 ； 否则，把它放入第七批中， 七2 鹏蛔麟u ，) ( 届心) 岛v ，e 西留，= 毋，u ，) 、 7、， 重复此过程，直至所有工件都被安排到了批中。 s t e p 3 ：以任意顺序在机器上加工批。 算法u l b2 ： s t e p l ：按工件加工时间非增序排列工件，令肌= 1 ，缈，= ； s t e p 2 ：选择列表中的第一工件，设其编号为f ，若q = 妒，则令朋= 脚+ 1 ，蛾= 0 ； 否则，把它放入第七批中， 七2 鹕慨霹譬，( 局h ，+ 岛。，e 毋嘶= 锄u ( f ” 。 第2 章差异工件批调度问题的启发式算法 重复此过程，直至所有工件都被安排到了批中。 s t 印3 ：以任意顺序在机器上加工批。 上述两个算法从工件的角度考虑，一方面使工件分成的批数尽可能少，另一 方面试图使加工时间相近的工件安排在一批中。 算法u l b 3 ： s t e p l ：以任意序排列工件；令七= l ，缈i = 矽； s t e p 2 ：若忙妒，则令七= 七+ l ，甄= ；否则，选择工件，加入批七， 2 鹕m ，糍0 届( 叫磊 重复此过程，直至所有工件都被安排到了批中。 s t 印3 ：以任意顺序在机器上加工批。 算法u l b4 ： s t 印l ：以任意序排列工件；令忌= l ，野i = ； s t 印2 ：若忙咖，则令七= 七+ l ，孵t = ；否则，选择工衔加入批七， _ ，2 鹕m ，鬈鬈 ( 届i i r + 伤匹f ) 。 。i “l 舄r = 毽k 幔f l 、l 2 。j 重复此过程，直至所有工件都被安排到了批中。 s t e p 3 ：以任意顺序在机器上加工批。 一 上