（管理科学与工程专业论文）求解一类订单调度问题的遗传算法研究.pdf

硕士论文求解一类订单调度问题的遗传算法研究 摘要 订单调度问题可以简单描述为：每个订单包括k ( k 肌) 种不同的作业，每台机器能 且只能加工某一特定的作业，每个订单的作业必须连续加工直至完成，每个订单的完成 时间是订单中所有作业的最大完成时间。所以，订单调度研究的是一组作业的整体完工 情况。因为订单调度问题类型众多，模型复杂，并且大部分被证明为n p h a r d 难题，因 此寻找多项式时间最优解是不可能的。国内外众多学者尝试发展启发式算法求解订单调 度问题，可以求得较优解，而遗传算法作为一种人工智能优化算法，具有自适应性、并 行性和全局优化的特点，所以本文尝试将遗传算法应用于一类订单调度模型，研究了专 门机环境下以最小化总( 加权) 完工时间优化目标的订单调度模型，并将其与启发式算法 进行性能比较。 文章首先详细地描述了订单调度问题，建立了总完工时间和总加权完工时间情况下 订单调度问题的数学模型；然后针对这两个数学模型的特点，完成了遗传算法的编码设 计、适应度函数设计、遗传算子参数的优选、遗传因子的基因操作等，并运用m a t l a b 强大的数值计算能力和库函数编写优化程序；接下来介绍了这两个模型的五个启发式规 则；之后采用数值仿真实验的方法，将遗传算法与启发式规则的求解结果进行比较研究， 在这个过程中考虑了不同订单数量和机器数量的情况；最后的研究结果表明，遗传算法 与启发式规则相比更为有效，适用于订单调度模型，但仍存在一些不足，值得进一步研 究。论文最后对遗传算法在订单调度中的应用前景进行了展望。 关键词：订单调度，总( 加权) 完工时间，启发式规则，遗传算法 a b s t r a c t 硕士论文 a b s t r a c t o r d e rs c h e d u l i n gp r o b l e mc a l lb es i m p l yd e s c r i b e da s e a c ho r d e ri n c l u d e sd i f f e r e n t t y p e so f j o b s ，e a c hm a c h i n ec a l lo n l yp r o c e s sap a r t i c u l a rj o b ，a n dt h ej o bo fe a c ho r d e rm u s t b eac o n t i n u o u sp r o c e s su n t i lt h ec o m p l e t i o no ft h eo r d e r , t h eo r d e rc o m p l e t i o nt i m ei st h e m a x i m u mc o m p l e t i o nt i m eo fa l lj o b s o r d e rs c h e d u l i n gi st os t u d yt h ew h o l ec o m p l e t i o n s i t u a t i o no fag r o u po f j o b si na no r d e r m a n ys c h o l a r sh a v ea t t e m p t e dt od e v e l o ph e u r i s t i c a l g o r i t h mf o ro r d e rs c h e d u l i n gp r o b l e m ，a n dm e yc a l la c h i e v eo p t i m u ms o l u t i o n ，w h i l et h e g e n e t i ca l g o r i t h ma sa na r t i f i c i a li n t e l l i g e n c ea l g o r i t h m ，w i t ha d a p t i v e , p a r a l l e la n dg l o b a l o p t i m i z a t i o nc h a r a c t e r i s t i c s ，t h i sp a p e ra p p l i e dg e n e t i ca l g o r i t h mt ot h e s et w ot y p e so fo r d e r s t os o l v et h es c h e d u l i n gm o d e li naf u l l yd e d i c a t e de n v i r o n m e n tt om i n i m i z et h et o t a l c o m p l e t i o nt i m ea n dm i n i m i z et h et o t a lw e i g h t e dc o m p l e t i o nt i m e t h ea r t i c l ef i r s td e s c r i b e si nd e t a i lt h eo r d e rs c h e d u l i n gp r o b l e m , e s t a b l i s ho r d e r s c h e d u l i n gm a t h e m a t i c a lm o d e lf o rt h e s et w oc h a r a c t e r i s t i c so ft h et o t a lc o m p l e t i o nt i m ea n d t o t a lw e i g h t e dc o m p l e t i o nt i m e a n dc o m p l e t e dt h ec o d i n gd e s i g no fg e n e t i ca l g o r i t h m ， f i t n e s sf u n c t i o nd e s i g n , o p t i m i z a t i o nc h o i c eo fg e n e t i co p e r a t o rp a r a m e t e r s ，g e n e t i cf a c t o r s s u c h 嬲g e n e t i cm a n i p u l a t i o n , a n du s et h ep o w e r f u lm a t l a bn u m e r i c a lc o m p u t i n ga n dl i b r a r y f u n c t i o n sw r i t eo p t i m i z a t i o np r o g r a m ；t h e nh e u r i s t i cr u l e so no r d e rs c h e d u l i n ga r ei n 仃o d u c e d ， d e t a i l e ds c h e d u l i n gp r i n c i p l ef o re a c hh e u r i s t i ca n dr e l a t e de x a m p l e sa leg i v e n ；a f t e r n u m e r i c a ls i m u l a t i o n , ac o m p a r a t i v ei ss t u d i e db e t w e e ng e n e t i ca l g o r i t h ma n dh e u r i s t i cr u l e s t oc o n s i d e rs i t u a t i o no fd i f f e r e n tn u m b e ro fo r d e r sa n dm a c h i n e s ；t h ef i n a lr e s u l t ss h o wt h a t g e n e t i ca l g o r i t h mi sm o r ee f f e c t i v ec o m p a r e dw i t ht h eh e u r i s t i cr u l e sf o rt h et w oo r d e r s c h e d u l i n gm o d e l s ，b u tt h e r ea r es t i l ls o m ed e f i c i e n c i e s ，w h i c hi sw o r t hf u r t h e rs t u d y f i n a l l y g e n e t i ca l g o r i t h mi no r d e rs c h e d u l i n gp r o s p e c t k e y w o r d s ：o r d e rs c h e d u l i n g ，t o t a l ( w e i g h t e d ) c o m p l e t i o nt u n e ，g e n e t i ca l g o r i t h m ， h e u r i s t i cr u l 锵 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明 确的说明。 研究生签名：盔! 艺二廷矽年占月f 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文， 按保密的有关规定和程序处理。 研究生签名： 鸯选 弘扣年易月叫日 硕士论文 求解一类订单调度问题的遗传算法研究 1 绪论 1 1 研究背景 随着科学技术的不断进步，经济的不断发展和国际化的加剧，制造企业面临的市场 竞争越来越激烈。在此过程中，逐渐形成了以客户为中心，基于时间的竞争市场机制， 制造业的生存与发展也开始面临着一些新的挑战，例如客户需求多样化和个性化，严格 的交货期要求，多品种小批量或单件生产，供应链间的竞争和供应商间的合作，高新信 息技术的使用范围越来越广泛等。 在这些新的挑战下，越来越多的企业按照订单的方式进行生产和制造，这就导致了 制造业除成本与品质外，从接单到交货的反应速度也成为主要的竞争力。面对具有不同 加工要求和不同完工期限的产品和订单，如何进行合理的作业计划安排和生产调度、以 较低的生产成本最大限度地满足顾客的要求成为理论界和企业界关心的问题。合理化的 调度改善可以有效缩短生产流程时间，降低在制品存货，减少工单延误，提升接单能力 与交货表现。订单调度( o r d e rs c h e d u l i n g c u s t o m e ro r d e rs c h e d u l i n g ) 就是在这样的情 况下产生的，它是研究一组产品( 或作业) 的整体完工情况( 例如一个订单包含不同类 型的产品) 的调度问题，用以提高实际生产率、缩短总完工时间、改善交货表现。 实际上，生产制造系统广泛存在着订单调度模型。生产制造系统通常包括两个阶段， 在预组装阶段首先需要制造不同类型的部件；之后在组装阶段，这些部件将会被组装成 最终的产品( 工件) 。前面的预组装阶段包含若干个并行机器，其中每个机器可以生产 相应的若干个部件。显然，只有在所有必需的部件生产完成之后，组装操作才能够开始 进行。在更广泛的领域中也存在着订单调度问题。例如在汽车维修企业，只有当某辆汽 车的所有故障都修理好之后，车辆才能够开出修理厂。还例如港口起重机的例子：港口 的每艘船有若干个货舱，每个货舱的装载或卸货都需要一定的时间，我们可以将一台起 重机看作是一台机器，一艘船是一个订单；一个起重机仅可以对货舱装载或卸货；多台 起重机可以同时对船上货舱进行作业，直到某一艘船上所有货舱的作业都被处理完成， 该船才能开走。 对于订单调度问题的研究，很多模型都已被证明是n p h a r d 或者强n p h a r d ，以致 现有的调度理论和方法在处理这些问题时能力有限。针对这样的情况，许多学者研究了 具有特定性质的订单调度问题，提出了一些有效的启发式算法或规则，这都对订单调度 问题的求解提供了较好的解决方案。 随着计算机技术的发展和生命、工程科学的相互渗透，以获得满意解为目标的智能 算法开始应用到车间调度等优化领域，并显示了解决大规模复杂问题的潜力。其中，进 化计算因其显著的寻优能力和鲁棒性而备受关注。遗传算法( g e n e t i ca l g o r i t h m ，g a ) l 1 绪论硕士论文 是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。 由于其思想简单、易于实现以及表现出来的稳健性，已经应用在优化和搜索、智能控制、 模式识别以及人工生命等领域，特别是对于那些传统搜索算法难以解决的复杂的和非线 性的问题尤其适用。它的提出一定程度上解决了传统的基于符号处理机制的人工智能方 法在知识表示、信息处理和解决组合爆炸等方面遇到的困难。学者们开始将遗传算法引 入调度研究中，并获得了广泛的应用，取得了较好的效果。 根据以上探讨，本文将在前人对订单调度模型研究的基础上，尝试将遗传算法应用 到该类问题的求解，以期获得良好的优化效果。由于订单调度模型的多样性和复杂性， 文章仅对订单调度问题的一类模型专门机环境下总完工时间和总加权完工时间进 行研究。在研究过程中，本文将遗传算法与目前使用较多的启发式规则进行比较研究， 分析遗传算法应用于订单调度模型的优点和不足，并提出一些改进方向，为遗传算法更 广泛的应用于订单调度问题提供一些思路和方法。 1 2 研究意义 本文主要的研究意义有： ( 1 ) 订单调度模型在实际中有着广泛的应用背景，在国外已经有了较多的研究并 应用于一些生产实际，但国内学者对该类模型研究尚不多，本文对订单调度模型的研究 为国内学者对此类模型的继续研究作了一些铺垫； ( 2 ) 文献中对订单调度模型的研究和求解多采用启发式规则和动态规划，本文将 遗传算法( 智能算法) 应用于订单调度的两类模型中，为遗传算法更广泛的应用于订单 调度模型进行了有益探索； ( 3 ) 本文将遗传算法与五个启发式规则对订单调度模型的求解结果进行了比较研 究，分析了遗传算法的优点、不足和应该注意的问题，为遗传算法更好的应用于订单调 度模型求解提出一些改进方向，为今后的研究提供思路和依据； ( 4 ) 本文的研究结果也对订单调度模型应用于实际生产制造过程提供了一些理论 依据和基础。 1 3 订单调度问题 1 3 1 调度问题 生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造 系统实现管理技术、运筹技术、自动化与计算机技术发展的核心。有效的调度方法和优 化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。改善生产调度方 案，可大大提高生产效益和资源利用率，进而增强企业的竞争能力。生产调度的研究主 2 硕士论文求解一类订单调度问题的遗传算法研究 要可分为建模和调度算法设计两方面，它是一个交叉性研究领域，涉及运筹学、数学、 计算机工程、控制工程、工业工程等多个学科。其中，建模主要研究调度模型、调度规 划、目标函数等内容；算法主要研究算法设计、算法复杂性、算法收敛性和优化质量等 内容。 生产调度问题复杂性较强，并行机调度问题种类很多，但其中以考虑求解最大完工 时间的问题居多，在考虑这个问题时，会因为工件批次生产与否、加工顺序不同等等的 因素而使得调度结果有所不同，因此会衍生出许多类型的问题，而且每一个问题都有一 个特定的目标函数，不同的目标函数也会计算出不同的最终结果，使用的目标函数经由 h a r te ta l t 6 】整理而得，如表1 1 所示。 表1 1 常见调度问题绩效衡量指标 类别 绩效指标 流程相关 平均流程时间( m e a nf l o wt i m e ) 加权流程时间( w 西g h t f l o wt i m e ) ( f 1 0 wm e a s u r e s ) 变量流程时间( v a r i a n c eo ff l o wt i m e ) 平均等待时间( m c a nh o wt i m e ) 平均完工时间( m e a nc o m p l e t i o nt i m e ) 平均加权完工时间( a v e r a g ew c i g h t 例lc o m p l e t i o nt r i n e ) 时间相关总完工时间( m a k e s p a no rc 0 ) 、 、 ( t i m e - b a s e x im e a s u r e s ) 总加权完工时间( t o t a lw 萌g h t c dc o m p l e t i o nt i m e ) 总加权流程时间( t o t a lw d g h t e df l o wt i m e ) 单位时间产量( t h r o u g h p u t ) 生产周期( c y c l et i m e ) 平均迟延时间( m e a nl a t e n e s s ) 平均延迟时间( m e a nt a r d i n e s s ) 总延迟时间( t 0 t a lt a r d i n e s s ) 交期相关 总加权延迟时间( t o t a lw 苟g h t c dt a r d i n e s s ) 延迟工作数( n u m b e ro f l a t ej o b s ) ( d u e - d a t er e l a t e dm e a s u r e s ) 宽放时间( a l l o w a n c e st i m e ) 符合交期百分比( ) 延迟工件数( n u m b e ro f l a t e n e s s ) 延迟工件百分比( p r o p o r t i o no f t a r d yj o b s ) 机器相关 平均机器利用率( a v e r a g em a c h i n eu t i l i z a t i o n ) ( m a c h i n em a s u r e s )平均机器闲置时间( i d l et i m e ) 在制品相关 平均在制品数量( a v e r a g ew i p ) ( 聊m e a s u r e s ) 平均等待工件数( a v e r a g en u m b e ro f j o b si nq u e u e ) 总成本( t o t a lc o s t ) 平均等待成本( a v e r a g ec o s ti nq u e u e ) 成本相关在制品存货成本( c o s to f c a r r y i n gw i p ) ( c o s t - b a s e c lm e a s u r e s ) 机器设置成本( f a c i l i t ys e t u pt i m e ) 缺货成本( b a c k o r d e rc o s t ) 延迟完工成本( t a r d i n e s sc o s t ) 而在求解方法中，早期学者最常使用精确法( 分支定界法、线性规划法) 解决并行 机调度问题，如在1 9 7 8 年l a 、v l e ra n dl a b e t o u l l e 刀使用线性规划法( l i n e a rp r o g r a m m i n g ) 3 1 绪论 硕士论文 方法求解并行机双目标( 与k ) 的问题，将加工时间乘上权重转化为成本，延迟 时间当成惩罚成本，目标函数为总成本最小化。精确法之优点在于能求得最佳解，但求 解过程费时费力，问题规模越大就越可能无法在合理的时间内求得最佳解。因此，便有 学者提出启发式算法来解决此类未定式多项式难度问题，以希望能在短时间内找到近似 解。但随着时代的进步，问题趋于复杂多元化，规模也越变越大，在求解过程中容易陷 入局部最优解的困境。因此又有学者提出改进的启发式算法，主要目的在于增大在搜寻 过程中跳脱出局部最优解的机会，我们将之称为启发式演算法，用来和之前的启发式算 法做出区别【8 1 1 9 1 o 】【1 1 1 。 遗传算法最早是1 9 7 0 年代由h o l l a n d 提出，主要利用生物学遗传优选的原理，利用 个体的配对与刺激法产生突变，来产生更好的下一代，然后将此种生命科学现象应用于 求解最佳化的问题。f a t i m a 1 l 】运用遗传算法求解零工式生产调度( j o bs h o ps c h e d u l i n g ) 的问题，包含非等效并行机，以为目标函数，将结果与g h e d j a t i 和p o m e r o l 的实验 相互比较，表明遗传算法可改善近似解最多达到1 1 。 e w a 1 2 】以遗传算法和双数产生法( c o l m n ng e n e r a t i o n ) 求解非等效并行机问题( 包 含前置作业时间) ，以气，与切换机器( c h a n g e o v e r ) 成本为目标函数，将结果与作者提 出的下界值作比较，结果显示两阶段启发式算法求解的结果的切换机器成本不会大于加 工时间成本的十分之一。 r u i z 和m a r o t o 【1 3 】以遗传算法求解流线型生产性能，且每一站都包含非等效并行机， 并考虑相应的准备时间，以c 。为目标函数，结果显示较之其他启发式算法优异许多。 1 3 2 订单调度产生背景 制造型企业主要分为两类：面向库存的制造型企业和面向订单的制造型企业。随着 顾客的需求变得多样化和个性化以及制造业追求高度的专业分工，面向订单的制造类型 已被越来越多的企业所接受。考虑到企业问持续增长的竞争性，目前企业的竞争不仅在 于价格和质量方面，更延伸至顾客订单交付的快速与准时方面。在一个面向订单的制造 型企业，顾客订单是企业生产的驱动力，如何准时完成顾客订单对企业来说十分重要。 对顾客订单的生产安排进行有效改善可以有效缩短生产时间，降低在制品存货，减少订 单延误，提升接单能力与交货表现，因此如何安排顾客订单对面向订单的制造型企业来 说十分重要。订单调度就是在这样的情况下产生的，用以提高实际生产率、缩短总完工 时间、改善交货表现等。 1 3 3 订单调度问题描述和分类 考虑一个制造型企业有m 台并行机器，可以用来加工七种不同类型的作业。假设有 栉个不同的客户分别下达刀个不同的订单。每个订单，包含不种类型的产品( p r o d u c t ) 或作业( j o b ) ，其中，= l ，2 ，k ，j = l ，2 ，刀。订单j 中每种类型作业的加工时间为 4 硕士论文 求解一类订单调度问题的遗传算法研究 p t , o 个时间单位( u n i to f t i m e ) ；若m = 0 ，表明订单中不包含作业，。 每个订单，可能有以下三个参数：释放日期( r e l e a s e d a t e ) ，代表订单，到达的时 间；交货日期( d u ed a t e ) d ，代表制造商承诺订单j 的运送或交货日期；权重w ，代 表订单，的重要性。订单的完成日期可以在交货日期d ，之后，但在这种情况下会出现 相应的惩罚。若交货日期d ，必须被满足，则用d ，表示最后交货期限。在某些情况下， 订单可能还会有优先权约束( p r e c e d e n c ec o n s t r a i n t s ) ，即要求一个或多个订单必须在某 个订单开始加工之前完成。 对于任意一个订单j ( ，= l ，2 ，刀) ，它的作业，( ，= l ，2 ，k ) 可以使用m 台机器 中的若干台进行加工即机器一个子集合，记为m l 冬 1 ，2 ，m 。m 台机器可以是等 效的( i d e n t i c a l ) ，一致的( u n i f o r m ) 或者不相关( u n r e l a t e d ) 的。在等效的机器环境中， 若假定每台机器的加工速度为1 ，则订单_ ，的作业，在i 鸩中任意一台机器上的加工时 间都相等，即需要仇，= 阮个时间单位。在一致的机器环境中，每台机器i 均有一个加工 速度m 0 ，因此若订单j 的作业，使用f m 中机器进行加工，则需要的加工时间为 p r o = p t , v , 个时间单位。最后一种情况是不相关的机器环境，指每台机器加工每种作业 ，都有着不同的能力和表现，即若f m 中的机器加工作业珀勺速度与机器和作业类型有 关，为屹，则订单j 中的作业z 在机器f 上的加工时间为砌= 砌屹个时间单位。 并行机环境可以是非抢占的( n o n - p r e e m p t i v e ) 或者抢占的( p r e e m p t i v e ) 。在非抢 占环境中，每个订单j 中的每个作业，在必须以不间断的方式在一台机器上进行加工。 相反，在抢占环境中，某个订单的某个作业可以先在某台机器上加工一段时间，暂停一 段时间之后继续在该台机器或者其他机器上进行加工。在订单调度模型中，通常假设“抢 占的不允许多台机器同时制造某个订单中的同一个作业。 不同订单中的同一种作业，可以在i m 中的任意一台机器上进行批量( b a t c h ) 加 工，订单之间不引起准备时间( s e t u pt i m e ) 。然而，作业，的所有批量在加工之前可能会 产生准备时间。作业珀勺一个批量在另外一个作业，的一个批量之后进行加工，机器f 的 准备时间记为品，。如果作业z 是机器i 加工的第一种作业，则准备时间记为墨叫。如果对 于每种作业，都有= s s 。，= s u ，则机器f 的准备时间称为次序独立的( s e q u e n c e i n d e p e n d e n t ) ，否则它们是次序相关的( s e q u e n c ed e p e n d e n t ) 。如果对于每台机器i 和所 有的z 和z ，都有s u ，= ，则准备时间称为机器独立的( m a c h i n ei n d e p e n d e n t ) ，否则为 机器相关的( m a c h i n ed e p e n d e n t ) 。如果准备时间既满足次序独立和机器独立，则对于每 台机器f 有勘，= = 勘= 。更进一步，如果准备时间还满足作业类型独立( p r o d u c t t y p e i n d e p e n d e n t ) ，则对每台机器f 都有s 册= j 删= s u = 墨= s 。若s = 0 ，则表明订单调度不需 要考虑准备时间。 订单调度模型的优化目标通常是全部订单完成时间的函数，这些完成时间在订单调 度是相关的。订单，的完工时间( c o m p l e t i o nt i m e ) 记为c ，是指该订单所有作业在某 5 i 绪论 硕士论文 台机器上的最大完工时间。设c ，表示订单的某个作业，在某台机器上的完工时间，则 显然有 c ! ，= i i 瞰【c i ，c 2 ) 优化目标也可以是交货日期的函数。订单_ ，的迟延( 1 a t e n e s s ) 定义为 l j = c 广d j 由上式可知，当订单迟于交货日期完成时，三，为正值，否则三，为负值。而订单 的延迟( t a r d i n e s s ) 定义为 弓= m a x c j - d j ，0 - m a x l j ，0 ) 所以，延迟( t a r d i n e s s ) 是非负的。订单j 的单位惩罚( u n i tp e n a l t y ) 可以定义为 = 任巍9 哆 通常我们关注订单调度模型中的一些优化目标，主要有： ( 1 ) 最大完工时间( m a k e s p a n ) ：c o m m a x l 耵。 q ； ( 2 ) 最大迟延时间( m a x i m u ml a t e n e s s ) ：c o m a x i 纠s 。 与 ； ( 3 ) 总完工时间( t o t a lc o m p l e t i o nt i m e ) ：q ； ( 4 ) 总加权完工时间( t o t a lw e i g h t e dc o m p l e t i o nt i m e ) ：_ q ； ( 5 ) 总加权延迟( t o t a lw e i g h t e dt a r d i n e s s ) ：m 乃； ( 6 ) 总加权迟延订单数( t o t a lw e i g h t e dn u m b e ro f l a t eo r d e r s ) ： ：w ，u ，。 j _ ，j 以上本章对订单调度模型进行了较完整详细的描述，可知订单调度模型有多种类 型，其中的两个极端的情况为： ( 1 ) 专门机情况( f u l l yd e d i c a t e dc a s e ) 有m 台机器和m 种作业；每台机器i ( 扛l ，2 ，m ) 只能加工m 种作业中的唯一一 种。换句话说，机器集合与作业集合之间存在着一对一的映射关系。这表明七= 朋， 对于每一个z = 1 ，2 ，七有i 鸩i = 1 ，且若，= ，则m ，鸩。 ( 2 ) 完全柔性情况( f u l l yf l e x i b l ec a s e ) 朋台机器的每台都可以加工所有七种作业，即对每种类型的作业，= l ，2 ，七，有 m l = 1 ，2 ，m 。 当然，在这两种极端订单调度模型之间还有很多其他模型。应该注意的是，对于专 门机情况，由于每台机器只能加工一种类型的作业，因此机器环境类型( 等效的，一致 的和不相关的) 就失去了意义。对于这种情况的订单调度模型，我们对机器环境类型不 加区分。 1 3 4 订单调度模型应用 订单调度模型在很多领域有着广泛的实际应用背景。事实上，对于决策者来说，在 硕士论文求解一类订单调度问题的遗传算法研究 许多背景下考虑考虑一组作业的整体完工时间而非考虑任意给定订单中单个类型作业 完成时间的思想有必要的。首先，对一个订单分开来进行运输将不可避免的增加运输成 本；其次，分拆订单会带来额外的管理成本；最后，某些顾客会要求供应商运送完整的 订单。因此，供应商必须等待某个订单的全部作业都加工完毕才能进行运送。任何拥有 一定数量并行资源面向订单制造的制造型企业都会遇到订单调度模型所描述的情况。 j u l i e n 和m a g a z i n e t l 】举出了两个订单调度模型的应用实例。第一个实例与计算机外 围设备( 例如终端设备、键盘和硬盘等) 制造商有关。当顾客订购计算机系统时，也会 同时订购不同种类不同数量的计算机外围设备，且常常要求整个订单同时运送。从制造 商角度来看，将多个订单对每种外围设备的不同要求整体考虑，聚合在一起进行大批量 生产和订单调度以减少生产准备次数是十分有利的。 第二个用来描述订单调度模型的例子来自具有生产多种类型药物能力的制药公司。 制药厂在生产药品时，每种类型的药品需要分别装瓶。对于一种给定的药，通常有着多 种不同尺寸的药瓶，药片和药瓶可基于预测进行生产。然而，由于顾客( 例如药店或者 医院) 会对每种产品( 指给定药品类型和药瓶尺寸) 下达不同数量的订单，因此药瓶和 包装阶段是订单驱动的。这就导致药瓶生产工厂的生产准备需要经常进行转换。 y a n g _ 【1 4 】给出了订单调度的另外一个例子，即汽车修理厂。假定每辆待修理汽车有若 干个需要修理的损坏部分，每个车辆的特定损坏部分只能由修理厂中的某些修理师进行 维修。若干个修理师可以同时对同一辆车进行修理。当一个修理师完成一辆汽车的修理 工作时，他可以继续修理其他车辆的相应损坏部分。一辆汽车在完全修好之前不能离开 汽车修理厂 以上我们列举了订单调度模型的三个实例，实际上，生产制造系统广泛存在着订单 调度模型。生产制造系统通常包括两个阶段，在预组装阶段首先需要制造不同类型的部 件；之后在组装阶段，这些部件将会被组装成最终的产品( 工件) 。前面的预组装阶段 包含若干个并行机器，其中每个机器可以生产相应的若干个部件。显然，只有在所有必 需的部件生产完成之后，组装操作才能够开始进行。文献中列举了大量的诸如此类的两 阶段组装系统的应用实例。图1 1 显示了订单调度、生产调度和主生产计划之间的关系 订单调度 简单主生产计划 i 订单释放， r i 生产调童 图1 1 订单调度、生产调度和主生产计划之间的关系图 7 1 绪论硕士论文 1 3 5 订单调度研究综述 为了下文描述方便，本节首先对订单调度模型的编码方式进行说明。文献对订单调 度问题的分类情况进行了符号编码，是对文献中介绍的o f l p l r 标记进行的扩展。 在口区域，专门机情况的机器环境记为p d m ，m 代表机器的数目，当可以假定机 器数量为任意时，m 可以忽略。对于完全柔性的情况，等效的、一致的和不相关的的并 行机环境分别被记为p 砌，q f m 和脚锄。同样，m 可以忽略。 在区域，1 7 k 代表有k 种不同类型的作业，省略k 表明作业类型任意。另外，区 域可以包括s 、s ，或者s 。，用以表示之前定义的不同类型加工准备时间。注意在专门机 的情况下由于每台机器只能加工某一种特定的作业，因此准备时间在这种情况下没有意 义。其他可以加入区域的约束还有有释放日期，抢占性，优先性，加工时间属性等。 y 区域代表需要优化的目标函数类型，例如，最大化延后时间迟延k 。和总加权迟 延订单数量 ：w i u ，等。 例如符号p d m r j 罗正表示专门机环境中有 n 个并行机器，刀个不同的订单，订单， 有一个释放时间和约定的交货日期d ，。优化目标是最小化总延迟时间。 j u l i e n 和m a g a z i n e 【i 】首先出了订单调度的概念，他们从一些实际问题中归纳总结出 了订单调度问题。例如，制造企业安排加工不同类型作业的客户订单，客户可以订购不 同类型组合作业；汽车维修企业对汽车进行维修；港口起重机作业等。该问题不同于其 他大多数调度问题，因为目标是与整体批量的完成时间有关的，而不是每个作业的完成 时间。 对订单调度模型大部分的研究都集中于专门机的情况。s u n g 和y o o n 1 6 】考虑m = 2 和 所有0 = o 的情况，即肋2 0 q 。研究表明肋2 l 吩c ：，是强n p h a r d 。对于订单等 权重的特殊情况，w a g n e u r 和s r i s k a n d a r a j a h 【1 7 1 尝试证明p d 2i xc ，是强n p - h a r d 。然而， l e u n g 等t t s l 的研究表明他们的证明不正确。w a n g7 f 1 1c h e n g d 9 1 对p z ：, l l xw ：, 模型研究了 三种贪婪启发式算法。 对于和交货日期有关的优化目标，w a g n e u r 和s r i s k a n d a r a j a h 1 7 】的研究表明 p d 2 i e u j 在通常意义下是n p - h a r d 。c h e n g 和w a n 9 2 0 1 的研究表明对于每个固定的 m 2 ，存在一个伪多项式时间算法。n g , c h e n g 和y u 孤1 2 1 】的研究表明当机器数量任意时， 该问题变成强n p - h a r d ，且更多限制条件的问题如肋l 岛 o ，l ，嘭= a l x u , ，仍然是强 n p - h a r d 。 完全柔性情况的订单调度模型更加复杂，然而仍然有一些学者进行了研究。当每种 作业都没有准备时间时，y 飙g 捌的研究表明尽管每个订单只包括一种或两种作业， p f 2 i f i iyc ，在通常意义下仍是i d - h a r d 。当机器数量任意时，b l o e h e r 和c h h a j e a t 矧表 明即l n c ，是n p - h a r d 。b l o c h e r 和c h h a j e d 4 也开发了5 种解决该问题的启发式算法， 8 硕士论文求解类订单调度问题的遗传算法研究 并列举了实验结果。 当允许抢占时，l e u n g 等【2 4 】表明p f 2p r m p ，n e i c ，为n p h a r d ，他们也对更普通 i h 3 题p f i p r m p ，n i 罗c ，开发了相应的处理算法。 即使对于一台机器的情况，引入准备时间也会使得问题更加复杂和困难。g e r o d i m o s 等【2 5 】研究了阿1 i 墨，h k r 和即1 i 墨，n i t 。研究结果表明艘1 i 岛，n l k 是n p - h a r d ，可以 采用动态规划予以解决。对于最小化加权迟延订单数目的优化目标，g e r o d i m o s 等【2 5 】的 研究表明阿l i s ，兀2 l 通常是n p - h a r d ，g f f p f l i s = 1 ，h ，p c o ，l i 是强n p h a r d 。 对于最小化加权完工时间的优化目标，g e r o d i m o s 等瞄】研究了 即1 b ，兀，g 丁，p c o ，l 引qf i 年i p f l l s t ，n ，g r ，既 oy c ，的情况等。 r o e m e r t 3 】研究了并行机环境下多种类型订单调度模型的复杂性，研究结果表明大部 分的订单调度问题都是n p - h a r d 。l i t l 5 】在其博士论文中对订单调度问题进行了全面总结， 详细研究了专门机和柔性机环境下多类订单调度模型，开发了一些启发式规则，取得了 较多研究成果。 近期，j o s e p hy - t l e u n g ，【u k 2 6 2 7 】【1 8 】等对订单调度问题进行了卓有成效的研究，包括： ( 1 ) 研究了两类用于解决总加权完工时间订单调度模型的启发式算法，即连续两阶段 启发式算法和动态两阶段启发式算法，共研究了9 种启发式算法，并根据其有效性将这 些启发式算法进行比较，同时也考虑了算法的运行质量和运行时间；( 2 ) 研究了基于多 作业类型的最小化总加权完成时间的订单调度，其研究重点是设计和分析有效的无释放 时间的情况下的启发式算法，包括各种静态和动态的优先权规则以及两个更为复杂的基 于线性规划的算法，还分析了优先权规则和算法的性能范围，并进行了比较分析。该规 则有时可以将结论延伸至有释放时间的情形：( 3 ) 研究了柔性情况等效机环境下的最小 化加权总完成时间的订单调度模型，提出了非抢先权和抢先权的启发式算法，得到了包 括机器台数以及机器速度差异函数的最差下界。实验结果表明，该规则非常接近最优解。 ( 4 ) 研究了主从系统中目标函数为总完工时间和最大完工时间的订单调度模型。研究 表明，即使抢先权不允许存在，两个问题仍都是强n p - h a r d ，这是主从模式订单调度问 题的第一个一般性结果。 另外，一些学者对较为实际的订单调度问题进行了有益研究。d a g a n z o1 2 9 1 、 p c t c r k o f s k y 和d a g a n z o 【3 0 l 等人研究了港口起重机调度问题，将三个基本调度原则发展并 应用于启发式算法中，提出了6 种用来评价算法性能的指标。p c t c r k o f s k y 和d a g a n z o 【3 0 】 研究了一种分支定界法，但缺乏一定的理论基础。r o c m e r 署f l a h m a d i 3 1 】也研究了这个问 题，研究结果表明，该问题是一元强n p 完全问题，并提供了更容易和简洁的证明。 r o z a 趾眦a d i 【3 l 】研究了快速响应的协调订单调度问题，解决了制造商在基于订单加工环 境下生产多种产品类型和经营中的相关问题。研究表明，该模型的最小化总加权完工时 间和交货时间问题的是n p h a r d ，运用最佳时间表来解决一些特殊情况问题，并提出一 9 1 绪论硕士论文 些启发式的解决办法。 1 4 论文研究方法和技术路线 本文在研究过程中主要使用到的研究方法有： ( 1 ) 文献归纳。对订单调度模型的相关文献进行整理和归纳，总结订单调度模型 的类型、特点和研究现状，分析其主要求解方法和存在的问题，为本文的研究奠定基础： ( 2 ) 遗传算法。本文使用遗传算法作为订单调度模型求解的主要手段，对遗传算 法用于订单调度模型的编码、交叉算子和变异算子等进行了研究； ( 3 ) 仿真分析。本文对多种情况订单调度问题大量数据算例进行了仿真分析实验， 用以验证遗传算法用于订单调度模型的可行性和可靠性，消除了随机因素，为论文的结 论提供了有力支撑： ( 4 ) 比较研究。本文通过对遗传算法与五个启发式规则对订单调度模型求解的比 较研究，一方面显示了遗传算法应用于订单调度模型求解的良好性能，另一方面分析了 遗传算法的劣势和不足，为遗传算法进一步的完善和改进提供思路。 论文研究的技术路线见图1 2 所示。 l o 硕士论文求解一类订单调度问题的遗传算法研究 1 5 论文的主要工作和结构 图1 2 论文技术路线图 本文对遗传算法在订单调度模型中的应用进行了研究和探讨，提出可以将遗传算法 用于两类订单调度模型的求解。重点研究了遗传算法用于订单调度模型的编码和各个遗 传操作等，在两类模型的研究过程中，均采用数值仿真分析实验与现有的五个启发式规 则进行比较研究，这都为本文的一些结论提供了支撑和说服力。论文的结构如下： 第一章为绪论，介绍本文的研究背景、研究意义、研究方法和技术路线等，是全文 的概括； 第二章为相关理论介绍和文献综述，介绍了遗传算法产生与发展、原理和特点、使 用步骤和操作设计等；介绍了调度问题及相关研究现状；详细阐述了订单调度模型的产 1 绪论硕士论文 生背景、问题描述、数学模型和分类以及应用领域等，并引出了本文要