单机带有不可用区间的批排序问题

1、单机带有不可用区间的批排序问题本章将批运输问题和机器带有不可用区阖的问题结合在一起研充极小化总流水吋何及运输的用z和.该问題不仅对实际生产有指辱意义，而且能够丰富生产物流调度优化理论.只百一定的理论价值”在很赛实际生产中工件一般在处理机上加工后,若干个放在一起形成一批.用车等工具运走，转2洽客户于中.才算加工完.我们这样的问题称为批运输问題"对F单机问题.闵机器在加工过程中发生故障或维修等原因而产生可用件限制这里I：件若披中斷加I：迖时必彷酋新加I：的苗阮称为不叩恢址的怙况我们这里讨论的都为不可恢复的情形.£禺为机器不可用区间.?；表示不可用区创的开始时阿，7袞示不可用区何

2、的终1一时间"在这一模型下.忒讹讨论了在机器上任意时间段为不可用区间的情况分别给出了极小化总流水时*I及运输a用Nf打时魁机问题的拟务项式的动态规划算法和算法的复杂性：幷用具体的数值例子表明了算法的有效性.本章览二节甘该问題进厅了描述：第.廿研丸了檢小化总流水时间及运输躋用z和的带有不可用区问的批运输排序单机问题的性质给出了某类廉优解应满足的条件：第四节给出了解决此问JH的Kt多项试时间的动态规创算注及算法的更杂性分析：第血节洽出了谏问题的数值例子：第穴节是对泰锻的小结.问题描述fin个匸fhflI11Ife为J=M丿>在一台机器上加工.工fh的加工时闸为卩.ck¥t

3、n-i的完工时间；所右工件都在零时刻圧可用的.并卫需划分若干个批进疔运输匸尺表示批数.则1<R<n目我示第批商表示批y屮的工件歡所有任一批的工件被一起运输给客户，故批的交»期等F批龙工时何用p&小*的交货期阖此一个工件的流K时何尊于它所在扯的交货期*F为匸件的流木时间"运输费用是关F批数的不減甫数、用旳简表示，H标是安井工件的加工顺序和甘批来檢小化总流冰时闻与运输聘用z和，即刀二巧十迅代八H标刚数用G表示.对F任意一个序列JT它的I标宓数值为GU）FE+疣破儿炷H标儒戳为总流水时何耳批运输跋用Z和的单机问題,用三磬獄長示注wi记为l,hbd,RSU工行+

4、a(R)其中h表示带有不可用区间限制的问题:M为批运输问题的缩写：U表示批数R的上界.三、最优解性质对F工件是不可恢复的极小化总完工时何的单机排序问题，Adiri等卩引指出苴问题是NP唯的.那么对于LI标曲数是总流水时何的问题，至少为NP难的。故可得到下而结论。定理2.3.1问题：Lh'bd.RWLH工F,+a(R)至少是NP堆的。对于单机带冇不可用区间LI标怖数为Z_F户a(R)的批运输问题(如图1所示)，我们可得如下的晟优解的性质门T2图1何题l./»lbd.Ml£+a(R)的例图引理2.3.2问题：lhlbd、R£UlR+a(R)一定存在一个满足下列

5、条件的最优解n=(B,.B)(1) 在7；前和近后的工件分别按SPT规则排列;(2) E包含所仔在(D“Dl之间完工的工件.证明首先证明(1)，即在7；前的工件按S7T规则排列。假设在最优序列;/中，不失一般性，存在两个工件厶和丿，其中丿，紧跟着厶加工，并且Pt>pt按照£与厶是否在同一批中，我们分两种情况来讨论。i)丿,与丿,在同一批中。由F同一批屮工件的完工时间相同，也就是说它们的流水时间也相同，所以交换厶与丿，加工顺序，设得到的新序列为兀，则G(/f)=GU)。ii)厶与人不在同一批中。设厶在中加工，打在B屮中加工.场的开始加工时间为f,B屮的开始加工时间为f+三几则有F

6、、=C、=C執="工人和F)=C)=C魯=f+W几+Z几.5*-=45“交换人与丿的加工顺序，其余工件不变.设得到的新序列为；：，那么此时工件丿和厶的流水时间分别变为<,=C?=CBt=f+工几+鬥F、=C：=C怙=1+工pk+工几+门"+工几+工几。其它批的完工时间不变.则Hc=C；:(11pt>P)可知.C：<CJ其余批不变。即第/批前的工件流水时间不变.第/批的工件的流水时间减少.笫f批后的工件流水时何也不变.从而GE>Gg所以与假设於为最优序列矛曲。则存在一个最优序列”,使得7；前的工件按SPT規则排列。同理可证在兀后的工件也满足SPT规则排

