工件a

第42卷第2期2014年4月福州大学学报(自然科学版)JournalofFuzhouUniversity(NaturalScienceEdition)Vol.
42No.
2Apr.
2014DOI:10.
7631/issn.
1000-2243.
2014.
02.
0265文章编号:1000-2243(2014)02-0265-05机器具有不可用时间间隔的两机无等待流水车间调度问题的求解性质陈可嘉,王潇(福州大学经济与管理学院,福建福州350116)摘要:研究工件具有无等待约束,并且只有一台机器具有不可用时间间隔的两机流水车间调度问题.
文中给出使用GGA算法得到问题最优解的条件,并证明问题的复杂性,分析将GGA算法作为问题启发式算法的最坏性能比范围.
关键词:两机流水车间调度;不可用时间间隔;无等待;GGA算法性;最坏性能比中图分类号:F406.
2文献标识码:APropertiesofsolvingtwo-machineno-waitflowshopschedulingwithanunavailableintervalCHENKe-jia,WANGXiao(CollegeofEconomicsandManagement,FuzhouUniversity,Fuzhou,Fujian350116,China)Abstract:Inthispaper,thetwo-machineno-waitflowshopschedulingproblemwithanunavailableintervalisstudied.
TheoptimalityconditionsofsolvingtheproblembytheGGAalgorithmarepresented.
Thecomplexityoftheproblemisproved.
Theworst-caseperformanceratiooftheGGAalgorithmasaheuristicisanalyzed.
Keywords:two-machineflowshopscheduling;unavailableinterval;no-wait;GGA;worst-caseperformanceratio在实际生产中,经常会对工件的加工过程以及机器的使用条件有特殊的要求.
无等待流水车间调度问题就是工业生产中常见的一种调度问题,比如,化学药品加工行业中,为了避免药品挥发等问题,药品在加工过程中不允许等待,必须连续进行.
与此同时,为了尽可能保证机器的正常运作,需要对机器进行定期的预防性维护,使得机器在某些时间段内处于不可用状态,这就产生了机器具有不可用时间间隔的调度问题.
工件具有无等待约束并且机器具有不可用时间间隔的流水车间调度问题广泛存在于企业的生产运作中,有必要对其最基本的两台机器的情况进行研究.
对于工件和机器都没有约束的两机流水车间调度问题,文献[1]提出了著名的Johnson算法.
当工件具有无等待约束时,文献[2]给出了最大完工时间最小化目标下两机无等待流水车间调度问题的多项式最优算法,简称GGA算法(gilmoreandgomoryalgorithm).
文献[3-5]分别对目标函数为最大延误时间最小化、总流程时间最小化、总完工时间最小化的两机无等待流水车间调度问题进行了研究.
考虑工件具有无等待约束并且机器具有不可用时间间隔时,文献[6]设计了最大完工时间最小化目标下,机器具有不可用时间间隔的两机无等待流水车间调度问题的启发式算法.
文献[7-8]讨论了两台机器不可用时间间隔存在重叠情况下无等待流水车间调度问题.
文献[9]研究了被不可用时间间隔中断的工件是可恢复(resumable)、部分可恢复(semi-resumable)和不可恢复(nonresumable)三种类型的两机无等待流水车间调度问题.
文献[10]分析了工件具有不同到达时间,并且机器具有重叠的不可用时间间隔的两机无等待流水收稿日期:2012-12-31通讯作者:陈可嘉(1978-),教授,研究方向:工业工程,系统工程,E-mail:kjchen@fzu.
edu.
cn基金项目:国家自然科学基金资助项目(70901021,71201033);教育部新世纪优秀人才支持计划资助项目(NCET-11-0903)福州大学学报(自然科学版)第42卷http://xbzrb.
fzu.
edu.
cn车间调度问题,给出了分枝定界算法.
从已有研究来看,探讨机器具有不可用时间间隔的两机无等待流水调度问题的文献较少,对问题求解性质的研究还不够充分.
为此,本文针对工件具有无等待约束并且只有一台机器具有不可用时间间隔的两机流水车间调度问题,分析在哪些条件下使用GGA算法可以得到问题最优解;问题复杂性如何;当GGA算法作为问题启发式算法时,最坏性能比是否存在上界.
1问题描述及符号定义机器具有不可用时间间隔的两机无等待流水车间调度问题可以描述为:n个工件J={1,2,…,n}以相同的顺序依次经过两台机器ml(l=1,2)的加工.
机器ml在固定时间间隔[sl,tl](l=1,2)内不可用,工件一旦开始加工不允许等待,被不可用时间间隔中断的工件是不可恢复的(nonresumable),即在不可用时间间隔之后,被不可用时间间隔中断的工件必须重新开始加工,不能接着不可用时间间隔之前已经加工好的部分继续加工.
目标函数为最大完工时间最小化.
机器ml(l=1,2)具有不可用时间间隔的两机无等待流水车间调度问题记作F2/no-wait,nr(ml)/Cmax.
为了方便说明,定义如下符号:J={1,2,…,n}:工件集合ml(l=1,2):第l台机器pi,l:工件i在机器ml上的加工时间Si,l:工件i在机器ml上的开工时间Ci,l:工件i在机器ml上的完工时间sl:不可用时间间隔在机器ml上的开始时间tl:不可用时间间隔在机器ml上的结束时间g:不可用时间间隔的持续时间Φ:在加工过程中不存在不可用时间间隔H:使用GGA算法求解问题F2/no-wait,nr(ml)/CmaxCHmax(G):使用GGA算法求解问题F2/no-wait,nr(ml)/Cmax得到的最大完工时间Cmax(Φ):使用GGA算法求解问题F2/no-wait/Cmax得到的最优完工时间Cmax(G):问题F2/no-wait,nr(ml)/Cmax的最优完工时间Π(Φ):使用GGA算法求解问题F2/no-wait/Cmax得到的最优工件排序Π(G):问题F2/no-wait,nr(ml)/Cmax的最优工件排序2最优解条件对于两机无等待流水车间调度问题,使用GGA算法可以得到最优解.
当机器具有不可用时间间隔时,一般情况下,使用GGA算法不能求得问题的最优解.
但当问题F2/no-wait,nr(ml)/Cmax满足一定特殊条件时,使用GGA算法仍可以求得问题的最优解.
首先回顾一下GGA算法.
在Gilmore和Gomory这篇著名的文章中[2],用一个实变量x来描述机器的状态,用两个变量Ai和Bi来表示工件i的开工状态和完工状态.
也就是说,当x=Ai时,工件i开始加工;当x=Bi时,工件i完成加工.
如果工件j接着工件i加工,机器的状态需要从Bi调整为Aj,相应的调整成本为cij.
优化目标是总调整成本最小化.
这就将两机无等待流水车间调度问题转化为一类特殊的旅行商问题(travelingsalesmanproblem,TSP).
问题求解的基本思路是:首先,找到使得总调整成本最小化的Ai和Bi排序φ,然后,通过构造最小支撑树的方法将排序φ转化为可行排序,即得到最优解.
下面给出使用GGA算法可以得到问题F2/no-wait,nr(ml)/Cmax最优解的条件.
定理1在问题F2/no-wait,nr(ml)/Cmax中,当sl=0时,使用GGA算法可以得到问题的最优解.
证明当s1=0时,只需要把调度问题的开始时间推迟到t1,然后使用GGA算法对J中各个工件进行排序,就可得到问题F2/no-wait,nr(m1)/Cmax的最优解.
当s2=0时,只需要把调度问题的开始时间推迟max{0,g-p1,1},其中p1,1为Π(Φ)中第一个工件在第一台机器上的加工时间,然后使用GGA算法对J中各个工件进行排序,就可得到问题F2/no-wait,nr(m2)/Cmax的最优解.
定理2在Π(Φ)中,当Si+1,l-Ci,l=max{Sj+1,l-Cj,l}≥g,j=1,2,…,n且Si+1,l≥tl,Ci,l≤sl时,使用GGA算法可以得到问题F2/no-wait,nr(ml)/Cmax的最优解.
·662·第2期陈可嘉,等:机器具有不可用时间间隔的两机无等待流水车间调度问题的求解性质http://xbzrb.
fzu.
edu.
cn证明由于工件的无等待要求,当Cj,2>Cj,1+pj+1,1,j=1,2,…,n时,机器m1上会出现空闲时间[Cj,1,Sj+1,1];另外,当pj+1,1>pj,2,j=1,2,…,n时,机器m2上会出现空闲时间[Cj,2,Sj+1,2].
当满足定理2中所给的条件时,上述两种情况的不可用时间间隔都正好完全处于机器ml上的空闲时间[Cj,l,Sj+1,l]中,因此问题F2/no-wait,nr(ml)/Cmax等价工件具有无等待约束,机器没有不可用时间间隔时的情形,此时使用GGA算法可以得到问题F2/no-wait,nr(ml)/Cmax的最优解.
定理3在Π(Φ)中,如果C1,l+∑ni-2pi,l+∑n-1i=1(Si+1,l-Ci,l)≤sl,则使用GGA算法可以得到问题F2/no-wait,nr(ml)/Cmax的最优解.
证明机器ml加工完成所有工件所需要的时间为C1,l+∑ni-2pi,l+∑n-1i=1(Si+1,l-Ci,l).
那么,当满足定理3中的条件时,机器ml上所有工件都在不可用时间间隔之前完成加工,即不可用时间间隔不会影响问题F2/no-wait,nr(ml)/Cmax的最大完工时间,因此问题F2/no-wait,nr(ml)/Cmax等价问题F2/no-wait/Cmax,此时使用GGA算法可以得到问题F2/no-wait,nr(ml)/Cmax的最优解.
3复杂性研究当机器没有不可用时间间隔时,问题F2/no-wait/Cmax是具有多项式最优解的.
但当工件具有无等待约束并且机器具有不可用时间间隔时,问题F2/no-wait,nr(ml)/Cmax就不再具有多项式最优解,下面给出该问题的复杂性证明.
定理4问题F2/no-wait,nr(ml)/Cmax是NP难的.
证明使用三划分问题来证明该定理.
首先给出下面的三划分问题,给定正整数a1,a2,…,an,且∑iai=2A,ai≥1,那么该正整数集是否可以划分为两个子集A1,A2,使得∑i∈A1ai=∑i∈A2ai=A.
根据上述三划分问题,当l=1和l=2时,分别构造问题F2/no-wait,nr(ml)/Cmax的例子如下:当l=1时,pi,1=aiA,pi,2=A,i=1,2,…,n,s1=A2,t1=2A2,g=A2;当l=2时,pi,1=A,pi,2=Aai,s2=A2+A,t2=2A2+A,g=A2.
则要证明问题F2/no-wait,nr(ml)/Cmax为NP难的就等价于证明:三划分问题有解的充要条件是问题F2/no-wait,nr(ml)/Cmax的最大完工时间Cmax=3A2+A.
下面先证明必要性,即如果三划分问题有解,则问题F2/no-wait,nr(ml)/Cmax的最大完工时间为3A2+A.
假设三划分问题有解,则上述两个子集A1,A2存在,那么先加工A1中的工件,然后再加工A2中的工件.
当l=1时,由于pi,1=aiA,pi,2=A,ai≥1,i=1,2,…,n,因此对于任意i、j,均有pi,1>pj,2,则在满足工件无等待的要求下,A1中的工件在机器m1上加工时,机器m1上不会出现空闲时间.
同理A2中的工件在机器m1上加工时,机器m1上也不会出现空闲时间.
又由于∑i∈A1pi,1=A2=s1,因此机器m1在整个加工过程中都不会出现空闲时间.
假设工件n是在机器m2上加工的最后一个工件,而∑i∈A2pi,1=A2,因此Cmax=∑i∈A1pi,1+g+∑i∈A2pi,1+pn,2=3A2+A.
类似地,当l=2时,机器m2上从加工第一个工件开始到所有工件完工,期间不存在空闲时间,即Cmax=3A2+A.
接下来对充分性进行证明.
当l=1时,由于∑i∈A1pi,1+g+∑i∈A2pi,1=3A2,因此Cmax=3A2+A意味着机器m1在整个加工过程中不存在空闲时间.
下面使用反证法.
假设三划分问题无解,即没有任何一个工件集合可以在机器m1的不可用时间间隔开始时完工,则对于机器m1上在不可用时间间隔开始时间s1=A2之前完工的工件,其总加工时间≤A2-aiA0且t1≤Sk,1(Φ)时,CHmax(G)=Cmax(Φ);当s1Cmax(Φ)时,下式成立(r(H)g+δ>Cmax(Φ))≤Cmax(Φ)+g+δPl+g+δ+Ph,minax(G),则可得:(r(H)g+δ>Cmax(Φ))=CHmax(G)Cmax(G)≤Cmax(Φ)+g+δCmax(G)≤Cmax(Φ)+g+δPl+g+δ+Ph,min=2Cmax(Φ)+(g+δ-Cmax(Φ))Cmax(Φ)+(g+δ-Cmax(Φ)+Pl+Ph,min)Cmax(Φ))≤Cmax(Φ)+g+δPl+g+δ+Ph,minait,nr(ml)/Cmax中,共有两个工件,它们在两台机器上的加工时间分别为:p11=1,p12=1,p21=2,p22=8.
同时,sl=2,g=3.
当l=1时,该启发式算法得到工件排序为(1,2),相应的最大完工时间CHmax(G)=15并且δ=1.
而问题F2/no-wait,nr(m1)/Cmax的最优工件排序为(2,1),此时最优完工时间Cmax(G)=11.
当工件具有无等待约束并且机器不存在不可用时间间隔时,即问题F2/no-wait/Cmax,使用GGA算法求得的最优解为Cmax(Φ)=11.
因此r(H)=CHmax(G)Cmax(G)=1+g+δCmax(Φ)=1511算法得到工件排序为(2,1),相应的最大完工时间CHmax(G)=14并且δ=0.
而问题F2/no-wait,nr(m2)/Cmax的最优工件排序为(1,2),此时最优完工时间Cmax(G)=13.
当工件具有无等待约束并且机器不存在不可用时间间隔时,即问题F2/no-wait/Cmax,使用GGA算法求得的最优解为Cmax(Φ)=11.
因此r(H)=CHmax(G)Cmax(G)=1413ax(Φ)A算法可以得到问题最优解的条件,证明了问题是NP难的,得出了将GGA算法作为问题的启发式算法时,最坏性能比不大于2.
在未来的研究中,对于两台机器不可用时间间隔存在重叠以及不存在重叠情况下无等待流水车间调度问题的求解性质还有待进一步探讨.
参考文献:[1]JohnsonSM.
Optimaltwo-andthree-stageproductionscheduleswithsetuptimesincluded[J].
NavalResearchLogisticsQuarterly,1954,1(1):61-68.
[2]GilmorePC,GomoryRE.
Sequencingaone-statevariablemachine:Asolvablecaseofthetravelingsalesmanproblem[J].
OperationsResearch,1964,12(5):655-679.
[3]DileepanP.
Anoteonminimizingmaximumlatenessinatwo-machineno-waitflowshop[J].
Computers&OperationsResearch,2004,31(12):2111-2115.
[4]常俊林,邵惠鹤.
两机零等待流水车间调度问题的启发式算法[J].
计算机集成制造系统,2005,11(8):1147-1153.
[5]SuLH,LeeYY.
Thetwo-machineflowshopno-waitschedulingproblemwithasingleservertominimizethetotalcompletiontime[J].
ComputersandOperationsResearch,2008,35(9):2952-2963.
[6]WangGuo-qing,ChengTCE.
Heuristicsfortwo-machineno-waitflowshopschedulingwithanavailabilityconstraint[J].
InformationProcessingLetters,2001,80(6):305-309.
[7]ChengTCE,LiuZhao-hui.
Approximabilityoftwo-machineno-waitflowshopschedulingwithavailabilityconstraints[J].
OperationsResearchLetters,2003,31(4):319-322.
[8]ChengTCE,LiuZH.
3/2-approximationfortwo-machineno-waitflowshopschedulingwithavailabilityconstraints[J].
InformationProcessingLetters,2003,88(4):161-165.
[9]KubzinMA,StrusevichVA.
Two-machineflowshopno-waitschedulingwithanonavailabilityinterval[J].
NavalResearchLogistics,2004,51(4):613-631.
[10]ChihaouiFB,KacemI,Hadj-AlouaneAB.
No-waitschedulingofatwo-machineflow-shoptominimizethemakespanundernon-availabilityconstraintsanddifferentreleasedates[J].
InternationalJournalofProductionResearch,2011,49(21):6273-6286.
(责任编辑:林晓)·962·