基于排序理论的生产和运输集成调度研究.pdf

天津大学硕士学位论文基于排序理论的生产和运输集成调度研究姓名：刘道良申请学位级别：硕士专业：管理科学与工程指导教师：李波20090501中文摘要生产和运输配送是供应链管理的两个重要环节，要使供应链获得好的运作绩效，生产和运输这两个环节必须进行协调运作。在过去的2 0 年里，已经有大量的文献讨论了这种协调、集成性，不过研究的着眼点都是在战略层和战术层上，对于运作层面上的研究还是比较少，而现代管理讲究的是一种精细化管理，运作层面上的这种研究也非常重要。本文将传统的生产调度即排序问题引入到供应链管理中，与运输调度的车辆路径调度结合在一起，在供应链管理运作层面上来研究生产和运输的集成调度问题。该问题就是有一系列的客户订单，订单先在工厂里加工，加工完成后由车辆运送到各自客户，目标是找到一个最优的生产排程和车辆调度解让客户服务水平和运输成本达到最优。客户服务水平是订单到达客户的时间函数，运输成本由固定成本和可变成本组成。本文的主要研究内容有：首先，研究了运输资源无约束下的生产和运输集成调度问题。针对该问题，改进了两个模型，即单机单客户和单机多客户的生产和运输集成调度模型，对这两个模型都给出了基于动态规划的求解方法，并都给出了时间复杂度分析。其次，研究了运输资源有限情形下的生产和运输集成调度问题。针对该问题，改进了两种模型：即单客户单车辆和单客户多车辆的生产和运输集成调度模型，对两个模型本章都给出了基于动态规划的求解方法，并都给出了时间复杂度分析。最后，通过对生产和运输的集成调度与独立调度的比较，来研究生产和运输集成调度的优越性。针对第三章、第四章提到的四个模型用独立调度的方法进行了求解，并将得到的结果与集成调度得到的结果进行比较，通过比较可以验证集成调度的优越性。最后对这种优越性进行了仿真实验，通过大量的数据仿真可以得出随着权重口值、客户数量g、车辆容量c 的增大，这种集成调度的优越性更加明显的结论。关键词：生产和运输集成调度动态规划集成调度价值A B S T R A C TP r o d u c t i o na n dt r a n s p o r t a t i o no p e r a t i o n sa r et h et w ok e yo p e r a t i o n a lf u n c t i o n si nas u p p l yc h a i n T oa c h i e v eg o o do p e r a t i o n a lp e r f o r m a n c ei nas u p p l yc h a i n，i ti sc r i t i c a lt oi n t e g r a t et h e s et w of u n c t i o n sa n dp l a na n ds c h e d u l et h e mj o i n t l yi nac o o r d i n a t e dm a n n e r I nt h ep a s tt w Od e c a d e s，at r e m e n d o u sa m o u n to fr e s e a r c hh a sb e e nd o n eo nv a r i o u si n t e g r a t e dp r o d u c t i o n-d i s t r i b u t i o nm o d e l sa ts t r a t e g i ca n dt a c t i c a lp l a n n i n gl e v e l s，b u tt h er e s e a r c ha tt h ed e t a i l e ds c h e d u l i n gl e v e li sf a i r l yl i t t l e M o d e mm a n a g e m e n ti sm o r ea n dm o r es c i e n t i f i c，t h i sr e s e a r c ha tt h ed e t a i l e ds c h e d u l i n gl e v e li sv e r yi m p o r t a n ta n dn e e d e d S oi n t h i sp a p e r,w es t u d ya ni n t e g r a t e ds c h e d u l i n gp r o b l e mo fp r o d u c t i o na n dt r a n s p o r t a t i o na tt h ed e t a i l e dl e v e l I nt h i sp r o b l e m,t h et r a d i t i o n a ls c h e d u l i n gp r o b l e mo fp r o d u c t i o ns c h e d u l i n gi si n t r o d u c e da n dc o m b i n e dw i t ht r a n s p o r t a t i o ns c h e d u l i n gv e h i c l er o u t i n gp r o b l e ma tt h ed e t a i l e dl e v e l T h i sp r o b l e mC a nb ed e s c r i b e da sf o l l o w：as e to fc u s t o m e ro r d e r sa r ef i r s tp r o c e s s e di nam a n u f a c t u r i n gp l a n ta n dt h e nd e l i v e r e dt Ot h ec u s t o m e r sd i r e c t l yw i t h o u ti n t e r m e d i a t ei n v e n t o r y T h ep r o b l e mi st of i n daj o i n ts c h e d u l eo fp r o d u c t i o na n dt r a n s p o r t a t i o ns u c ht h a ta l lo b j e c t i v ef u n c t i o nt h a tc o n s i d e r sb o t hc u s t o m e rs e r v i c el e v e la n dt o t a lt r a n s p o r t a t i o nc o s ti so p t i m i z e d C u s t o m e rs e r v i c el e v e li sm e a s u r e db yaf u n c t i o no ft h et i m e sw h e nt h eo r d e r sa r ed e l i v e r e dt ot h ec u s t o m e r s T h et r a n s p o r t a t i o nC O S to fad e l i v e r ys h i p m e n tc o n s i s t so faf i x e dc h a r g ea n dav a r i a b l ec o s t T I l em a i nw o r k sa r e：F i r s t l y,t h i sd i s s e r t a t i o ns t u d i e st h ei n t e g r a t e dp r o d u c t i o na n dt r a n s p o r t a t i o ns c h e d u l i n gp r o b l e mu n d e rt h eu n c o n s t r a i n e dr e s o u r c e so ft r a n s p o r t a t i o n I nt h i sp r o b l e m,w ed e v e l o pt w om o d e l s o n ei st h ei n t e g r a t e dp r o d u c t i o na n dt r a n s p o r t a t i o ns c h e d u l i n gp r o b l e mo fs i n g l em a c h i n ea n ds i n g l ec u s t o m e r,t h eo t h e ri st h ei n t e g r a t e dp r o d u c t i o na n dt r a n s p o r t a t i o ns c h e d u l i n gp r o b l e mo fs i n g l em a c h i n ea n dm u l t i p l ec u s t o m e r s F o re a c ho ft h em o d e ls t u d i e d w ep r o v i d ead y n a m i cp r o g r a m m i n ga l g o r i t h ma n dt i m ec o m p l e x i t ya n a l y s i s S e c o n d l y,t h i sd i s s e r t a t i o ns t u d i e st h ei n t e g r a t e dp r o d u c t i o na n dt r a n s p o r t a t i o ns c h e d u l i n gp r o b l e mu n d e rt h ec o n s t r a i n e dr e s o u r c e so ft r a n s p o r t a t i o n I nt h i sp r o b l e m，w ed e v e l o pt w om o d e l s，o n ei st h ei n t e g r a t e dp r o d u c t i o na n dt r a n s p o r t a t i o ns c h e d u l i n gp r o b l e mo fs i n g l ec u s t o m e ra n ds i n g l ev e h i c l e，t h eo t h e ri st h ei n t e g r a t e dp r o d u c t i o na n dt r a n s p o r t a t i o ns c h e d u l i n gp r o b l e mo fs i n g l ec u s t o m e ra n dm u l t i p l ev e h i c l e s F o re a c ho ft h em o d e ls t u d i e d，w ep r o v i d ead y n a m i cp r o g r a m m i n ga l g o r i t h ma n dt i m ec o m p l e x i t ya n a l y s i s A tl a s t，w ea l s oi n v e s t i g a t et h ep o s s i b l eb e n e f i to fu s i n gt h ei n t e g r a t e dm o d e lr e l a t i v et oas e q u e n t i a lm o d e lw h e r ep r o d u c t i o na n dt r a n s p o r t a t i o no p e r a t i o n sa l es c h e d u l e ds e q u e n t i a l l ya n ds e p a r a t e l y T h r o u g ht h ec o m p a r i s o no fr e s u l t sb yt h et w ok i n d so fs c h e d u l i n gs o l u t i o nf o rt h em o d e lo fc h a p t e rt h r e ea n dc h a p t e rf o u r,t h ea d v a n t a g e so fi n t e g r a t e ds c h e d u l i n gm o d e lC a l lb ev e r i f i e d A l s oc o m p u t a t i o n a lt e s t sa l ep e r f o r m e d T h es i m u l a t i o nr e s u l t ss h o wt h a tt h r o u g ht h ev a l u eo fw e i g h t 口t h en u m b e ro fc u s t o m e r sg，a n dv e h i c l ec a p a c i t yci n c r e a s e s，t h ea d v a n t a g e so ft h i si n t e g r a t e ds c h e d u l i n ga l em o leo b v i o u s K E YW O R D S：I n t e g r a t e ds c h e d u l i n go fp r o d u c t i o na n dt r a n s p o r t a t i o n,D y n a n l l Cp r o g r a m m i n g，V a l u eo fi n t e g r a t i o n独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得苤壅盘堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：茜1 董莨签字日期：砂叼尹年 月z 日学位论文版权使用授权书本学位论文作者完全了解苤壅盘堂有关保留、使用学位论文的规定。特授权鑫鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明)学位论文作者签名：知1 煎衾签字日期：沙、，7 年月z 日导师签名：李激签字日期：劫夕年月二日第一章绪论1 1 问题背景及研究意义第一章绪论进入2 0 世纪9 0 年代以来，由于科学技术不断进步和经济的不断发展、全球化信息网络和全球化市场形成及技术变革加速，围绕新产品的市场竞争也日趋激烈。技术进步和需求多样化使得产品寿命周期不断缩短，企业面临缩短交货期、提高产品质量、降低成本和改进服务的压力。所有这些都要求企业能对不断变化的市场做出准确、快速、有效的反应，源源不断地开发出满足用户需求的、定制的“个性化产品”去占领市场以赢得竞争【l】。而随着全球经济一体化、市场国际化和电子商务的发展，市场竞争已由原来有形产品的竞争、价格的竞争，转换为品种和服务的竞争，由单个企业之间的竞争转换为企业与企业之间的形成的供应链之间的竞争。2 1 世纪的市场竞争将不是企业和企业间的竞争，而是供应链和供应链之间的竞争，任何一个企业只有从供应链管理的角度来考虑企业的整个生产经营活动才能够取得竞争的主动权，逐步提升企业竞争力，传统的管理模式已经凸现出各种弊端，供应链管理应运而生。生产和运输配送是供应链管理的两个重要环节，要使供应链达到好的运作绩效，生产和运输这两个环节必须集成在一起进行协调运作。当今社会，有许多企业都采取了按订单生产m a k e-t o o r d e r(M T O)的商业模式，尤其是半导体，电子产品类企业，这类企业采取了大规模客户定制的生产模式，产品的生命周期短，交付期也非常短，例如D e l l，因此这类企业的库存很少，或者没有库存。在这种面向M T O 生产的企业里，成本和客户服务水平是两个重要的考虑因素。由于库存很小，所以库存成本可以忽略不计。运输成本通常有固定成本和可变成本构成，因此运输次数和运输路线就决定了总运输成本。至于客户服务水平，提前期越短，客户服务水平越高。但是为了更短的提前期，运输次数就会增加，而这又会使运输成本增加。因此，在客户服务水平和运输成本之间找到一个平衡对于企业的整体运作绩效非常重要。要实现这个目标，就必须实现供应链的同步化运作，建立一种供应链的协调机制，在过去的2 0 年里，已经有大量文献在讨论这种协调性和集成性，不过研究的着眼点都是在战略层和战术层上【2 J，对于运作层面上的研究还是比较少，而现代管理讲究的是一种精细化管理，运作层面上的这种研究也非常重要，事实上，这种战略战术层面与运作层面上的集成性是个层级关系【3 1。前者是一第一章绪论个长期计划，后者是短期计划，是日常生产每天都要面对的问题。因此二者对于整个供应链的协调运作都是非常重要的。所以我们更需要具体地从运作层面上来研究生产和运输之间的这种相互制约关系。1 2 国内外研究现状在过去的2 0 年里，已经有大量的文献讨论了生产和运输的这种协调、集成性，不过研究的着眼点都是在战略层和战术层【2】，对于运作层面上的研究还是比较少，至于运作层面上的这种生产和运输集成调度还没有明确的定义，从文献上可以看出该集成调度是传统生产调度(S c h e d u l i n g)的一种延伸，在生产调度的同时考虑运输的因素。虽然生产调度问题和车辆路径问题已经得到了广泛而深入的讨论，例如P i n e d o(2 0 0 2)4 ，B r a m e l 和S i m c h i L e v i(1 9 9 7 1【5】；但是过去多年来很少有文章把这二者联系起来考虑。只是在过去5 年来生产和运输的集成调度问题才逐渐成为了一个焦点，C h e n(2 0 0 8)6】指出此类文章大多在近3 年发表。下面本文将简单地进行相关文献的回顾。最早在生产调度(s c h e d u l i n g)问题里面提及运输(t r a n s p o r t a t i o n)问题的是M a g g u 和D a s(1 9 8 0)口J，该文研究的是两台机器的f l o w s h o p 问题，即假设在两台机器之间车辆数量没有限制，工件在第一台机器加工完成后就可以立刻运送到第二台机器，目标是最小；此外，M a g g u 和D a s(1 9 8 1)【8】，K i s e e t a l(1 9 9 1)【9】，V a i r a k t a r a k s i(1 9 9 7)1 0 J 等人也讨论过相似的问题，但是以上这些文献考虑的都是车间内机器之间的运输问题。P o t t s(1 9 8 0)1 1 1，H a l l 和S h m o y s(1 9 9 2)1 2 1，W o e g i n g e r(1 9 9 4，1 9 9 8)t 1 3】等人考虑工件先在机器上加工处理然后运送到客户，目标函数采用传统生产调度的时间函数。文章假设有充足的运输车辆且每个工件被单独的即时运输，因此实际仍然是传统的S c h e d u l i n g 问题。H e r r m a n n 和L e e(1 9 9 3)1 5 1，C h e n ge t a l(1 9 9 6)1 6 1，C h e n(1 9 9 6)t 1 7 1，W a n g 和C h e n g(2 0 0 0)1 8】，H a l l 和P o t t s(2 0 0 3)1 9】目标函数虽然考虑运输成本，但是假设工件是即时运输的且每次运输成本是固定的，没有考虑车辆路径问题。L e e 和C h e n(2 0 0 1)2 0 1 讨论了两类含有运输的生产调度问题，第一类问题是考虑车间内机器调度问题，工件半成品在机器之间由运输车辆来运输。第二类问题是考虑车间机器和客户的生产和运输调度。两类问题都考虑了运输时间和运输容量有限。在第二类问题中，文献假设客户处于相邻位置，所以车辆运输的目的地是一个，运输时间是同定的，不涉及车辆路径选择问题，模型的目标函数是采用传统的生产调度模型中的基于时间的目标函数，不考虑运输成本。对其中一些多2第一章绪论项式时间可解或者拟多项式时间可解的模型文献给出了动态规划算法，对一些难解的问题，文献证明了其N P 类型。H a l le ta 1(2 0 0 1)t 2 1】考虑的模型中工件必须在一系列固定运输日期情况下运输。这两篇文章都没有考虑运输成本，也没有考虑车辆路径选择问题。C h a n g 和L e e(2 0 0 4)t 2 2 1 在L e e 和C h e n(2 0 0 1)t 2 0 1 的第二类问题基础上考虑T -r件尺寸不同，所以问题更加复杂，因为涉及装箱问题，文献对其中提到的三个模型给予了启发式算法，并进行了最坏情况分析。L ie ta 1(2 0 0 5)2 3 1，G e i s m a re ta 1(2 0 0 3)矧讨论的问题类似L e e 和C h e n(2 0 0 1)2 0】的第二类问题，L ie ta 1(2 0 0 5)2 3 1 文献假设只有一辆车辆可供使用，车辆容量有限，目标函数是时间函数，不考虑运输成本。文中讨论了三种情形：一个客户、两个客户、多个客户，对每个问题文献采用动态规划算法来求解。G e i s m a re ta 1(2 0 0 3)2 4 与L ie ta 1 相似，但是限制运输必须在一定的时间内进行。C h e r t 和V a r a k a r a k i s(2 0 0 5)2 5】研究了单机和多平行机下生产和运输的集成调度问题，文献假设车辆数量没有限制，并采用动态规划和启发式算法来求解相应模型。M o h a m m a de ta 1(2 0 0 7，2 0 0 8)t 2 6 1 1 2 7 1 对于单机环境下的批运送提供了一种分枝定界法，W a n g 和C h e n g(2 0 0 9)2 2 1 研究的成果与H a l l 和P o t t s(2 0 0 3)t 19】相似，不同之处是加入了运输时间，同样没有考虑车辆路径选择问题。另外一类相似的是供应链管理的相关文章，如C o h e n 和L e e(1 9 8 8)t 2 9 1，C h a n d r aF i s h e r(19 9 4)t 3 0 1，F u m e r o 和V e r c e l l i s(19 9 9)31 1，S a m i e n t o 和N a g i(19 9 9)t 3 2】以上这些存在的模型为p r o d u c t i o n i n v e n t o r y d i s t r i b u t i o n 模型，主要研究的是在供应链战略或者战术层面上的协调，对于车间的生产不做考虑，没有深入到运作层面上进行研究【2 2】【3 3】【3 4】。相对来说，国内对这方面的研究还比较少，而且对于生产和运输的协调研究大多集中在供应链协同的战略和战术层面上，对于运作层面上的协调研究比较少。近几年才出现这方面的相关研究。吴超超和顾幸生(2 0 0 4)p 5】研究的是包含工件生产和工件送货的单机调度问题，目标是寻找所有公共交货期和每个工件的送货时间使得工件所受到的惩罚值最小。袁晖(2 0 0 7)【3 6】指出近年来有研究将经典排序理论引入供应链管理中，提出供应链排序研究模型，但还没有形成统一的框架和定义，文章简单的介绍了这一领域的研究现状和发展前景。柏孟卓和唐国春(2 0 0 6)t 3 7 1，柏孟卓，陈峰和唐国春(2 0 0 7)1 3 8 与文献H a l l 和3第一章绪论P o t t s(2 0 0 3)1 9】类似，研究了平行机环境下生产和分批发送的集成排序问题，以工件的总流程时间作为排序目标，给出了相应的动态规划算法。汪松玉和陈友军(2 0 0 8)【3 9】在文献和C h a n g 和L e e(2 0 0 4)t 2 2 1 的基础上给出了一个时间限制条件，并且证明了最劣性能比可以改进，与文献C h a n g 和L e e(2 0 0 4)2 2】一样目标函数不涉及运输成本函数。关静和唐立新(2 0 0 6，2 0 0 7)4 0 4 1 研究的是钢铁企业生产和运输费用的协调调度问题，运输发生在机器加工之前，运输费用固定。李昆鹏，马士华(2 0 0 7)4 2】研究了航空运输背景下的消费电子生产和运输的协调调度，将该协调问题分为两个子问题，对航空运输子问题建立了整数规划问题，对单机生产调度子问题提出了基于到排序调度方法。李昆鹏，马士华(2 0 0 7)”3】在此基础上研究了并行机生产子调度问题，李昆鹏，马士华(2 0 0 8)m】研究由3 P L 主导的供应链中3 P L 协调调度问题。1 3 本文的研究思路和方法本文主要解决的问题是生产和运输的集成调度问题，传统的供应链管理中探讨生产和运输协调问题多数是在战略层面和战术层面上，对运作层面的集成调度问题研究较少。本文将传统的生产调度(s c h e d u l i n g)即排序问题引入到供应链管理中，与运输调度的车辆路径调度(V R P)结合在一起来考虑生产和运输的集成调度。生产调度就是决定订单何时加工、在哪个处理机上加工，订单的加工顺序怎么安排，运输调度就是确定进行多少次运输，每次运输的起运时间，运输路径的选择，每次运输装载哪些订单。本文研究对象包括运输资源无约束下的生产和运输集成调度问题及运输资源有限下的生产和运输集成调度问题。对运输资源无约束下的生产和运输集成调度问题先给出最简单的情形，即所有的订单属于同一个客户，所以这种情形下不涉及车辆路径的选择，问题相对简单，然后探讨的是多个客户的情形，此种情形涉及车辆路径的选择，相对来说较为复杂。然而实际上，运输资源往往是有限的，所以本文还研究了运输资源有限下的生产和运输集成调度问题，先假设最简单的情形，即假设只有一辆车辆可供使用，然后进一步研究多辆车的情形。最后，将传统的独立调度与本文研究的集成调度进行了比较，验证了集成调度的优越性。本文的研究方法主要采用传统的动态规划方法，之所以采用此种方法，是因为动态规划方法是现代管理中一种重要的决策方法，而且非常成熟，可用于解决排序等组合优化问题，另一方面由于本文探讨的问题是最近5 年来才比较关注的问题，所以着重点在于模型的探讨，通过对国内外研究文献的归纳总结中可以发4第章绪论现多数文献都采用过动态规划方法，所以本文将采用动态规划方法来求解模型。另外，本文用m a t l a b 进行了仿真实验。1 4 本文的主要工作本文共分六章，从生产和运输集成调度问题的背景论述开始，归纳总结了国内外对生产和运输集成调度问题的研究现状，阐述了生产和运输集成调度问题的有关理论，针对运输资源无约束和运输资源有限情形下的生产和运输集成调度问题，本文分别改进了两个模型，并且运用动态规划的方法进行了求解。进一步，针对传统的独立调度，提出了独立调度模型，并将本文研究的生产和运输集成调度模型与传统的独立调度模型进行了比较来研究了集成调度的优越性，最后对生产和运输集成调度问题的研究进行了总结和展望，具体研究内容如下：第一章，对本文研究的背景进行了阐述，同时归纳总结了国内外对生产和运输集成调度问题的研究现状；最后给出了本文的研究思路和方法。第二章，主要阐述了生产和运输调度问题的相关理论基础，由于是生产调度和运输车辆调度的一个结合，所以涉及生产调度和车辆调度的有关理论。对于生产调度的有关理论，主要阐述了生产调度问题的由来、生产调度的定义，生产调度问题的分类，以及生产调度的常用计算算法等内容。对于车辆调度问题，同样阐述了车辆路径问题的由来、定义，车辆调度问题的分类以及求解该问题的常用算法，这些都为后续对生产和运输集成调度问题的研究奠定了理论基础，是研究生产和运输集成调度问题的基本知识。本章第三部分主要阐述了生产和运输集成调度问题的由来，定义及分类，由于生产和运输集成调度问题近五年来才逐渐变成一个焦点，所以该领域还比较新，没有一个系统成熟的框架。所以本部分已开始就对该问题的定义进行了一个简单的阐述，为了便于以后进一步的研究，对生产和运输集成调度问题进行了分类。第三章，首先针对传统生产和运输独立决策的弊端提出了生产和运输集成调度问题，描述了该问题及假设条件，进而给出了本章研究的运输资源无约束下的生产和运输集成调度问题模型。针对该问题，改进了两个模型，第一个是单机单客户集成调度模型，第二个是单机多客户集成调度模型。对两个模型本章都给出了基于动态规划的求解方法，并且对每个求解方法给出了时间复杂度分析。为了便于理解，对每个模型的动态规划求解方法都给出了一个计算实验，并进行结果分析。且本章的最后针对口的两个极端情形口=0。口=1 分别给予了讨论，给出了求解的方法。第四章，在第三章的基础上对车辆可用数量资源进行了限制，引出了本章要第一章绪论研究的运输资源有限的生产和运输集成调度问题。本章描述了该问题背景及假设条件，进而给出了本章研究的运输资源有限下的生产和运输集成调度问题模型。针对该问题，提出了两种模型：一个是单客户单车辆集成调度模型；另一个是单客户多车辆集成调度模型。对两个模型本章都给出了基于动态规划的求解方法，并且对每个求解方法给出了时间复杂度分析。本章的最后针对口的两个极端情形口=0，口=1 分别给予了讨论，并且给出了求解的方法。第五章，主要是通过对生产和运输的集成调度与独立调度的比较，来研究生产和运输集成调度的优越性。首先，针对传统的将生产和运输两个过程进行孤立决策的过程抽象出一个独立调度模型，然后给出了一个顺序决策的方法来求解该独立调度模型。本章针对第三章、第四章提到的四个模型用独立调度的方法进行了求解，并将得到的结果与集成调度得到的结果进行了比较，通过比较可以验证集成调度的优越性，最后对这种优越性进行了仿真实验，通过大量的数据仿真可以得出随着权重口值，客户数量g，车辆容量c 的增大，这种集成调度的优越性更加明显的结论。第六章，对本文所做的研究工作进行了总结，同时提出了存在的问题和未来的研究方向。6第二章生产和运输集成调度的理论基础第二章生产和运输集成调度的理论基础2 1 生产调度的基本理论及方法生产调度问题的产生是随着制造方式的逐步演化逐渐发展起来的，当敏捷制造作为2 l 世纪企业的先进制造模式，综合了J I T、并行工程、精良制造等多种先进制造模式的哲理，其目的是要以最低成本制造出顾客满意的产品，即是完全面向顾客的。在这种模式下如何进行组织管理，包括如何组织动态联盟、如何重构车间和单元、如何安排生产计划、如何进行调度都是我们面临的问题。其中车间作业调度与控制技术是实现生产高效率、高柔性和高可靠性的关键，有效实用的调度方法和优化技术的研究与应用己成为先进制造技术实践的基础。制造系统的生产调度是针对一项可分解的工作(如产品制造)，探讨在尽可能满足约束条件(如交货期、工艺路线、资源情况)的前提下，通过下达生产指令，安排其组成部分(操作)使用哪些资源、其加工时间及加工的先后顺序，以获得产品制造时间或成本的最优化。在理论研究中，生产调度问题常被称为排序问题或资源分配问题。调度，即排序 4 5 (s c h e d u l i n g)问题是一类重要的组合最优化问题，它是利用一些处理机(p r o c e s s o r)、机器(m a c h i n e)或资源(r e s o u r c e)，最优的完成一批给定的任务(t a s k)或作业O o b)。在执行这些任务或作业时需要满足某些限制条件，如任务的到达时间、完工的限定时间、任务的加工顺序、资源对加工时间的影响等。而最优的完成指的是使目标函数达到最小，而目标函数通常是对加工时间的长短、处理机的利用率的描述。其一般情况是指在一定的条件下，为了完成各项任务，把一定数量的处理机和限制的资源分派给给定的任务，使目标函数达到最优。2 1 1 生产调度问题的分类处理机、任务或作业和目标函数三要素组成了排序问题，在排序问题中，处理机的数量和种类，任务或作业的顺序、到达时间、完工限制、资源的种类和性能等情况是错综复杂的。所以G r a h a m 等人首先使用三元组来描述排序问题的类型，使排序问题的表示更加方便。三元组记号由三个域组成：口l p l y，它们具有下边的含义。(1)口域表示处理机的数量、类型和环境，它可以为：7第一章生产和运输集成调度的理论基础只：m 个同速机级：m 个恒速机C：m 个处理机，流水作业瓯：m 个处理机，开放作业L：聊个处理机，异序作业艘：s 类处理机，柔性流水作业处理机的各种类型和环境总结如下：厂单处理机厂同速机I 同类机(平行机)_ 恒速机处理机类JL 变速机型及环境广同顺序作业(流水作业)I 多类机(车间作业异顺序作业1L 自由顺序作业(开放作业)L 柔性流水作业图2 1 处理机类型及环境(2)域表示任务或作业的性质、加工和限制，资源的种类、数量和对加工的影响等约束条件。它同时可以包含多项，可能的主要项是：0：任务有不同的到达时间，如果中不出现0，说明l=0，J=1，2，刀。s 肚：表示在有安装时f 司(s e t u pt i m e)，如果中不出现J 埔表示所有的安装时间为零。p 册矽：加工时间可中断，如果中不出现p 聊妒，表示加工时不可中断。p r e c，c h a i n s，i n t r e e，o u t t r e e：表示任务的相关性，分别表示一般优先约束、链、入树和出树，如果中不出现这些项，任务集是无关的。(3)，域表示要优化的目标函数，一般是：c 眦：时间表长q，_ c，：总完工时间，加权总完工时间k：最大延误，E _：误工任务数，加权误工任务数例如1 I 乃，p 唧I Mq 表示一个单机、可加工中断的排序问题，任务有不同的到达时间，极小化的目标函数是加权完工时间。第_ 章生产和运输集成调度的理论基础2 1 2 生产调度问题的算法从2 0 世纪5 0 年代起，调度问题的研究就受到应用数学、运筹学(最优化理论)和工程技术等领域科学家的重视，科学家们利用运筹学中的线性规划、整数规划、目标规划和动态规划等方法，研究并解决了一系列有代表意义的调度和优化问题。但是随着调度应用范围的扩大和实际问题变化，这些方法不是调度结果不理想就是难以解决复杂的调度问题。随着各种新的相关学科与优化技术的建立和发展，从2 0 世纪、8 0 年代初开始，在调度领域出现了许多新的优化方法，比如基于人工智能、计算智能和实时智能的各种智能调度方法，这些方法已经成为调度方法的主流。下面对这些方面进行分类介绍：(1)数学规划(精确算法)方法。数学规划方法(包括分支定界算法与动态规划算法等)源自于运筹学，目的是将调度问题通过条件简化，转化成熟悉的数学模型，并且采用整数规划、目标规划、动态规划以及决策分析算法来解决调度最优化或近似最优化问题。数学规划的优点是任务分配和排序的全局性比较好，一些约束条件可以得到很好的执行。但是，它属于一种精确调度方法，需要对调度问题进行统一的建模，任何参数的变化都会使得算法的实用性很差，而且对于所涉及的变量的数量也是有一定的自身限制的。冈此，对于复杂多变的系