7、列.从而存在一个晟优解兀满足在7；前和耳后的工件分别按SPT规则排列。下而用反还法证明(2)不失一般性.设最优序列才中T件的加T顺序为丿叶彳2|，丿，其中丿小表示兀中笫j个加工的工件0批的交货期为D；,则D；<.<D；V.<D；假设存在一个工件/(”满足ZVi<5、(<D；且不在Bi批中加工,由于工件/“在色批之前没有完工,则有F*>D；若把工件乙放在场批中，设为新序列打，具它工件的加工顺序与所在批不变，则I；=D；所以F&>Fj又因为G(Z)«/；+&(/?)和5穴)=工人+£”+&(/?),从而G(”)&

8、gt;G(/r)与兀为竄忧排序矛盾.在其它批中的壬解按照同样的讨论,我们可以证明存在个最优排列，使得所有批都是由一些连续完工的工件组成的。在任意的用优排列中.因为所有在。处完工的工件，都可以被分到色中，/=1，./?»约应包含在(D“叩完工的所有工件。rti同批中的所仃工件的流水时间相同，我们可以得到下面的结论。引理对于问题：IMIM.RSUI工巧+a(R)任何一个用优序列，每一批内的工件加工顺序是任意的。四、动态规划算法及算法复杂性的分析由引理2.3可知，对于问题：M】bd.R<UF”+a(R),存在最优排序，H中排在7；前和T:后的工件的加工顺序都按SPT排列。那么我们可以

9、将工件分成两部分，分别在7；前和7；后.使得每一部分工件都按SPT列，从而得到用优排序。拥此，我们可以建立求解这个问题的动态规划算法.在下述动态规划算法中，设p=Zj假设工件土珀己排完，定义比(jg厶Q，卩为己排列工件£到的晟小总流水时何，其中排在£前的总加工时间为/,(/,<7；),排在石后的总加工时间为2,则排在兀后最后一个工件的完工时间为G+7；,色的交货期为D,t于是，工件Jl-J/的总流水时何分以F两种情况:(1) 当工件打排在0,7；区间内有HJDi"DJmHJj7山-p户.D、,DJ+F)其中F产叩1儿2几几=0=1,/?：(2) 当工件人排在

10、耳后，有,DJ=H小j一山人一p丿入、,DJ+F)其中冇=。I叽v'+兀M=OJ=1,R由以上分析可得动态规划算法如下.拟食项式动态观划算法2.1(DP2.1)：(1)把工件按SM序編号.使戸S化S几.(2)初始条件SdQD、，Dk)o如杓=(“8其它(3) 按递归方程:HMQL、S、DJ=min4Hj-L.一p严QD、,.rDJ+F尸其中巧=卩|/儿<片卩口=0/=1，,RHJjL.心p户D、F”其中巧DlDJl<t1+T1<DJD.m,R这里/=0nJ=01J,=0.,P.1片=I片、+1,石+P/=1,/?Q=。(4) (T=min少I)+a(R)利用反向追踪得

11、到最优井用及分引理2.34动态规划算法DP2.1的时何貝朵性为O(MT7；(7；+P)i)证明在状态(从，&4，.0下Hjwp.,Q)中j的取值为1,2.,/：/,的取值为0到7则4在片取定之后便可确定;2到D*可取到的最大值都为T2+P,R=l.,U:从而递推关系式的不同状态尺=1，.U至筝仃叭(丁广P屮对于每个状态，递推关系式的右边可以在0()时间内被计算。因此，整个的计算复杂性为O(M/S+Pf)。五、数值例子对于问题：工厅+"(/?)给出以下数值例子.例2.1丿=人厶厶a(R)=8Rp=(1246).7；JJ=5,7t/=4.解当R=1时，a(i.i()5)=i5/1

12、(2J,2J5)=nnn/1(lAOJ5)+Fr/1(L-L2J5)+F2=min15+15,oo=30"】(35215)=min"2丄25)+化,“J2.5-2J5)+化=min30+I5,oo=45”i(4.5&15)=minWj35215)+耳/(3-1&+耳=min45+15.oo(=6()G(/r；)=60+8=6S塔R=2时，(2丄2,515)=5+15=2()”J2,3.(),3,17)=6比(3.525J5)=minH2(2丄2.515)+化比(25.2.515)+代=min20+5.8=25H2(3,3,4,3=rl7)Hmin(20/.3

13、2,4-7),+F(：=min*6+17,ooj=23円2(4,5,8,5专15)屮in(3十氏尹»45)，+F(：=min25+15a=40比(4,3,10.3=U7|Hpiin(3+冲.7)7J+Hp=min：23+17.x)=4()G(/r；)=4016当R=3时，"(3.3.4.3.11.17)=17,(丄95)=19/J3.5.2.5.9,15)=19，人(4.3.10,3,11.17)=min"亿(3,34.3,11.17)+耳.比(3,-3.10.3,11.17)+化=min：17+17,8=34Hj45&l915)=min"j35295)+F"j3.-1&1,95)+巧=min卩9+15,8=34円3(4,5,8,5,9,15)=min円3(3,5,2,5,9,15)+巧出3,-1,8,5,9,15)+化=min19+15,00=34G(/r；)=34+24=58当R=4时.乞（4,5&1,5,9,15）=30G（/r：）=30+32=62因此.我们可以得到用优解G（/r）=minG（/r；）,G（/r；）.G（/r：）G（/r；）=min6&