（控制理论与控制工程专业论文）现代调度若干问题研究.pdf

南开大学博士论文 摘要 在经济全球化、贸易自由化和社会信息化的新形势下，传统的相对稳定的世 界市场逐步呈现出动态多变的特征，企业之间过去是在局部区域内进行竞争，而 现在是在全球范围内进行竞争；同行业之间、跨行业之间的相互渗透、相互竞争 日益激烈，因此，企业的经营战略发生了很大变化，以最低的成本、最好的质量、 最快的上市速度、最优的服务来满足不同顾客的需求，成为现代企业适应市场需 求、提高竞争力的关键因素如何作到上述几点呢? 调度在其中的作用是不容忽 视的，因为好的调度方案可以降低在制品库存，缩短产品的生产周期，提高生 产率，提高客户定单交付期满足率 另外，就调度本身而言，由于随着社会的发展，出现了许多新的问题，所以 传统的调度模型就不能满足人们的需求了，为了帮助企业适应新形式，解决新问 题，继续开展对调度问题的理论研究具有重要的现实意义基于此，本文在调度 方面作了如下工作： 一研究了三个单机维修调度问题： 本文研究的三个单机维修调度问题都是对以前模型的扩展，其中问题1 是将 以前文献研究的单机维修调度问题的目标函数一工件的完成时间和推广为加权 完成时间和来进行研究由于问题1 是强n p h a r d 的，所以本文对该问题给出了 三个启发式算法、一个遗传算法、一个综合遗传算法和一个分枝定界算法，并通 过仿真实验对这些算法进行了评价问题2 是在以前文献研究的单机维修调度问 题的目标函数一工件的完成时间和上加上一个使附加费用不超过事先给定的一 个常数这个约束米进行研究的，分两种情形进行讨论，剥第一种情形：工件的加 工不允许中断的情形给m 一个多项式复杂度的最优算法，对第二种情形：工件的 加工允许中断的情形，由于此时问题2 是强n p h a r d 的，因此本文首先研究了问 题2 的最优调度的性质，然后基于性质给出一个启发式算法问题3 是在问题1 的目标函数j ：加一项附加费用而得到的，它也是强n p h a r d 的，所以对该问题本 文给出一个基于局部搜索的启发式算法 摘要 二新建立并讨论了两个批处理机随机调度模型： 本文以超市( 配送中心等) 进货及半导体制造业中的老化( b u m i n ) 操作为背景 新建立了第一个批处理机随机调度模型，针对六个与交货期有关的目标函数得 到六个问题，分机器不允许空闲和允许空闲两种情况进行了讨论当机器不允许 空闲时，对这六个问题分别给出了与其等价的确定优化问题，针对确定优化问 题：研究了最优调度的性质对其中的第一个问题给出一个启发式算法，个整 数规划模型，对它的一种特殊情形给出了一个多项式时间复杂度的最优算法；对 其中的第二个问题给出两个启发式算法，对它的一种特殊情形给出了一个多项式 时间复杂度的最优算法：对其中的第五和第六个问题分别给出了一个多项式时间 复杂度的最优算法 当机器允许空闲时，对每个问题只给出了与其等价的确定优化问题，针对 确定优化问题研究了最优调度的性质 本文以每隔一段固定时间向某一货物集散地( 或超市、港口等) 发一辆车的货 物运输为背景新建立了第二个批处理机随机调度模型，针对六个与交货期有关 的目标函数得到六个问题，对这六个问题分别进行了讨论，给出了与其等价的确 定优化问题，针对确定优化问题研究了最优调度的性质，对其中的一个问题给出 了启发式算法，另一个问题给出了整数规划模型 关键词：调度；单机；批处理机；维护；遗传算法；分枝定界算法；启发式算法； 组合优化 南开大学博士论文 a b s t r a c t w i t ht h ea c c e l e r a t i o no fg l o b a le c o n o m y ，t h ed e v e l o p m e n to fi n t e m a t i o n a lf r e e t r a d ea n dt h ee x p a n s i o no fi n f o r m a t i o ni nt h es o c i e t y ，t o d a y sm a r k e t sa r e c h a r a c t e r i z e db yh i g hf l u c t u a t i o n si nd e m a n d ，a n dt h ec o m p e t i t i o nb e t w e e n e n t e r p r i s e sh a sb e e ne x p a n d e dw i d e l y i nt h ew o r i d t h es a m e p r o f e s s i o n s i n t e r p e n e t r a t ea n dc o m p e t em o r ei n t e n s e l y , s od ot h ec r o s so c c u p a t i o n a ll i n e s t h e r e f o r e ，t h ee n t e r p r i s e s m a n z l g e m e n ts t r a t e g i e sh a v ec h a n g e dg r e a t l y t h e e n t e r p r i s e sa r er e q u i r e dt ow i nm a r k e ta n dc u s t o m e r sw i t ht h el o w e s tc o s t ，b e s t q u a l i t y , f a s t e s tt i m et om a r k e ta n db e s ts e r v i c e ，w h e r es c h e d u l i n gi sn o tn e g l i g i b l e g o o ds c h e d u l i n gs c h e m e sm a yr e d u c et h ew o r k i n - - p r o c e s si n v e n t o r y , s h o r t e n p r o d u c t i o np e r i o d ，i m p r o v ep r o d u c t i v i t y , a n dm e e tt h ed e l i v e r yt i m e c l a s s i c a ls c h e d u l i n gm o d e l sc a nn ol o n g e rs a t i s f yt h ec u r r e n tr e q u i r e m e n t sa s m a n yn e wp r o b l e m sa p p e a r i th a st h ei m p o r t a n tp r a c t i c a ls i g n i f i c a n c et oc o n t i n u e r e s e a r c h i n go ns c h e d u l i n g , s oi nt h i sd i s s e r t a t i o nw ed ot h ef o l l o w i n gw o r ka b o u t s c h e d u l i n g ： i t h r e es i n g l em a c h i n em a i n t e n a n c es c h e d u l i n gm o d e l s t h r c es i n g l em a c h i n em a i n t e n a n c es c h e d u l i n gm o d e l ss t u d i e dj nt h i sd i s s e r t a t i o n a r ee x p a n s i o n so fa ne l e m e n t a r ym o d e l i nt h ef i r s tm o d e l ，w ee x p a n dt h eo b j e c t i v ef u n c t i o no ft h ee l e m e n t a r ym o d e lt o t 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 i ti sn p h a r di nt h es t r o n gs e n s e t h r e e h e u r i s t i ca l g o r i t h m s ，ag e n e t i ca l g o r i t h m ，az o n g h e g e n e t i ca l g o r i t h ma n da b r a n c ha n db o u n da l g o r i t h ma r eg i v e n ，a n dt h ec o m p u t a t i o n a lr e s u l t sa r ep r e s e n t e d i nt h es e c o n da n dt h et h i r dm o d e l s ，t h es t a r tt i m eo fm a i n t e n a n c ec a nb e p o s t p o n e d ，t h u st h ea d d i t i o n a lc o s t sa p p e a r i nt h es e c o n dm o d e l ，w ea d dar e s t r i c t i o no nt h eo b j e c t i v ef u n c t i o no ft h e e l e m e n t a r ym o d e l ，w h i c hr e q u i r e s t h a tt h ea d d i t i o n a lc o s t sc a nn o te x c e e da p r i o r - g i v e nc o n s t a n t w h e np r e e m p t i o n sa r ea l l o w a b l e ，ap o l y n o m i a lt i m eo p t i m a la l g o r i t h mi sg i v e n ； o t h e r w i s e i ti sn p h a r di nt h es t r o n gs e n s e p r o p e r t i e so ft h eo p t i m a ls c h e d u l i n ga r e d i s c u s s e da n dah e u r i s t i ca l g o r i t h mi sp r o p o s e d i nt h et h i r dm o d e l a d d i t i o n a lc o s t sa r ea d d e di nt h eo b j e c t i v ef u n c t i o no ft h ef i r s t m o d e l i ti sa l s on p h a r di nt h es t r o n gs e n s ea n dah e u r i s t i ca l g o r i t h mb a s e do nt h e p a r t i a ls e a r c hi sg i v e n i i t w os t o c h a s t i cs c h e d u l i n gm o d e l so fab a t c hp r o c e s s i n gm a c h i n e t h ef i r s ts t o c h a s t i cs c h e d u l i n gm o d e lo fab a t c hp r o c e s s i n gm a c h i n ei s e s t a b l i s h e db a s e do nt h eb a c k g r o u n do fs u p e r m a r k e t s s t o c k i n gw i t hg o o d sa n dt h e b u m i no p e r a t i o ni nt h es e m i c o n d u c t o rm a n u f a c t u r i n gi n d u s t r y s i xp r o b l e m sw i t h d i f f e r e n to b i e c t i v ef u n c t i o n sa r eo b t a i n e d t h ed e t e r m i n i s t i ce q u i v a l e n t sa r eg i v e n a n dp r o p e r t i e so ft h eo p t i m a ls c h e d u l i n gs c h e m e sa r ed i s c u s s e d w h e nt h em a c h i n e i d i ei s p r o h i b i t i v e h e u r i s t i ca l g o r i t h m s a r ep r o p o s e dt ot h ef i r s ta n ds e c o n d p r o b l e m s p o l y n o m i a lt i m eo p t i m a la l g o r i t h m sa r eg i v e nt os p e c i a lc a s e so ft h e m a n da l s ot ot h ef i f t ha n ds i x t hp r o b l e m s ；a ni n t e g e rp r o g r a m m i n gm o d e li sp r o p o s e d a b s t r a c t t ot h ef i r s tp r o b l e m t h es e c o n ds t o c h a s t i cs c h e d u l i n gm o d e lo fab a t c hp r o c e s s i n gm a c h i n ei s e s t a b l i s h e db a s e do nt h eb a c k g r o u n do fc a r g ot r a n s p o n e dt oac o l l e c t i o na n d d i s t r i b u t i o nc e n t e r ( o ras u p e r m a r k e t ，ah a r b o ra n ds oo n ) b ys e n d i n gav e h i c l ee a c h f i x e dt i m e w ea l s oo b t a i ns i xp r o b l e m sw i t hs i xo b j e c t i v ef u n c t i o n sr e l a t e dt o o b s d u ed a t e s t h ed e t e r m i n i s t i ce q u i v a l e n t so ft h e ma r eg i y e na n dp r o p e r t i e so fa n o p t i m a ls o l u t i o na r ed i s c u s s e d w eg i v eah e u r i s t i ca l g o r i t h mt ot h ef i r s tp r o b l e m ， a n ds o l v et h ef o u r t hp r o b l e mb yi n t e g e rp r o g r a m m i n g k e y w o r d s ：s c h e d u l i n g ；s i n g l e m a c h i n e ； b a t c h p r o c e s s i n g m a c h i n e ； m a i n t e n a n c e ；g e n e t i ca l g o r i t h m ；b r a n c ha n db o u n da l g o r i t h m ；h e u r i s t i c a l g o r i t h m ；c o m b i n a t i o no p t i m i z a t i o n 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本：学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：张酾擘 功口j 年r 月3 d 日 经指导教师同意，本学位论文属于保密，在年解密后适用本 授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下 内部5 年( 最长5 年，可少于5 年) 秘密1 0 年( 最长1 0 年，可少于l o 年) 机密2 0 年( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：张翮华 2 一o r 年f 月；d 日 南开大学博士论文 第一章引言 当前世界市场竞争空前激烈，而各种资源又很有限，企业如何有效地利用各 种资源，如何快速地响应市场，如何满足越来越挑剔、越来越个性化的客户的需 求，先进的管理手段是不可缺少的 调度是管理中的核心内容，好的调度方案可以充分利用人力、物力，财力， 比如在制造系统中，开发好的调度系统可以降低在制品库存，缩短产品的生产周 期，提高生产率，提高客户定单交付期满足率正因为如此，几十年来，调度一 度受到重视，企业也在研发实用的调度系统，这方面的理论研究也一直在进行， 而且随着时代的发展，不断有新的问题出现，从而不断给调度领域的理论研究带 来新的活力，因此调度领域的研究前景十分广阔 本文研究的几个调度问题，分别隶属于机器不可用情况的调度问题类和批处 理机调度问题类所以本章下面的内容这样安排：第一节介绍调度的内涵：第二 节对上面提到的两类调度问题的研究现状进行综述，第三节介绍调度问题的三 个新的方向，第四节介绍本文所做的工作 第一节调度的内涵 1 1 1 调度的定义1 】【4 】园 所谓调度就是将有限的资源在时间轴上分配给各种任务或活动的一个决策 过程，目标是优化一个或几个目标函数 这里的资源和任务是广义的，即可以呈现不同的形式，例如资源可以是工厂 中的机器、机场中的跑道、建筑工地的工人、计算机环境中的处理单元，甚至是 一个企业，还有物流中的各种运输工具以及公交车辆等等；任务可以是生产过程 中加工零件等的操作、机场中飞机的起飞和着陆、建设项目中的各个阶段、计算 机程序的执行、顾客定单的加工、各种商品的运输等等 调度存在于大多数生产制造系统和大多数计算机信息处理环境，除此之外 在运输和分配环境、农业、建筑业和服务业( 例如医疗、通信、银行1 还有供应链 等众多领域都存在调度 第一章引言 1 1 2 调度问题的分类2 儿6 】 调度问题分类方法有好几种，本文只按机器的数目，配置和工件操作对机器 的需求将调度问题分成下列几类： 1 单机调度：在问题中，只有一台机器可用，每个工件只需要一个操作 2 并行机调度：在问题中，有m 台机器可用( m ) - 1 ) ，每个工件只需要个操作 3 f l o w s h o p 调度：在问题中，有m 台机器可用( m ，1 ) ，记为 m ，m ：，m 。 每个工件需要m 个操作，且这些操作必须依次在机器 m 。，m ：，m 。) 上完成 4 j o b - s h o p 调度：在问题中，有m 台机器可用( m ，1 ) ，记为 m ，m 2 ，m ， 每个工件需要m 个操作，每个工件以各自特定的机器次序进行加工。 5 o p e n s h o p 调度：在问题中，有m 台机器可用( m 1 ) ，记为 m ，m ：，m ，) ，每个工件有r r l 个操作，工件依次在机器上加工的次序并 不指定可以是任意的 6批处理机调度：一台机器同时加工若干个工件，每个工件只需要一个操作 7多处理机任务调度：一个工件需要若干台机器同时对其进行加工 1 1 3 调度问题的主要研究方法砸1 1 1 3 1 计算复杂性 计算复杂性是7 0 年代在计算机科学中建立起来的个理论，它从算法的角 度定义了个闯题的“难”和“易”如果一个问题存在多项式时间复杂度的算 法，则认为它是容易解的；如果一个问题是n p 难的，就认为不存在多项式时间 复杂度的算法，也就很难在可接受的时间内求解 在调度研究中，一个问题的复杂度是人们首要关心的问题它不仅有其本身 的理论意义，而且对调度问题的解法也有指导作用如果证明了一个问题是_ 尸 难的，那么就不要费力去设计多项式时间的算法，而应该寻找其他途径去求解 当然了复杂性研究也是调度问题中比较困难的一个内容 对n p 难的问题还可分为强p 难和一般意义下p 难的这两种对一般意义 的p 难问题，可能存在伪多项式时间复杂度的算法，对强p 难问题，一般认为 不可能存在伪多项式时间复杂度的算法( 如果存在伪多项式时问复杂度的算法， 则等价于所有p 难问题都存在多项式时间复杂度的算法) 南开丈学博士论文 1 1 3 2 完全搜索算法 对一个 p 难的调度问题，得到最优调度主要依靠各种完全搜索算法，在调 度问题中，常用的完全搜索算法包括动态规划和分枝定界 动态规划在解调度问题中的一个成功应用是伪多项式时间复杂度的动态规 划很多文献表明，伪多项式时间的动态规划算法是解一般意义的p 难调度问 题的一个有力的工具 分枝定界是另一种隐含的完全搜索算法由于存储空间的限制，对强n p 难 的问题，动态规划很难适用，但对分枝定界算法，如果能找到好的下界计算公式， 还是能够解一定规模的调度问题 但是对绝大多数调度问题来说，用完全搜索算法在可以接受的时间内求最 优调度是不现实的因此人们降低了要求，希望能够用合理的时间来找一些近似 的最优调度 1 1 3 3 启发式算法 启发式算法是最常用的近似算法，它根据具体调度问题的性质，以及某些 经验规则，构造出一个可行的近似最优调度在f f d ws h o p 和j o bs h o p 问题中普 遍使用的调度规则方法也属于启发式算法一般来说，启发式算法的解与最优解 会有一个误差一个启发式算法的好坏可以通过对误差的分析进行评价，可以从 三个方面进行分析： 1 ) 最坏情况分析：最坏情况分析得到的是启发式算法的解相对于最优解的误差 的一个上界a ：设f ( h ) 是启发式算法得到的目标函数值，是最优调度的 目标函数值，如果f 一0 ，则有： 堕! 二：；。 f 1 2 1 随机分析：随机分析是利用概率论的方法对启发式算法的性能进行理论上的 分析，得到误差的分布，数学期望的概率特性 3 、计算机仿真：由于随机分析的困难性，人们通常借助于计算机仿真对启发式 算法的结果进行统计分析，这也是启发式算法评价中最常用的方法 在最优解难以得到的情况下，有时人们会在几种启发式算法之间进行比较， 有时也将启发式的解与最优解的下界进行比较 第一章引言 在三种方法中，最坏情况分析对启发式算法的性能给出了一个最低限度保 证，但其结果通常对应的是一些极端情况，对大多数问题，启发式算法的结果要 小于得到的误差的上界相比之下，利用计算机仿真得到的统计结果，是平均性 能的体现，更具有实际意义随机分析本来可以对误差得到理论上的保证但它 经常需要增加一些随机分布方面的假设，限制了其实际的应用价值 1 1 3 4 随机邻域搜索算法 随机邻域搜索算法包括近年来在优化算法方面被广泛使用的遗传算法、模拟 退火、禁忌搜索等这些方法都被用来解调度问题，而且得到了较好的效果 邻域搜索本来是调度问题的一个基本解法，其基本思想是对一个可行解进 行一个微小的变动，即认为是在当前可行解的邻域内找另一个较好的可行解上 述随机邻域搜索算法在调度中的应用，都是在这种邻域搜索中，用不同方式增加 了随机搜索能力而且还可以将不同的搜索方法结合起来，得到混合搜索算法 1 - 1 3 5 人工智能方法及其它 由于调度问题的复杂性，在实际系统中，人们还用神经网络，人工智能，专 家系统等解决调度问题，也都取得了一些成果 以上从调度的定义、调度问题的分类以及调度问题的主要研究方法三个方面 给出了调度的内涵，这方面比较典型的著作有【1 。【3 南开大学博士论文 第二节两类调度问题研究概况 1 2 1 机器不可用情况的调度问题研究概况 所谓机器不可用情况的调度问题，就是要考虑实际生产中可能出现故障的 情况也就是说，调度中必须考虑到机器的故障和维修问题这类调度问题的特 点是突破了传统调度问题中的“机器在任何时刻都是可利用的”这一基本假设， 使问题更加接近实际根据所采用的模型的不同，一般可以把这类问题即有机器 故障和维修的调度问题分成两种类型【7 1 ： 1 基于随机模型的有机器故障和维修的调度问题”1 该种问题的特点是将机器的可用( 正常运行) 状态和不可用( 故障和维修) 状态 采用一随机过程来刻画，并在一定的随机性假设下，来研究问题的调度方案如 果随机性假设合理，那么这类模型比较符合工程实际，但是需要应用概率和随机 过程的方法，其分析过程往往比较复杂 2 基于确定性模型的有机器故障和维修的调度问题 7 1 这种问题的一个背景是机器的预防性维修问题，通常维修计划是事先决定 的( 当然最近也有模型将何时进行维护也作为决策变量) ，且一般具有周期性，即 按一定的时间间隔对机器维修一次，在维修( 如设备的检修、设备的定期加油等) 期间机器不可用，在其它期间机器总是可以用的它的另一背景是由于加工过程 中插入其他特定任务的需要而造成的“虚拟性维修问题”，例如在某些指定的时 间内机器必须转而进行其他加工任务( 如加工上一班次所未完成的工件、一些特 殊紧急的加工等) ，在此期间机器被认为是处于“维修”状态 基于随机模型的有机器故障和维修的调度问题的研究始于上个世纪八十年 代，因为这方面最早的一篇文献是由g l a z e b r o o k 8 1 于1 9 8 4 年给出的【9 】，从那时开 始陆续有这方面的文献发表，例如文献【1 0 - 【3 8 】 基于确定性模型的有机器故障和维修的调度问题的研究也始于上个世纪八 十年代，文献f 3 9 1 应该是这方面最早的一篇文章【加】下面将这方面的近期文献作 以归类介绍 文献 4 1 4 2 是关于荦机环境的：文献 4 3 卜 5 2 是关于两机f j o w s k o p 环境 的；文献 5 3 是关于两个平行机环境的； 5 4 是关于二机o p e n s h o p 环境的，这些 文献都只考虑一次维护活动文献 5 5 考虑单机情形且带有多次维护活动；文献 5 6 足关于两个平行机环境的： 5 7 卜 5 9 是关于两机f o w , s 1 o r ) 环境的，这四篇 一一 笙二兰! ! i 文献中的两台机器在加工工件时各有一个区间不可用文献 6 0 研究多个平行机 情形，其中有一些机器在加工工件时只有有限个预先指定的可用区问以上这些 文献都假设维护活动是事先已知的，是固定的 文献 6 1 6 2 是关于二机f l o w s h o p 环境的，其中第二台机器在加工工件时有 无限个不可用区间 文献 6 3 是在平行机环境下讨论的，机器在加工工件时都只有一次维护活动 但维护活动的开始时间是不固定的( 在一个时间窗内变化) ，文献 6 4 6 5 考虑多 机情形，每台机器在加工工件时各有一次维护活动，且维护活动的开始时间也是 在一个时间窗内变化 文献 6 6 卜 6 8 都是统一考虑了工件调度与机器的维护活动，这一点更重要 因为这样制定的调度方案有时比将维护活动固定起来 4 1 一【6 。 更有效，而且文 献 6 7 和 6 8 还考虑了如果推迟维护活动对工件的实际加工时间所带来的影响 文献 4 0 ， 6 9 ， 7 0 是这方面的三篇综述性文章 由以上这些近期文献可知，这方面的研究还是比较活跃的 1 2 2 批处理机调度问题研究概况 批处理机是指可同时加工多个工件的一类机器批处理机模型广泛存在于 制造系统中，典型例子包括加热炉( 机器) 对若干工件为一批的加热处理( 批处理) ， 半导体、集成电路制造中的各类批处理等交通系统中的车辆，电梯等都可以看 成批处理机 批处理机调度问题从模型上来看也有确定模型的和随机模型之分 确定型的批处理机调度问题的研究始于上个世纪八十年代，i k u r aa n d g i m p l e 7 1 】发表了目前公认最早的一篇批处理机调度论文，之后有关批处理机调 度的论文陆续发表，逐渐引起了人们的兴趣w e b s t e r db a k e r 7 2 1 综述了关于批 处理机调度的研究情况 在确定型的批处理机调度问题中，根据批的组成和批加工时间的确定，可将 其分为三类：在i k u r aa n dg i m p l e 7 1 】研究的问题中，每个工件都可以和其它任意 工件作为一批加工，且批加工时间是确定的，与工件无关称之为最经典的批处 理机调度模型，这也是最简单的模型l e ee ta l 7 3 】提出了在半导体生产中老化 ( b u r n i n ) 操作的批处理机调度模型：每个工件有不同的加工时间，而整个批的加 工时间等于该批中最大的工件的加工时间u z s o y 7 4 i 讨论了多类型工件的批处理 南开大学博士论文 机调度问题：工件按类型分类，只有同类的工件才能在同一批中加工，批加工时 间取决于工件的类型1 6 j 关于确定型的批处理机调度问题，文献 2 对2 0 0 1 年以前的文献进行了回顾 近期文献有 7 5 】- 【9 4 】 从这里的讨论可知，随着时代的发展，不断地出现新的问题，调度也紧跟时 代的步伐，相应给出新的调度模型，来适应时代的需要 随机型批处理机调度问题的研究要起步的早一些，因为在排队论中将这类 问题称为批服务序n ( b u u c s e r v i c eq u e u e ) l b q 题，从上个世纪七十年代就开始对其 进行研究【9 5 】一【9 7 1 在排队论中对批服务序列的研究可分为两种类型，一种是研究这种服务系 统的性能【9 5 】1 1 2 0 1 ，一种是研究如何去控制这种系统，以使给定的目标函数最优 【1 2 1 】【”小从文献上看，这方面的研究也正在进行，而且模型中考虑的因素在增多 文献 1 3 5 用随机调度中的研究方法，即将工件的加工时间视为随机变量， 在假设加工时间可以随机排序“的条件下，极小化所有工件的最大完工时间 c 和所有工件的总的运行时间( f o w t i m e ) 的数学期望，这样处理的原因是在 制造系统中，工件的加工会受到各种随机因素的干扰，而使加工时间呈现不确 定性，因此将加工时间视为随机变量，给出的调度方案应该更加可行 7 第一章引言 第三节调度问题的三个新的方向 随着时代的发展，现代企业所面l 临的生产环境和市场环境与以前相比发生 了巨大的变化，比如产品的生命周期在缩短：由于用户需求日益个性化，多品种 小批量生产比例增大；企业由传统的基于库存的生产变为基于定单的生产企业 现在面临的是动态多变的全球市场，现代企业竞争不是单一企业与单一企业间 的竞争，而是一个企业供应链与另一个企业供应链之间的竞争在这种大市场大 竞争的环境下，企业需要新的管理理念、先进的管理模式和管理技术作为支撑 这就给作为管理核心内容的调度带来许多值得研究的新问题，下面就给出三例 1 3 1 批交付调度问题研究概况 在传统的调度模型中，一般都只考虑对工件的加工进行调度而忽略了同时 对工件的交付进行调度这一环节，实际上，工件的交付费用也是生产费用的一 部分，这是因为在工厂中，发货费用是库存运做费用的一个重要因素，因此同 时考虑调度工件加工及调度工件交付的调度问题更符合生产实际由于在实际 中，工件的交付一般是成批进行的，这样显然会节省交货的启动费用，所以将 这种统一考虑调度工件的加工和调度工件的交付的调度问题称为批交付调度问 题 目前已有少量文献对这方面进行了研究 文献 1 3 6 给出这样一个模型：n 个工件在一台机器上加工，工件的加工不 允许中断，工件有一个公共的交货期( d u ed a t 由，目标是极小化延误工件数的 加权和及工件的提前和延误惩罚，这里的延误工件数的加权和指的是每有一个 工件延误就会得到惩罚，该惩罚是固定的，与延误的工件及该工件的延误时间无 关，在该惩罚项就包含延误工件的交付费用这是第一篇在调度中考虑工件交 付费用的文献“ 但真正第个统一考虑调度工件的加工( 确定工件的加工次序) 和调度工件 的交付( 确定哪些工件在同一批，它们一起被交付) 的文献是 1 3 7 ，在这篇文献 中，n 个工件在一台机器上加工，工件的加工不允许中断，且所有工件的到达时 间为零 工件被分成几个不同的批次，每批工件有一个交货时间( d e l i v e r yt i m eo r d e l i v e r yd a t e ) ，该时间实际上是该批中最后一个工件的完成时问，在该时刻 这批中所有工件一起被交付 8 南开大学博士论文 如果一个工件在它所在的批的交货时间之前加工完，那么它就会占用库存， 由此而产生费用，将此费用定义为该工件的由于提前所产生的费用，简称提前惩 罚费用，它等于该工件所在批的交货时间( d e l l v e r yt i m eo fd e l i v e r y 幽t p ) 与 它完成时间之差的一个倍数 很显然每交付一批工件都会产生费用，这里的费用包括出车等费用，因此 这篇文献中将由交付所产生的总的费用定义为批数的一个非负的函数 需要同时做出下列决策：确定批数、将工件分配到各批，以及确定每批中工 件的加工次序，以使所有工件的加权提前惩罚费用与所有交付费用之和最小 文献 1 3 7 讨论了该问题的复杂性，证明了它是一般意义下的舻动甜d 问题 并对。种特殊情况：所有工件的提前惩罚费用都相同的情形进行了讨论，说明了 此情形是多项式可解的 文献 1 3 8 讨论的问题与 1 3 7 相同，在其中给出了求解问题的伪多项式时 间复杂度的动态规划算法，并对所有工件的加工时间都相同的情形进行了分析， 指出了这种情况是多项式可解的 文献 1 3 9 的模型是文献 1 3 7 模型的扩展，在文献 1 3 9 的模型中，只是将 1 3 7 中的目标函数作了修改，即将由工件的提前所产生的惩罚费用定义为该工 件提前量的一个一般的非负函数( 文献 1 3 7 中的是工件提前量的一个常数倍) ， 该文将问题转化为一个传统的平行机调度问题，利用传统的平行机的复杂性结 果和算法解决了问题 文献 1 4 0 研究的问题与文献 1 3 7 稍有不同，在该文献中，n 个工件在一台 机器上加工，工件被分成若干批，机器在加工相临批工件时有一个常数切换时间， 将各批最后一个被加工的工件的完成时间定义为该批的交货时间( d e l i v e r y 出t o 。，d e i v e r yt i r e ) ，各批工件在该时间被一起交付，若一工件的完成时间 小于它所在批的交付时间，就会出现一个提前惩罚费用，该费用等于这个工件提 前量的一个常数倍：欲同时做出下列决策：确定批数、将工件分配到各批以及 确定各批中工件的加工次序，目标是极小化所有提前惩罚费用与平均批交付时 间之和 文献 1 4 1 的一1 j 作与以上的工作有显著不同，在该文中，n 个工件在一台机 器上加工，工件的加工不允许中断，所有工件的到达时问为零。所有工件有 个公共的交货期( d u ed ar e ) ，如果一个工件的完成时间小于或等于公共交货期， 那么它就在公共交货期时刻被交付，否则就称它为延误工件，它或者在完成加 工后立即被交付，或者在加工完成之后进行等待，与在它之后被加工的工件加工 9 第一章引言 完之后一起交付，将该时间称为该工件的交货时间( d e l i v e r y 如t eo rd e l i v e r y t i m e ) 若一个工件的完成时间小于它的交货时间，就会出现一个提前惩罚费用， 它等于该工件的提前量( 该工件的交货时间减去它的完成时间) 的一个倍数，对 所有延误工件都有一个延误惩罚费用，它等于该工件的延误量( 该工件的交货时 间( d e l i v e r yd a t e0 2 - d e l i v e r yt i m e ) 减掉公共交货期( d u e 幽r e ) ) 的一个倍数， 若一个工件在它加工完之后立即被交付，就会产生一个交付费用，设每次出现的 交付费用都相同，目标是极小化所有提前惩罚费用、所有延误惩罚费用及所有交 付费用之和文中为一种特殊情形提供了一个伪多项式时间复杂度的动态规划 算法 文献 1 4 2 证明了文献 1 4 1 的问题是强胪书a ，d 的 文献 1 4 3 是文献 1 4 1 的扩展，它将文献 1 4 1 中工件的公共交货期( d u e d a t e ) 视为决策变量，其余的条件不变，由此产生一个与公共交货期( d u ed a t e ) 有关的费用将公共交货期( d u e 出e ) 视为决策变量的原因是，一般来说，工件 的公共交货期( d u ed 3 t e ) 是企业的营销部门与客户协商( n e g o t i a t i o n ) 得来的， 若企业给出的公其交货期( d u ed a t e ) 比较晚，那么要想不失去客户，就得降低产 品的销售价格作为补偿，这时企业就需要对公共交货期( d u ed a t e ) 进行决策，以 确定一个双方都能接受的合适的公共交货期( d u ed a t e ) ，使企业即不失去客户又 使自己损失最小，为达到这个目的，文献将公共交货期( d u ed a t 曲视为决策变量 并将其带来的费用加到目标函数上去于是文献 1 4 3 模型中的目标函数比 1 4 1 模型中的目标函数多一项由公共交货期( d u ed a t e ) 带来的费用，它等于公共交 货期( d u e 幽e 曲的一个常数倍，而且假设每个工件的单位提前惩罚费用相同，每 个工件的单位延误惩罚费用也相同文中说明了此情形是多项式可解的 文献 1 4 4 的模型与文献 1 4 3 的模型稍有不同，n 个工件在一台机器上加 工，工件被分成若干批，将各批最后一个被加工的工件的完成时间定义为该批的 交货时间( d e l i v e r y 出t eo fd e l i v e r yt i m e ) ，所有工件有一个公共的交货期( d u o 如f 曲，如果工件在公共交货期前面完工，称作提前完工，将会受到提前惩罚， 在公共交货期时间按照一批送货：如果工件在公共交货期后面送货，称作拖后 完工，将会受到拖后惩罚，并且需要支付相应的库存费用，将根据情况进行批 量送货 在文献 1 4 4 中，也是将公共交货期( d u ed a t e ) 视为决策变量，与文献 1 4 3 i 同的是1 ) 未考虑由公共交货期( d u ed a t 曲带来的费用：2 ) 将在公共交货期前面 完工工件的提前惩罚费用( 公共交货期( d u e 幽r e ) 与该工件的完成时间之差的常 数倍) 与在如果工件在公共交货期后面送货的工件的提前惩罚费用( 该工件的交 1 0 南开大学博上论文 货时间与该工件的完成时间之差的常数倍) 进行了区别，将后一项视做支付的库 存费用，二者的单位惩罚费用不同该文中确定了公共交货期( d u ed a t e ) ，并给 出了相应的排序 以上讨论的都是单机的情形，只有文献 1 4 5 考虑了平行机的情形，其中讨 论的模型是这样的：n 个工件在m 台相同的平行机上加工，工件的加工不允许中 断，且所有工件的到达时间为零工件被分成几个不同的批次，每批工件有一 个交货时间( d e l i v e r yt i m e0 1 d e l l v e r yd a t e ) ，该时间实际上是该批中最后一 个工件的完成时间，在该时刻这批中有工件一起被交付于是一个工件的运行 时间( f l o wt i m e ) 就等于它所在批的交货时间( d e l i v e r yt i m eo rd e l i v e r yd a t e ) 所有批的交付费用定义为批数的一个非减的函数需要同时做出下列决策：确 定批数、将工件分配到各批以及确定每批中工件的加