（计算机应用技术专业论文）启发式求解大规模流水调度问题.pdf

竺兰兰矍三奎兰三兰竺：茎竺丝兰 启发式求解大规模流水调度问题 摘要 大规模f l o ws h o p 调度是一个重要的制造加工系统中的核心问题，广泛 应用于工业环境中。大规模流水调度足很多实际流水线生产调度问题的简化 模型，也是一类典型的n p 完全问题，已被证明在多项式时间内得不到最优 值。该问题也是生产管理中的核心问题，好的求解方法可以促进企业提高生 产率。因此，对于该问题的研究从理论到实践都有重要意义。近年来，对于 流水调度问题的求解主要有启发式算法和元启发式算法，但各有其不足之 处：元启发式方法的运行时间长，可获得较好的解，但其解不稳定：启发式 方法可在较短的时间内得到鲁棒性较强的解，但是极少获得较优的解。为了 更好地解决大规模流水调度问题，提出两个相应的启发式算法，从实时性和 优解性两个方面与现有的算法进行比较，大量试验结果衷明该方法能有效求 解所考虑的大规模流水调度问题。 首先，针对以总完工时间为优化目标的大规模流水作业调度问题，提出 基于局部插入和全局插入的双插入启发式算法d i h 。i ) i h 算法与目前求解流水 调度问题最好的启发算法r z 、w y 、凡在1 5 0 0 个实例上进行比较。试验表明， d i h 算法具有最好的性能，并且能够满足大规模调度对于实时性和优解性的 要求。 其次，提出复合启发式算法c d i h 求解最优化总完工时间的大规模流水调 度问题。在c d i h 算法中，将d i h 算法的调度结果通过全局插入和工件交换操 作进行二次改进。通过4 0 0 0 个不同规模实例将c d i h 算法与目前最好的复合 启发式算法i h 7 、f l i h 7 在a r p d 、s t d 、o p t 和计算时间等参数方面进行比 较，试验结果表明：在最好调度的获取能力、所得调度的平均质量及所得调 度的稳定性方面，c d i h 算法均是最优的。c d i h 能够更有效地解决以总完工 时间最小为目标的f l o ws h o p 调度问题。 关键词大规模流水调度：启发式算法；总完工时问 哈尔滨理工大学工学硕士学位论文 h e u s t i c sf o rl a r g e s c a l ef l o ws h o p s c h e d u l i n gp r o b l e m s a b s t r a c t s l a r g e * s c a l ef l o ws h o ps c h e d u l i n g i sa ni m p o r t a n tm a n u f a c t u r i n gs y s t e m w i d e l ye x i s t i n gi ni n d u s t r i a le n v i r o n m e n t s l a r g e s c a l ef l o ws h o ps c h e d u l i n gi s t h es i m p l i f i e dm o d e lo fm a n ya c t u a lp r o d u c t i o n s a n df l o ws h o ps c h e d u l i n gi sa t y p i c a l l yn p - c o m p l e t ep r o b l e m ，w h i c hm e a n st h a ti ti si m p o s s i b l et of i n dt h e g l o b a lo p t i m u mi np o l y n o m i a lc o m p l e x i t y i ti so n eo ft h ek e yp r o b l e m si nt h e p r o d u c t i o nm a n a g e m e n t g o o da l g o r i t h m s f o rt h i s p r o b l e m c a l l p r o m o t e p r o d u c t i v i t y o fe n t e r p r i s e s s ot h e s t u d yo fl a r g e s c a l e f l o ws h o ps c h e d u l i n g p l a y sa ni m p o r t a n tr o l eo nt h e o r ya n dp r a c t i c e i nr e c e n ty e a r s ，m e t a - h e u r i s t i c s a n dh e u r i s t i c sa r et w ok i n d so fa l g o r i t h mf o rf l o ws h o pp r o b l e m h o w e v e r , t h e y a r ed i f f e r e n ti nc p u t i m ea n dp e r f o r m a n c e m e t a h e u r i s t i c sc a na l w a y so b t a i n b e t t e rs o l u t i o n st h a nh e u r i s t i c sb u tt h e yn e e dm u c hm o r ec p u t i m e s a sw e l l ， r o b u s t n e s so fh e u r i s t i c si sg o o db u to p t i m u mc a l ls e l d o mb eo b t a i n e d t bb e t t e r s o l v el a r g e s c a l ep r o b l e m ，t w oh e u r i s t i c sa r ep r o p o s e d t h ep r o p o s e dh e u r i s t i c s a r ec o m p a r e dw i t ht h ee x i s t i n go n e si nb o t he f f i c i e n c ya n de f f e c t i v e n e s s t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e dh e u r i s t i c sc a i ls o l v et h ec o n s i d e r e d p r o b l e m se f f e c t i v e l ya n de f f i c i e n t l y f i r s t ，an e w h e u r i s t i cd i h ( d o u b l ei n s e r t i n gh e u r i s t i c ) i sd e s i g n e df o rl a r g e s c a l ef l o w s h o ps c h e d u l i n gp r o b l e m s t om i n i r r l i z et o t a l f l o w t i m e ，w h i c h i n t e g r a t e sl o c a l i n s e r t i o no fn e ha n dg l o b a l i n s e r t i o no fr zr e s p e c t i v e l y 。d i h i s c o m p a r e dw i t ht h r e eb e s te x i s t i n gh e u r i s t i c s ，r z ，w ya n df l ，o n15 0 0 r a n d o m l yg e n e r a t e di n s t a n c e s e x p e r i m e n tr e s u l t s s h o wt h a td i hi s v e r y e f f e c t i v ea n de f f i c i e n tf o rf l o ws h o p sw i t ht o t a lf l o w t i m em i n i m i z a t i o n s e c o n d ，t h ec o m p o s i t eh e u r i s t i cc d i hi sp r o p o s e df o rl a r g e s c a l ef l o ws h o p s c h e d u l i n gp r o b l e m sw i t ht o t a lf l o w t i m em i n i m i z a t i o n i nc d i h ，t h es o l u t i o no f d i hi si m p r o v e db yr z i n s e r t i o na n dp a i r - w i s ee x c h a n g e c d i hi sc o m p a r e d a g a i n s t0 t h e rt h r e eb e s te x i s t i n gc o m p o s i t eh e u r i s t i ca l g o r i t h m si h 7 。f l i h 7o n i i 墼垒堡矍三查兰三兰璧耋兰堡篁兰 4 0 0 0r a n d o m l yg e n e r a t e di n s t a n c e si n a r p d ( a v e r a g er e l a t i v ep e r c e n t a g e d e v i a t i o n ) ，s t d ( s t a n d a r dd e v i a t i o n ) ，o p t ( n u m b e ro fo p t i m u ms o l u t i o n s o b t a i n e df o rag i v e ns i z eo f p r o b l e m s ) a n dc t ( c p ut i m e ) c o m p u t a t i o n a lr e s u l t s s h o wt h a tc d i hn e e d sl i a l em o r ec p ut i m et h a ni h 7a n df l i h 7 b u ti ti s 也e b e s ti na r p d ，s t da n do p ta m o n g 侥ec o m p a r e da l g o r i t h m s s oc d l hi sa n e f f e c t i v ec o m p o s i t eh e u r i s t i ca l g o r i t h mf o rt o t a lf l o w t i m em i n i m i z a t i o nl a r g e s c a l ef l o ws h o ps c h e d u l i n gp r o b l e m s k e y w o r d sl a r g e s c a l ef l o ws h o ps c h e d u l i n g ；h e u r i s t i c sm e t h o d ；t o t a lf l o w t i m e 1 1 1 一 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文启发式求解太规模流水调度问 题，怒本人褒导爆撂霹下，谯哈零滨理工大学攻读硕士学位期闯独立遴霉磅突 工作所取得的成果。据本人所知，论文中除已滤明部分外不包禽他人已发表或撰 写遘懿磅究成莱。对本文磅究盖终骰爨贡簸戆个天帮繁俸，稳积在交串l ；乏骥确努 式注明。本声明的法律结果将宪全由本人承担。 作者镰名：高祥 日期：2 甜年多月阳 哈尔滨理工大学硕士学位论文使用授权书 启发式求解大规模流水调度问题系本人在哈尔滨理工大学攻读硕士学缀 期间农导师指撂下完成的硕士攀位论义。本论文的研究成果归嗡尔滨理工大学艇 有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工大 学关予僳存、馕趸学簸论文熬嫂定，弱意学技僳整劳自毒关嚣瞧提交论文和电子 版本，允许论文被查阅和借阅本人授权哈尔演理工大学可以采用影印、缩印或 萁建复裁手段傈存论交，虿瑷公摩论文豹垒帮袋帮分痣容。 本学位论文属于 保密翻，在年簿密后适用授衩书。 不保密口。 ( 请在以上相应方框内打、，) 日期：汐幸序歹月自 日期：如绛岁月，孑日 f r ，髟； 毋 卜 ，蔼参 名 名 煞 箍 者 师 作 导 呛尔溃理t 大学t 学顸+ 学舒论文 1 1 课题背景 第1 章绪论 作业排序问题”1 有着深刻的实际背景，是工农业生产、国防、科研、交通 运输以及各种服务行业中普遍遇到的问题。作业调度问题的研究不仅具有重大 的现实意义，而且具有深远的理论意义。作业调度就是根据产品制造需求合理 分配产品制造资源，进而达到合理利用产品制造资源、提高企业经济效益的目 的。它是产品制造行业中共存的问题，它与c i m s 中的工厂管理、产品制造层 次紧密相关，是c i m s 领域中研究的重要课题。 一般地说，凡是有多个不同项目要完成，就有排序问题的存在“。2 1 。这些问 题的共同特征就是要将不同的任务安排一个执行的顺序和时间，将有限的人 力、物力资源分配给不同的任务，使预定的目标达到最优。由于同一台设备上 可能要加工的零件有多个，一个零件可能有多道工序要到多台设备上去加工， 不同零件的加工工艺路线也可能不相同，而每道工艺的加工时间也可能不相 同，这就使得排序问题非常复杂。一个任务在m 台机器上不同的安排顺序得出 的结果差别较大，怎样安排加工顺序，才能得到最优或近似最优的结果，就是 调度问题；其中，“机器”可以指工厂里的各种机床、维修工人、轮船要停靠 的码头、计算机的中央处理器、存储器、输入和输出单元，即代表“服务 者”；而“任务”则是等待机床加工的各种零件、待修理的机器、即将停靠码 头的轮船、等待处理的程序，即“服务对象”；对于一般的排序问题，“机 器”和。任务”都有多个，调度问题要解决的是确定服务者对服务对象的服务 顺序和时间，使目标函数达到最优。 大规模、复杂约束、多目标的调度问题是目前的研究热点，是接近实际生 产的优化模型。大规模流水调度是其中一类，该问题的研究对实际生产具有重 要意义：对一般的流水调度问题，总完工时间( t o t a lf l o w t i m e ) 最小促使资源 稳定有效地利用、任务的快速传递及在制品库存最小”；而最大完工时间 ( m a k e s p a n ) 最小能减小总的生产周转时间，这些都是目前现代集成制造系统 c i m s 、计算机系统和其他一些信息系统所关心的一些问题。 流水车间作业调度是c i m s 领域中研究的重要课题。同时也是在实际中应 用最广的运筹学分支之一，研究它对于在现有资源条件下提高工作效率和经济 哈尔滨理t 大学t 学碲i 十学世论文 效益有重要作用。理论上已经证明车间调度问题足一个n p 难题，要想用多项 式时间复杂度的算法找到最优解是不可能的。但是，在实际生产中即便一个较 优解也能带来极大的经济效益，所以人们探索了许多途径以寻求最佳近似解， 结果却不令人满意。目前对这些问题的研究主要可以分为两类方法：启发式方 法( h e u d s t i e s ) 和元启发式方法( m e t a - h e u r i s t i e s ，包括遗传算法、模拟退火、 人工神经网络、禁忌搜索和蚁群算法等) 。这两类方法在评价算法性能的两个 标准方面各有优缺点：在最优性( e f f i c i e n c y ) 方面，元启发式算法在总体上优 于启发式算法，但是由于不确定参数的存在使其解的稳定性较差；在有效性 ( e f f e c t i v e n e s s ) 方面，元启发式算法通常较差，其需要的c p u 时间远远多于 多项式复杂度的启发式算法，使得它们很难应用于工程实践，特别是对于大规 模的调度问题。 由于一个好的作业调度方案不仅可以降低生产成本，而且可以提高企业产 品的准时交货能力，从而增强企业的竞争力。所以，本题研究大规模流水车间 调度问题的启发式求解方法，以满足实际工程应用中对于实时性和优解性需 求。 1 2 国内外研究现状及发展 1 2 1 国内外研究现状 调度问题是一个典型的n p 难问题，理论上已经证明要想在多项式复杂度 内对这一类问题找到全局最优解是不可能的。由于调度问题的复杂性，导致不 同的研究者从不同的角度研究某一方面的问题，产生了许多的车间调度问题的 类型和方法，并随着对各类调度问题研究的深入及各种交叉学科的发展，涌现 出许多新的车间调度理论与方法。求解流水调度问题的技术与方法主要分为两 类，一类是近似方法，一类是最优化方法。用近似方法求解作业调度问题时， 它们可以很快得到问题的解，但它们不能保证得到的解为最优。 1 最优求解方法 最优化方法的主要数学工具有线性规划法、动态规划法、拉格朗日乘子 法、分支定界法等。在上述算法中，线性规划法研究与应用较早，它将调度优 化目标和各种约束条件表示为线性关系式或线性不等式。分支定界法在生产调 度领域也是一种常见的精确算法，它的效率与众多因素密切相关，如：搜索树 的空间结构、定界方法和剪枝规则等。如果能合理设计这些因素，可将其用于 哈尔泞理t 大学t 学硕十学位论文 中小规模调度问题精确求解。 2 近优解求解方法 目前对调度问题常用的近优求解方法主要可以分为两类：启发式方法 ( h e u r i s t i c s ) 和元启发式方法( m e t a h e u r i s t i c s ) 。启发式算法足针对一个特定 问题的性质和目标函数，选用或设计有效的调度规则来获取近优解或满意解， 启发式方法主要包括j o h n s o n 算法”1 、p a l m e r 算法”、c d s 算法、g u p t a 算法 “1 、n e h 算法”1 、r z 算法1 、w y 算法1 及f l 算法“”。p a n w a l k e rc ta 1 在前人研 究工作的基础上总结了1 1 3 个调度规则，为求解调度问题近优解的方法做了一 个汇总”。启发式方法减少寻优空间，大大缩短寻优过程，计算量小。但是， 随着调度问题复杂性提高，很多简单调度规则存在对最优解逼近程度的问题； 元启发式方法是以迭代求精法为核心思想的新启发式搜索方法，能克服传统启 发式方法易陷入局部最优的不足，主要包括遗传算法、模拟退火、人工神经网 络、禁忌搜索和蚁群算法等。在最优性( e f f i c i e n c y ) 方面，元启发式算法在总 体上优于启发式算法，在有效性( e f f e c t i v e n e s s ) 方面，元启发式算法通常较 差，使得他们很难应用于工程实践，特别是对于大规模的调度问题。 流水调度问题最早由j o h n s o n ”1 提出一个求解两台机器的最优解求解算法和 三机问题的近似最优求解算法，多年来受到大量的运筹学专家、数学家和企业 管理人员的关注，同时也出现了大量的研究结果。在我国最早由越民义和韩继 业开展这方面的研究工作“”，并取得较多成果；近年来，郑大钟、王凌、唐 立新等采用元启发式算法在这方面也得到了较好结果”“1 。 1 ) 最大完工时间最短的流水调度问题( f m l p r m u l c l ) 最大完工时间最短的流水调度问题是研究得较多的问题。其研究方法主要 分为启发式算法和元启发式算法两类，较典型的启发式算法有基于作业优先级 的p a l m e r 算法”、c d s 算法”、g u p t a 算法”和基于任务插入的n e h 算法，其中 n e h 算法被认为是目前求解该类问题最好的启发式算法，n e h 基于任务插入方 法，在任务插入时，一个末调度的任务被插入到当前方案的每一个可能位置 中，在所产生的调度或部分调度方案中选择最好的作为新的当前方案，开始时 任务按加工时日】升序排列并且将这个序列作为种子序列，将种子序列的第一个 任务作为当前解，其它任务被顺序地取出执行任务插入操作，这样最后的当前 方案就是n e h 的解；另外，n a g a n o o “、k o u l a m a s 2 、s e v a s t j a n o v 。1 、 l o u r e n c m l 、m o c c e l l i n 和p o u r “1 等也分别对这类问题做了研究，并提出了几个 启发式算法，其中n a g a n o l 2 l 】和k o u l a m a s 2 1 所提出的n & m 算法和h f c 算法与 n e h 算法相当，没有太明显的提高，但所提方法为相关问题的研究提供了新的 哈尔滨理t 大学t 学硕十学位论文 研究思路。其借助于生物进化或者一些物理现象的优化过程，人们开始抽象这 些过程并用来求解流水调度这类组合优化问题， 如对f m l p r m u l c 一问题，提出 的元启发式算法有遗传算法1 2 7 2 8 l 、禁忌搜索 2 9 3 0 1 和模拟退火算法【3 “，其中文献 3 0 1 的禁忌搜索算法b f 是目前性能最好的元启发式算法，其结果基本接近文献 3 2 1 给出的上界。 2 ) 总完工时间最短的流水调度问题( f m i p r m u i y c l ) 总完工时间比最大完工时间更为重要“，总完工时间( t o t a lf l o w t i m e ) 最小促使资源稳定有效地利用、任务的快速传递及在制品库存最小。由于以完 工时间最小为目标的流水作业调度问题是n p 完全问题”“，一些研究者考虑了 两台机器的问题，主要集中在隐式枚举技术和启发式技术；对于多台机器的问 题，许多研究者致力于找到一种能够在有限的c p u 时间内取得较优解的启发式 算法，g u p t a o ，r a j e n d r a na n dc h a u d h u r i “，r a j e n d r a n 1 。h o 1 ，r a j e n d r a na n d z i e g l e r 。w o oa n dy i m 1 。f r a m i n a na n dl e i s t e n “”和a l l a h v e r d ia n da i d o w a i s a n 1 等提出了不同的启发式算法。r a j e n d r a n 和c h a u d h u r i 设计了三个启发式算法， 就解的质垦和计算花费而言其提出的算法都要优于g u p t a 、m i y a z a l d 等提出的算 法。r a j e n d m 提出了一个新的启发式方法，其在质量上优于r a j e n d r a n 和 c h a u d h u r i 提出的算法，但是该算法的计算花费也要大于r a j e n d r a n 和c h a u d h u r i 提出的算法。h o 提出了一个迭代的启发式算法，这些迭代过程中使用任务交换 操作来取得局部最优解，并通过任务插入来对解进行改进，这种方法的性能明 显优于上面提到的方法，但其缺点是需要更多的c p u 时耳j ”1 ，实际上这种方 法更像足一种局部搜索技术如模拟退火或禁忌搜索，此外该算法不适用于大规 模问题和对于时间性要求较高的环境，因此在启发式算法关于完工时间性能的 比较时通常不考虑该算法。r a j e n d r a n 和z i e g l c r 提出一个启发式算法r z ，其由 两个阶段构成：在第一个阶段，种子序列通过将机器分组的优先权规则来产 生，该规则与最小加权总加工时间规则相似；第二个阶段则是调度序列的构 造。w a n g 等提出了两个启发式算法l i t ( 最小空闲时间) 和s p d ( 最小等待 时间) ，两个启发式算法的核心思想是使机器空闲时间最小，因为机器的空闶 时间等价于任务的完工时间。他们提出的算法没有与上面提到的方法进行比 较。a l l a h v e r d ia n da l d o w a i s a n ”提出了一系列的启发式方法来求解完工时间最 小问题。这些方法某种程度上说足合成式启发式方法1 ，也就足说：这些方法 使用一种或几种启发式方法( 如n e h 、w y 、r z ) 来产生初始解，然后对其进 行改进。在其提出的启发式方法中性能最好的是i h 7 ，它明显优于w y 和r z 同 时也优于文献 4 2 1 提到的其它启发式方法。i h 7 由三个阶段构成，在第一个阶段 哈尔滨理二r 大学t 学硕卜学位论文 中，对于要解决的问题用w y 来求解其初始解；第二个阶段，将该初始解作为 r z 算法的种子序列；最后，将第二个阶段得到的解用任务交换操作来进行改 进直到其达到局部最优。n e h ”1 似乎是对于最大完工时日j 最小问题最好的启发 式算法，但它并不是对于总，平均完工时间最小问题最好的启发式算法“。 对于总平均完工时间最小的问题，目前最好的启发式算法是f l 、w y 和r z 。 f l 与n e h 相似，但是每一次任务插入完后紧接着任务交换操作来提高每一次迭 代的当前方案的质量。任务交换操作是将当前方案中每一对任务的位置进行交 换以产生新的调度或部分调度。如果当前方案比新产生的调度或部分调度中最 好的方案差则用该方案来代替当前方案。w y 同样也是源f l n e h ，但它不需要 像n e h 那样要预先确定种子序列，而且在一次任务插入操作时对所有未调度的 任务都要进行插入操作。文献“1 中对于w y 和r z 进行了比较，发现对于规模 比较小的实例r z 要优于w y ，但随着任务数的增加w y 的相对性能最终超过 r z 。f m m i n a n 和l e i s t e n 1 进行的模拟实验结果显示f l 算法的性能在大多数随机 产生的实例中优于w y 和r z ，f l 和w y 的时间复杂性为o ( m r 4 ) ，i 湿的复杂性 为o ( m n 3 ) 。然而对于每一个实例f l 比w y 需要更多的c p u 时间。此外，效率较 高的复合启发式算法f l i h 7 “”也是基于n e h 、r z 和任务交换操作( p w e ) ， 即它们也是基于任务插入操作和任务交换操作。在这些混合式启发式算法中就 解的质量而言 f l - i f l 7 似乎是最好的，但_ f l - i h 7 是需要消费更多的c p u 时间。 对于最大完工时问和总平均完工时间，这样的两目标问题，f r a m i n a n , l e i s t e na n dr u i z - u s a n o 1 设计了两个加权启发式算法f l r ( p r i o r ) 和f l r ( p o s t ) ， 以便为制造者提供一个决策方案。 1 2 2 调度问题的特点及发展趋势 调度问题具有以下几个特点： 1 复杂性：由于生产车间中工件、机器、缓存及搬运系统之自j 相互影 响，相互作用、每个作业又要考虑它的加工时间、操作顺序、交货期等，因而 相当复杂。调度问题是在等式或不等式约束下优化性能指标，在计算量上往往 是n p 完全问题，即随着问题规模的增大，对于求解最优化的计算量呈指数 长，使得一些常规的最优化方法往往无能为力。 2 动态随机性：在实际的生产调度系统中存在很多随机的和不确定的因 素，比如作业到达时间的不确定性、作业的加工时间也有一定的随机性，而且 生产系统中常出现一些突发偶然事件，如设备的损坏修复、作业交货期的改 变、紧急定单等。 3 多目标性：实际的计划调度往往是多目杯的，并且这些目标自j 可能发 生冲突。生产调度的性能指标可以是成本最低、库存费最少、生产周期最短、 生产切换最少、设备利用率最高、最短的延迟，最小的提前期或者拖期惩罚、 三废最少等。这种多目标性导致调度的复杂性和计算量急剧增加。 4 多约束性：生产车间中资源的数量、缓存的数量、工件的加工时间和 加工顺序都是约束。此外还有一些人为的约束，如要求各机器上的负荷平衡等 等。 今后调度问题的研究应向两个方向发展： 1 集成化：探索车间计划与调度的集成，调度层把车间状态不断地反馈 到计划层，计划层根据车间状态制订新的计划或更改原来的计划；计划层再把 变化了的计划下达到设计层，调度层根据变化了的计划调整生产。 2 动态化：研究车间生产的动态特性，探讨车间状态的变化规律，找到 更能反映车间状态变化的调度方法。在加工过程遇至q 扰动和故障时，调度方法 能根据系统的状态修改原定的加工顺序和调度系统的所有资源，使系统持续、 高效地运行。 总之，随着调度研究的深入，调度算法必然会进一步与生产实践相结合， 向着集成化、动态化、高效化、智能化、实用化的方向发展。 1 2 3 研究中存在的问题 虽然对调度问题的研究已有几十年的历史，但至今尚未形成一套系统的方 法和理论，理论研究与实际应用之间还存在着很大差距。尤其随着j i t ( j u s t - m n m e ) 思想的广泛采用，e 厂r ( e a r l i n e s s t a r d i n e s s ) 调度问题，即使得工件 尽量按交货期完成，变得越来越突出。实际应用中的调度方法能够响应系统的 动态变化，但不能保证得到好的调度：一些理论上的最优化方法能提供最优调 度，但由于其计算的复杂性，并且忽略了很多实际因素，离实际运用还有较大 距离。基于最优化的方法，诸如动态规划算法与分枝定界算法等等，由于其大 多数足建立在对可能调度的部分枚举上，因此只能解决小规模的调度问题。 调度理论、方法与应用的研究是一项非常艰巨的工作，目前人们还在进行 各种各样的探索性研究工作。 哈尔泞弹t 大学t 学硕十学估诒史 1 3 研究方法 启发式算法本质是将所有任务( 或部分) 的一个全排列视为多维空间中的 一个点，并用邻域搜索技术搜索该结点的一个邻域，取其中最好调度作为新结 点继续搜索，直到所有任务搜索完毕或邻域中没有更优结点为止。 l 对现有性能较好的启发式算法如：n e h ，r z ，w y ，f l 等通过实验进 行分析，对其中出现的局部搜索方法进行比较，以便总结出有效的局部搜索方 法： 2 启发式算法求解过程中大量的调度方案部分调度方案被产生，个体之 间具有继承性，可以利用这一特性来降低算法的时间复杂性； 3 。启发式算法一般包括种子序列的产生和对调度的改进两个阶段。可以 利用l 中得到的高效的局部搜索方法( 及其改进或组合) 进行优化，以提高解 的质量，同时考虑2 中的特性来降低时间复杂性，将二者结合起来以得到有效 的启发式算法，使其能在较短时间内找到较好的解以满足实际工程应用对于实 时性和优解性的要求。 1 4 评价启发式算法的性能指标 启发式方法是一种获得合理解的直觉方法。当n p 完全类问题发现之后， 对启发式方法的研究成为排序问题的一个重要方向。对于一些问题，我们没有 找到分析求解方法；对另一些问题，分析解根本就不存在。对这些问题只有用 启发式算法。由于启发式算法得到的不是最优解，而足近优解，要衡量启发式 算法的好坏首先要确定衡量标准。 评价启发式算法的性能指标：相对于最好解的平均相对百分比偏差 ( a r p d ) 、标准偏差( s t d ) 、对于给定问题最好解的取得次数( o p t ) 、c p u 时间 ( c d 。a r p d 表明一个启发式算法所得解的平均质量。s t d 表明启发式算法所 得解与平均解的接近程度。最好解是由进行比较的启发式算法所得最优解。启 发式算法h 的a r p d 和s t d 的计算见公式i - h r上 j a r p d = ( ，b e s t t 行d ”q 一1 ) n 1 0 0 ，”1o ( i - i ) i s 加= 专喜 c f n , b e s t _ k n o w n i - 1 ) x 1 0 0 - a r p d 2 2 其中n 为对于给定任务数与机器数组合运行实例的个数，本文中 ，均为 1 0 0 。昂，表示启发式算法对于给定组合中第i 实例所取得调度的总完工时 间，b e s t _ k n o w n ，为对于第f 实例进行比较的启发式算法所得调度总完工时间的 最小值。 1 5 课题来源 本课题受到以下课题的资助： 1 国家自然科学基金项目：基于目标增量的大规模无等待调度复合启 发式算法( 6 0 5 0 4 0 2 9 ) ： 2 黑龙江省自然科学基会项目： 研究( f 0 2 0 7 ) ； 3 国家自然科学基金项目： ( 9 0 4 1 2 0 1 4 ) 。 单件小批生产的多级供应链计划与调度 以网络为基础的科学活动环境研究 啥尔渍理t 大学 学碜卜学能论文 2 1 引言 第2 章流水作业调度的理论与方法 大规模流水调度问题是一类机器调度问题，广泛应用于计算机系统、运输 调度和生产管理等领域。在流水调度排序中，任务均依次在机器( 处理机、站 台、码头或者机床等) 上加工，如果任务在各台机器上的加工顺序也相同，则 称为同顺序流水调度问题或排列排序流水调度问题。总完工时间( t o t a l f l o w t i m e ) 最短的同顺序流水调度( f m l 删l c 衄) 是研究得较多的问题， 其研究方法主要分为启发式算法和元启发式算法两类，其中启发式算法主要有 p a l m e r 算法”1 、g u p t a 算法”1 ，c d s 算法、r z 算法1 、w y 算法1 、f l 算法“” 和i n s e r t i o n 算法1 等，而元启发式算法主要有遗传算法“”“、禁忌搜索“和 模拟退火算法”。通常启发式算法的计算量相对较小但只能求得近优解，而元 启发式算法能得到更好的解，但却需要较大的计算量，且其计算时间随着问题 规模的扩大增长得很快。不同规模的流水调度问题对时间和性能两方面有不同 的要求，如果实时性要求较高，则采用性能较好的启发式算法，否则可以采用 运算时间较长的元启发式算法。实际应用中的大规模流水调度问题对时间和性 能都有较高的要求，元启发式算法的计算时间随着问题规模增加增长得太快从 而很难满足实际需求，所以处理这类问题应该采用启发式算法；同时启发式算 法的性能也需尽可能提高，因为对于大规模问题而言即便f l o w t i m e 提高不大也 能带来较大的效益。 2 2 流水作业调度概述 2 2 1 流水作业调度问题的目标 流水作业调度的目标是对企业资源进行优化配置，提高企业的经济效益。 具体在评价调度方案好坏时，优化目标的确定可以根据影响企业成本费用的主 要因素来确定，调度问题一般采用下列目标函数值最小作为优化目标。 1 全部产品生产所需要的最大时间或生产周期( m a k e s p a n ) ； 2 平均完工时间( m e a nf l o wt i m e ) ，是指一个产品从原料投入到产品输出 ：兰至二奎茎：至三兰竺丝兰 整个生产过程的时间： 3 总完工时间( f l o w t i m e ) ，在数值上等于所有产品在最后一台设备上完工 时间的总和； 4 平均的进度延迟时间，进度延迟时f a j ( t a r d i n e s s ) 是指一个产品实际发运 时间与产品交货期限之间的正偏差； 5 产品成本。 在研究文献中采用的目标函数是以最大完工时问、总平均完工时间居 多。此外，一个好的调度方案，一般应能做到： 1 ) 均衡生产； 2 ) 在制品库存量少； 3 ) 操作人员的等待时间或空闲时间少： 4 ) 准时交货； 5 ) 准备时间短和准备费用少； 6 ) 完成产品的总需求时间短等。 因此，流水作业调度问题一般属于多目标问题，对于多目标问题的求解， 最常用的办法是，先设置各个目标的权重，然后通过对各个目标加权，将多目 标问题转化为单目标问题。在转化过程中，其关键是确定各个目标的权重，一 般可采用号家调查法来获得。本文中使用的指标是总完工时间( f l o w t i m e ) 。 2 2 2 流水作业调度问题的类型 流水作业调度( f l o ws h o ps c h e d u l i n g ) 问题足指r 个工件在小台机器上加 工，每个工件按同一顺序通过m 台机器( 即每个工件具有相同的工艺路线) ，显 然，对不同的机器、任务、目标有不同的分类方法。 1 若栉个工件在每台机器上的加工顺序是相同的，就是同顺序流水作业 问题( p e r m u t a t i o nf l o ws h o ps c h e d u l i n g ) 。同顺序流水作业问题在生产中有广泛 的实际应用背景，无论是成组加工，还是多品种混流生产，都会碰到这一问 题： 2 如任务在加工过程中不能等待则称之为无等待流水作业调度问题( n o w a i tf l o ws h o p ) 。即任务一旦开始加工，必须在每台机器问连续地进行，一 直到加工完成( 如轧钢、塑料加工、化工和食品加工等都具有这种特性) ： 3 按照目标函数可以分为：单目标问题、双目标问题和多目标问题，通 常研究的足单目标问题； 哈尔滨理t 大学丁学硕+ 学位论文 4 机器数m = l 时是一类特殊问题，称之为单机问题。 对这些问题关系总结如图2 1 所示： 图2 - l 流水调度分类关系 f i g u r e2 - lt h er e l a t i o n s h i po f f l o ws h o ps c h e d u l i n g 2 2 3 同顺序流水作业问题的一般描述 有斥个任务m 台机器的同顺序流水调度问题可以描述为：每个任务有完全 相同的工艺路线，每一台机器上任务加工的先后】顿序也完全相同，每个任务的 加工时间足确定的。不考虑复杂情况，假设每种机床只有一台，并且在有任务 未加工完时，后续任务不允许抢先占用机器。优化目标是求出这一个任务的一 个全排列，使其总完工时间最小。总完工时间是所有任务完工时间之和，设 c ，表示任务i 在机器j 上的完工时间，为任务i 在机器_ ，上的加工时间，f 为 总完工时间，则f 的计算方法如公式2 1 下： f = 0 ；c o ，= q 2 ，qomax(cj ) + ，( f 2 l ，珥，2 l ，嘲 ( 2 1 ) h o f = 同顺序f l o ws h o p 排序问题满足以下约束条件： 1 一个任务不能同时在不同的机器上加工。尽管一个任务有时可能包括 多个零件，也不能将其分成几部分，同时在几台不同的机器上加工； 2 对所有任务来说，在加工过程中采取平行移动方式。即当上一道工序 完工后，立即送下道工序加工； 3 不允许中断。只要一个任务在某个工序上歼始加工，必须一直进行到 哈尔泞理t 大学 学碜卜学位论文 该工序完工，不允许中途停下来，插入其它任务； 4 每道工序只在一台机器上完成，每台机器只完成一道工序。工序都不 是有优先权的； 5 任务数，l 、机器数m 、加工时间，已知，且加工时间与加工顺序无 关，一组共行个任务在肌台机器上加工，所有任务可以在零时刻开始加工。机 器的调整时间包括在加工时间之内： 6 允许任务在工序之问等待，允许机器在任务未到达时闲置； 7 任务加工技术上的约束事先给定； 8 每台机器同时只能加工一个任务： 9 所有任务在各台机器上的加工顺序相同。 2 2 4 调度问题求解 调度问题是一个典型的n p 难问题，理论上已经证明要想在多项式复杂度 内对这一类问题找到全局最优解是不可能的。由于调度问题的复杂性，导致不 同的研究者从不同的角度研究该问题，产生了许多调度方法，并随着对调度问 题研究的深入及各交叉学科的发展，涌现出了许多新的调度理论与方法。 由于以完工时间最小化为目标的流水作业调度问题是n p 完全问题，因此 在多项式时间内找到最优调度非常困难。元启发式方法( m e t a - h e u r i s t i c s ) 和启发 式方法( h e u r i s t i c s ) 足解决流水作业调度问题的两类有效方法。 2 3 流水调度的元启发式方法 在求解流水作业调度问题时，元启发式方法通常可获得优于启发式方法的 调度结果。元启发式方法是以迭代求精法为核心思想的新启发式搜索方法，能 克服传统启发式方法易陷入局部最优的不足。比较著名的元启发式算法有：遗 传算法、模拟退火、禁忌搜索。 2 3 1 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，简称c a ) 是由j h o l l a n d 于1 9 7 5 年受生物进 化论的启发而提出的。g a 是基于“适者生存”的一种高度并行、随机和自适 应的优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色 体”群不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境” 哈尔滓理t 大学_ 学硕十学位论叟 的个体，从而求得问题的最优解或满意解。g a 是一种通用的优化算法，其编 码技术和遗传操作比较简单，优化不受限制条件的约束，而其两个最显著的特 点则是隐含并行性和全局空间搜索。但g a 在解决流水调度问题时也产生的计 算速度较慢和过早收敛的问题，为了克服g a 的几点不足，人们对g a 进行了 大量的改进。 2 3 2 模拟退火法 模拟退火算法( s i m u l a t e da n n e a l i n g ，简称s a ) “”的思想最早由m e t r o p o l i s 等 ( 1 9 5 3 ) 提出的，1 9 8 3 年k i r k p a t r i c k 等将其用于组合优化。s a 算法是基于 m e n t ec a r l o 迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体 物质