第13卷第3期工业工程 2010年6月June 2010 Industrial Engineering Journal 无空闲占优机器的加工时间可变流水作业排序程明宝，张毕西(广东工业大学管理学院，广东广州510520)摘要:研究了基于实际应用背景提炼出的工件加工时间是其开工时间的线性函数的元空闲流水作业排序问题。在机器分别具有某些优势关系的情形下，探讨了目标函数为极小化最大完工时间和极小化总完工时间之和的情况。对于每种情况，分别给出了工件按某种规则排序为最优序的多项式时间算法。关键词:排序;流水作业;占优机器;依赖于开始时间的加工时间中圈分类号:0223文献标识码:A文章编号:1∞7-7375(2010)03α)61-05 Flow Shop Scheduling with Start Time-Dependent Processing Times on No-Idle Dominant Machines Cheng Ming-bao, Zhang Bi-xi (School of Management, Guangdong Univer百ityof Technology ,Guangzhou 510520, China) Abstract: For some manufacturing processes, a machine idletime can result in high cost and should be a›voided. Also, the actual job processing time can be dependent on its start time. The later a job is to be pro›cessed, the shorter time it takes to process. For flow shop scheduling with start time dependent processing times on no-idle dominant machines is studied. Polynomial time algorithm is presented to obtain optimiza›tion solution for minimizing makespan or total completion time. Key words: sequencing; flow shop; dominant machines; start time dependent processing time 在经典的排序问题中，工件的加工时间通常是于操作工人对操作技巧的熟练程度不断加强，工件一个确定的恒定时间。但在大多数有实际应用背景越往后，加工所需要的实际加工时间会越短。这类问的排序问题中，由于工件、操作人员和加工设备等因题通常称为工件加工时间与其开始加工时间相关的素，工件的实际加工时间比工件原来预定的加工时排序问题。在排序理论中工件的实际加工时间可以间要长或更短些。这种现象在炼钢工业、塑料加工、通过其正常加工时间、变化率和开始加工时间的函数来描述。Browne和Yechiali[ 1]初次介绍了工件加事故营救、车床零件加工以及大量加工类似产品等方面较为常见。如在炼钢行业锻造工件过程中，某些工时间与其开始加工时间相关的时间模型(p，=α:， + 工件的锻造过程有温度的要求，在满足温度要求的句)。他们研究了单处理机情形下的最大完工时间问条件下，工件的加工时间为常数时间，如果工件在锻题，得到了以{号}的非降序排列所获得的序为该问造前要等待一段时间，将会引起工件温度的重大变化。这样，工件元论是重新回炉加温使其满足温度要题的最优排序。其他相关的详细文献可参考综述求还是在不满足温度要求的情况下加工，都将导致[2-3 ]。工件的实际加工时间的增加。再如，在于工操作加工相对于该加工时间模型下的单机排序问题，此工件的过程中，由于大量加工或处理类似的工件，基模型下的流水作业排序问题则显得更加复杂。收稿日期:2(阴-07-09基金项目:国家自然科学基金资助项目(7侃71030，7ω71026);广东省自然科学基金资助项目(9151ω∞刚刚时);高校人文社科重点研究项目(08jdxm63∞4);广东工业大学博士启动基金项目(佣3092)作者简介:程明宝(1972-)，男，湖南省人，副教授，博士，主要研究方向为推序理论与算法、库存控制与优化.
第13卷工业工程62 Mosheioy[4l研究了工件的加工时间为简单线性函数的所有工件在to= 0后均可以被加工且不计工件加工前的调整安装时间，机器一旦开始加工，工件就不允两台处理机的流水作业问题F21PiJ = b.} 1 C'并对max许出现空转(no-idle)，且工件在加工过程中不可以目标函数为C皿的情况给出了复杂性为O(nx log n) 中断。若目标函数为极小化最大完工时间的m台的多项式时间算法。同时证明了此类问题的3台处理l机情形为NP-难问题。Kononoy和Gawiejnowicz[5则机器的流水作业排序问题，则可以简写成Fm1 P." = 几-bt,no -idle 1 C皿。为使研究的问题有意义，不m证明了F21NP-难问题。由P." =飞+b.}/C为强max妨假设对任意的t，恒有P'=ι-bt ;3: 00 于该类问题大多都属于NP-难问题，因此，近年来很J定义对于机器M，和机器吨，如果maxjα'J1 j = 多研究人员对此加工模型的一些特殊情形进行了研1，2，…，叫~minjαkd|j=1，2，…，叫，则称机器M，究，读者可以参考文献[6-9J。对于m台处理机的经优于机器矶，不妨记为M，< Mk。典流水作业问题，除了两处理机的Johnson算法对目根据定义，本文主要讨论以下优势关系:标函数为极小化最大完工时间可获得多项式时间算1)机器具有单调递增的优势关系(Increasing 法外，其余情况多为NP-难问题。所以，很多学者通m;dominant machines, idm) : M< M< <M1 2 过提出一些近似算法来研究这类NP-难问题。如2)机器具有单调递减的优势关系(Decreasing Sm川nicki等[叫;或者通过讨论此类问题的一些特殊dominant machines,ddm) :M1 < M< <Mm; 2 情况(例如，机器间具有某种优势关系)来分析这类3)机器具有先增加后减少的优势关系:M1< M2 NP-难问题，相关的工作可参考文献[11-13J。< <M> > Mm(idm-ddm)，其中，1<h<m;h 加工机器在加工过程中的元空闲(no翩idle)约束4)机器具有先减少后增加的优势关系:M1> 主要体现在生产过程中若机器出现空闲会产生高昂M> >Mh < < Mm(ddm-idm)，其中，1< h < m。2 的成本费用(如租借他人加工设备)，加工工艺技术要求(如温度要求)，或者为了使产能最大化(如铸造2 极小化最大完工时间(C)问题max生产线)。例如，加工玻璃纤维工艺流程中的加热炉，在本节中，主要讨论机器具有优势关系条件下在一个生产周期里要一直保持其固有的高温，否则的极小化最大完工时间问题。首先给出一些引理以将为重新恢复到生产所要求的温度付出很高的成方便后面对排序问题的探讨，这些引理可从文献[1 J 本。相关的文献可以参考文献[14-16J。和[8J中直接推导出来，因此不予以证明。结合上述综述，本文主要研究工件加工时间是引理1对于问题11P, =气-bt 1 C阻，以|αJmi 其开工时间的递减线性函数的元空闲机器流水作业的非增序排列所获得的序为最优排序(LPT)。排序问题。这主要体现于，某些加工领域一方面由于引理2对于问题1 -btno -idleidm 1j Fm,,, P’J 让机器在加工过程空闲会导致高昂成本;另一方面([1j E j C三飞|和一给定的工件序σ=], max机器在加工过程中由于自身及加工工件因素导致工'[2[n])则工件的完工时间为], , ，C[，= hll件的实际加工时间会减少。由于只有两台机器的流水作业问题存在多项式时间解，所以本文研究加工-k-俨寸1+)，-b (1 (1 。矶[1]主川1Z机器具有单调递增、单调递减、单调增加减少和单调引理3-对于问题1 α-btno idleFm=,, J P’'J 减少增加优势等关系下的机器无空闲流水作业问ddmlj[n]) 和一给定的工件序([1[2σ=], ],,, 题。所讨论的目标函数为极小化最大完工时间和极小化完工时间之和问题，得到了此加工模型在机器则工件的完工时间为CU]=ZGI[k](1-hl具有优势关系条件下都为多项式时间可解的。叫-k-1m-叫)α;[ n -b) --+ (1 (1 J 句，[klLL1 问题描述-k)，b 。假设有n个工件J，J，…，人将依次在机器矶，12引理4-对于问题lFmbt no idle=,, 飞P’J -M2'…，Mm上加工。若工件礼的开始加工时间为人其idm -ddm 1 j和一给定的工件序σ=([1[2],], , 实际加工时间定义为P'=气，-bt, i = 1,2, ,m, J叶-b)m1+[n ) ，则的完工时间为C(1J 三矶，[1]ful[j=lj=11，…爪，表示工件越迟被加工，其实际加工时mvhn-1 TL" tκ J，，，、-、A ，。、‘，m 忖’--且ED、、 .，m 甘n 间越短。其中，凡为工件扎在机器M.上的正常加工，，‘、α + a zh 'κ 自Fn F，问时间;b(O< b < 1)为所有王件共同的变化率。假设
第3期程明宝，张毕西:无空闲占优机器的加工时间可变流水作业排序63 证明考虑工件序σ=(J[ll ,][2] , ,][n]) ，由L am,[k] (1 -b)J飞引理3可得引理5对于问题Fm1p，，j'=飞-bt，n。一idle，C=LαI，[k](1-b)mH-k-1+工α，，[n](1 -m皿ddm -idmlf和一给定的工件序σ=([1],[2], , n-I (2) [n]) ，则工件h]的完工时间为C[J]= L al,[k] (1 -若末个加工的工件确定且满足俨-M+zh](1-俨-pz-zh](1-三αiJ(1-b)m-z=min|豆，αi，J(1 -b)叫1运J:运叫，俨-M+SEfz[1](1一b)叫十1+主川](1 -n-I 则式(2)中的第2项为常数，而立αI，[k](1 -由引理2可知，第1个被加工的工件和最后1台b)m叶k-I可由其余(n-1)个工件在第1台机器上以机器上工件的加工顺序对工件h]的完工时间产生i αIJ f非增序排列而获得最小，则问题FmI p’,J = 重要的影响，则可得如下定理。α'，J -bt, no -idle, ddm I C可获得最优序。max定理1问题Fm1P'，J=矶、J-bt,no -idle,idm 对于问题凡Ip’J =矶，JFbt，no-idle，idIIIEddm I C'由引理1和引理4可得maxI C'如果首个加工工件J，确定且满足La,,(1 -maxiCH]=Zh](1-b) -I+Zh](1-b)m -1=min |2;α'J(1 -b) -,-1 I 1运j运nf，b)…-k+Zh](1-b)飞则有如下定理。则序σ=jJ"σ1 f为最优排序，其中，σl为其余(n-1 )个工件以jaf非增序排列的部分排序。mJ 定理3对于问题凡Ip’J =α'J -bt,no -idle,idm 证明考虑序σ=(1[1] ,J[2] , ,][n]) ，由引理2-ddml C础，当确定第1个和最后1个加工工件后，以可得其余(n-2)个工件以jah,J f的非增序排列所获得的序为最优排序。Cm=ZqH](1-wm-1+Eh](1-V。(1)证明考虑工件序σ=(J[I] ,J[2] , ,][n]) ，由如果首个加工的工件确定且满足引理4可得mTIJ4·、、.，m，，+ n ’nu ，，、、α = 且】川C-b)-1+zh](1-m皿](1 =Zα，，[1 min j Lα，) 1 -b)m -1 I 1运j运nf，川。b)-hzh](1-b)(3)…则式(1)中的第1项为常数，由引理l可知若第1个和最后1个加工的工件确定，则式(3)的第1和第3项为常数。(3由)引理1可知，对于式中三~川川[问kρ川]的第2项由其余的(n-2)个工件在机器Mh上以台‘如机器上以|问αm风'叫Jf非增序排列而获得最小，则问题j 的非增序排列所获得的序可使其最小。定理ahf,J F凡mI p’J =α'J -bt,no -idle,idm I C皿可获得最m证毕。优序。由定理可知，问题btno -idleFmI =ι-, , p’,J 由引理3可知，第1台机器上工件的加工顺序和idm -ddm I Cm阻的最优序可按如下获得:依次选取最后1个待加工的工件主要影响着工件J[J]的完工J1，，…λ，Jn作为第1个加(工n-工件，再从剩余的时间，则有如下定理。1)个工件中选取1个工件作为最后加工的工件，其定理2问题FmI P’,J =α'J -bt,no -idle,ddm 余的(n-2)个工件以α的非增序排列，由此获ifhJ I C'如果末个加工工件λ确定且满足三α"，(1 -max得n(n一1)个序，其中使目标函数最小者所对应的序为最优排序。2b)m-, = min j Lι(1 -b )m-, I 1运j运nf，则加工工显然易知，该算法的计算复杂性为O(mn1ogn)。对于问题no -idleddm FmI -bt-序=,,σ=j σI，J，f为一最优排序，其中，σ1为以iαI，j f p’J ιidm I C由引理1和引理5，则在如下定理。的非增序排列的其余(n-1)个工件组成部分序。max'
工业工程第13卷64 定理4对于问题FmI P’=飞-bt,no -idle, J 主挝主~阳川[川k刮ρμ]ddm -idm I CIDBl('当确定第1个和最后1个加工工件后，其余(n-2)个工件以|龟孙](I_b)m-1_α队以](1-_ 川+1 ]((I-b)1) b川)m川→+ t E~ 川川[忱k川川。b) m-h +αm.[k] \的非增序排列所得的序为最优序。如果首个加工的工件确定且满足证明考虑序σ=(1[1] ,1[2] , ,J[n]) ，由引理5，可得m-. 川_b)m叫=αsmin -b) I 1运1 (1 矶.，LLC= L r a..rll(1 -b)1寸+生L斗1(1 -max 问h+1L'.-~ m -n. ((1-by-k+I-1)j运n\α[k]，，可由其余(n-且三隅，b)川-2+三|αrn 1 (1 -b) m-. +包[n~1+ 1)t:1 L -qnJ ’ --I h -1 J 个工件以|α非增序排列而获得最小，所以问m.;\n-1 题I Fma-btno idleidm I= -,,立飞可获得最ij ,J P’三[α1.[k](I-b)m-1-句.[k](1 -b)川+αm.[k]]( 1 -优序。b)叫。(4)由引理3可知，对于问题btnFmI o -=,飞J P’-若第1个和最后1个加工的工件确定，则式(4)idle ddm I C最后1台机器上的工件序的完工时,j，L 的第1和第2项为常数。对于式(4)中的第3项，显间和首个被加工的工件对工件的完工时间产生J[il然，利用交换原理可证得由其余的(n-2)个工件在重要的影响，所以有如下定理。机器M|α上以1.[k](1-b)m-1-鸟.[k](1 -b)m-h + h定理6问题FmI =btno -idle-,, Pi., α'，j 句.[k]\的非增序排列所获得的序可使其最小。定理ddm I 如果末个加工工件J确定且满足证毕。，L C"l_b)n_1FI 由定理可知，问题FmI P’,J =矶，J(-bt, no -idle, +1 -b) +α= 用t主化(1b ddm -idm I C皿的最优序可按如下获得:依次选取m1 ;:,J，J，…，J作为第1个加工工件，再从剩余的(n(1 -1 -bt 1 2n-l俨I 1运ZMIEj~n\, nib 问，1)个工件中选取1个工件作为最后加工的工件，其则序σ=1σI，J，\为该问题的一最优排序，其中，余的(n-2)个工件以|α1.[k](1-b)m-1-αh.[k] σ1(1 --b)m 为其余(n-1)个工件以(α-α-1(1((1 b) m-h +α隅•[k] \的非增序排列，由此获得n(n -1)个1.;m) b)n-l)+序，其中使目标函数最小者所对应的序为最优排序。α-b)叫|的非降序排列的部分序。m/l 2显然易知，该算法的计算复杂性为O(mnlog n)。证明考虑序σ=,1，…(1[1] [2] ，J[叫)，由引理3可得3 极小化完工时间之和(I C)问题jn n-l ZQ=ZZG1[k](1-b)rkfl+ 本节主要讨论机器具有优势关系条件下的极小化完工时间之和问题。类似于上一节，由引理2可知，ky-zh](l-m.[k](I-b= 俨叫-王军1α工件序中的第1个加工工件和最后1台机器上工件z 加工顺序主要影响着工件h]的完工时间，则有如下n1m哺叫[ ( 1 一的旷机-川1+ajMI 川川[k] 口J切m川[问k叫μ(叫]川E 定理。 (ο1 -b的r--1 r ~ 定理5对于问题FmlP’,J =α'，j -bt,no -idle, ~n _旷叩I+bαW~] (1 -[ a..[n] ιlnJ'l ~ t当(1 -b -1 r idm I L C"若首忖H工工件λ确定且满足Fzz(1-tzhh r =min |zasd(1-by-zl1运j~n\，则工件序若未个加工的工件确定且满足σ= lJ"σ1\为一相应最优排序，其中，σ1为其余-.+1α(1+凡=-俨豆"，n ’." (n -1)个工件以1am,j \的非增序排列的部分序。-b) -1 t1 (1 证明考虑序σ=(1[1] ,J[2] , ,1[n]) ，由引理2-.+1+帆min iFKJ(1-俨I1运j运f.-J --., 可得含1'"-bt-l--(1b)n LC, =豆豆α山。](1-b)叫-.-1+ 而-1.[k][(1+αρ -lJ m.[tziα
第3期程明宝，张毕西:无空闲占优机器的加工时间可变流水作业排序65 b )m-k可由其余(n-1)个工件以|α1，[，]((1 -b)n -b) m-h+1 [ (1 -b t -1] +αm，[k] (1 -b)附11(1-b)-k+ m1) +αm，[，]()l-l非增序排列而获得最小。由引(1 _b)n_1I L21 ~l 芝芝;α町"川材，[r「巾川n问l(1i 含饵~--'，lnJ'--, (1 一bt -1 J 理1，问题FmI Pi,j =α'" -bt，o。一dile，ddmI L C，可获得最优序。士(Zh])，对于问题几IP’" =α'" -bt, 00 -dile, idm -则有如下定理。ddm I L C"由引理4可知，定理8对于问题Fmlp,,, =αi" -bt,oo -dile, hynT''声叫工州叫咱CJ2Lυ、m=斗αhmV且JBJLU」町++ 口-’1 ddm -idm I L 午C, 时'若+第1个加工和最后1个加工工件HThM 确定，则其余工件以αu((1-b)n -1)(1 -b)m_ 门、，，‘、、α lαB/一司αu (1 -b) m-h+1 ( (1 -b) n -1) +α (1 -b) n+1的非增序排列所获得的序为最优排序。豆》l严α阳f》~m叫川[k忱什证明证明类似于定理4，略。由定理可知，问题FmI p,,, =飞j-bt, 00 -dile, 1 ’" bαr1 1 ZGsh](1-b)m→+1+mAnj|+士Ljah,[k] [(1-J (1-bt-1b ddm -idm I L C，的最优序可按如下获得:依次选取J,]2 ，…，人作为第1个加工工件，再从剩余的(n-1旷_1](1_b)m-h +a_b)l-k_寸÷Z~川 [h忱k叫川]m川 1 )个工件中选取1个工件作为最后加工工件，其余则有如下定理。的(n-2)个工件以|α( (1 -b) n -1) (1 -b) m -定理7对于问题FmI p’J =飞-bt,oo -dile, αu (1 -b) m-h+1 ((1 -b) n -1) +α (1 -b)叫i的idm -ddm I L C，若第1个加工和最后1个加工工件非增序排列，由此获得叫n-1)个序，其中使目标函j数最小者所对应的序为最优排序。确定，则其余工件以αu((1 -b)n -1)(1 -b)川+2显然易知，该算法的计算复杂性为O(mn10gn)。α的非增序排列所获得的序为最优排序。证明证明过程类似于定理3，略。4 结束语由定理可知，问题FmI Pi,j =αi" -bt,oo -dile, 在实际生产中，机器设备在加工过程中的空转idm -ddm I L C，的最优序可按如下获得:依次选取会产生高昂的成本费用(租借他人加工设备);另外(J1，]2，…，J)作为第1个加工工件，再从剩余的(nn作业在加工过程中，由于工人操作技巧的不断加强，-1)个工件中选取1个工件作为最后加工的工件，加工工艺技术的不断改进，会导致作业的实际加工其余的(n-2)个工件以ja((1 -b) n -1) (1 -u 时间更短。基于此实际背景，本文主要研究了无空闲b) m-h +α I的非增序排列，由此获得n(n -1)个优势机器条件下工件加工时间是其开始加工时间的序，其中使目标函数最小者所对应的序为最优排序。线性关系的流水作业排序问题。由于多机器环境下，2显然易知，该算法的计算复杂性为O(mnlog n)。此类问题一般都隶属于难解问题，在此讨论了机器对于问题Fm具有单调递增、单调递减、单调增I p加减少和,,,单 =飞-bt,oo -idle,ddm 调减少-增加等优势关系的情形下，目标函数为极小化最大idm I L C，及一列给定的序σ=([1], [2],..., 完工时间和极小化总完工时间之和的情况。对于每[n]) ，由引理5有种情况，分别给出了工件按某种规则排列加工的多三乌=ZIZα1，[剖(1一俨k-1项式时间算法，这对在生产实+ 践中如何合理安排工件加工顺序具有很好的指导意义。zh](1-斗b俨-参考文献:[ 1 J Browne S, Yechiali U. Scheduling deteriorating jobs on a sing扣&豆豆豆豆1卢α叫f町i川ω介[川山口1门川川]刊川(1 -俨护川，-1+υ+ 主ια》阳m叫~[川μk叫川]刊(1-斗b川旷)γ尸rl川叫叮k才-斗]寸= processor[ JJ. Operations Research, 1990 ,38( 3) : 495-498. [ 2 J Alidaee B, Wo mer NK. Scheduling with time dependent pro›(1-?Y?n~-1ILi[1](1-byhl[1](lJY-11+ cessing times: review and extensions [J J . Journal of the Oper›ational Research Society, 1999 ,50 ( 4 ) : 711-720. 过ja，[k][(1-b)n -1](1 -b)m -a,[k](1 -1h(下转第88页)
工业工程、第13卷88 [ M J . New York: Oxford University Press ，2∞1 :238-3∞. [ 7 J Hauser J R, Clausing D. The house of quality [ J]. Harv时[ 14 J Kulak 0, Kahraman C. MuIti-attribute comparison of ad›Business Review, 1988 ,66(3) :63-73. vance manufacturing systems using fuzzy vs. crisp axiomatic [ 8 J Kim S H, Jang D H, Lee D, et al. A methodology of construc›desi伊approach[ J J. lnternational Journal of Production E›ting a decision path for πinvestment [ J J . Journal of Strategic lnformation conomics，2∞5，95 :415424. Systems ，2α泪，9(1):17-38. [9 J Partovi F Y. An analytical model of process choice in the [15 J肖人彬，程贤福，廖小平.基于模糊信息公理的设计方案chemical industry[ JJ. lnternational Journal of Production E›评价方法及应用[JJ.北京:计算机集成制造系统，2∞7，13(12) :2331-2338. conomics，2∞7，105 (1) :213-227. [ 16 J Cengiz Kabraman, Selcuk Ceb. A new muli-attribute d配1-[10 J Buckley J J. Fuzzy hierarchical analysis[ JJ. Fuzzy Sets and sion making method: Hierarchical fuzzy axiomatic design Systems, 1985,17 (3) :233-247. [ 11 J Hsieh T Y, Lu S T, Tzeng G T. Fuzzy MCDM approach for [ J J . Expert Systems with Applications, 2∞9，36(3) :4848-planning and desi伊tendersselection in public office build›4861. [ 17 J Martin Stopford. Shipping intelligence weekly [ M J. Eng›ings [ J J. lnternational Journal of Project Management, 2∞4，22(7) land : Clarkson Research Service Ltd., 2创)7.:573-584. [12JSuh N P.四eprinciples of design [ M J. New York:伽ford[18 J Drewry Shipping Insight.世界油轮船队情况统计[OB/ University PressOLJ.[2∞9-3-30 J. , 1990: 158-221. [13 J Suh N P. Axiomatic design: Advances and applications jsp? cid = 31. (上接第65页)[ 10 J Smutnicki C. Some results of worst-case analysis for flow [ 3 J Cheng TCE, Ding Q, Lin BMT. A concise survey of schedu›ling with time-dependent processing timω[J]. Euro严mshop scheduling [ J J. European Journal of Operational Re›泪Journal of Operational Research ，2'α，152(1):1-13. search,1998,109(1) :66-87. [ 4 J Moshieov G. Complexity analysis of job-shop scheduling with [ 11 J Nouweland AV D, Krabbenborg M, Potters J. Flow shop w地deteriorating jobs [ J J. Discrete Applied Mathematics, 2∞2， a dominant machine [ J J. European Journal of Operational 117(2) :195-209. Research,1992,62(1) :3846. [5 J Kononov A, Gamiejnowicz. NP-hard cases in scheduling dete›[ 12 J Ho JC, Gupta JND. Flow shop scheduling with dominant ma›riorating jobs on dedicated machines [J] . Journal of the Oper›chines [J J. Computers & Operations Research, 1995,22 ational Research Society, 2∞152(4) :708-717. (2) :237-246. [ 6 J Wang JB, Xia Z Q. Flow shop scheduling wi出deteriorating[ 13 J Xiang S, Tang G, Cheng TCE. Solvable c倒四ofpermutation jobs under dominant machines [ J J. Omega, 2∞6，34(4): flow shop scheduling with dominating machines [ J J. lnter›327-336. national Journal of Product Economics, 2α泊，66(1 ) : 53-[7 J Wu C C, Lee W C. Two-machine flowshop scheduIing to min›57. imize mean flow time under linear deterioration [ J J . lnterna›[14 J Kalczynshi Pawel Jan, Kæ由urowskiJe町.A heuristic for tional Journal of Production Economics, 2创汤，103 ( 2) : 572-minimizing the makespan in no-idle permutation flow shop 584. [ J J. Computer百&lndustrial Engineeri吨，2∞5，49(1) : [ 8 J Cheng M, Sun S, He L. Flow shop scheduIing wi也deteriora146-154. ting jobs on no-idle dominant machines[ JJ. European Jo山咀al[ 15 J Kalczynshi Pawel Jan, KanIburowski Jerzy. On no-wait and of Operational Research, 2∞'7 ,183( 1) :115-124. no-idle flow shop wi由makespancriterion [ J J. European [9 J Lee W C, Wu C C, Wen C C, et al. A two-machine flowshop Journal of Operational Research ，2∞7，178(3) :677-685. makespan scheduling problem with deteriorating jobs [ J J . [ 16 J Saadani No旧日，Guinet Alain, Moalla Mohamed.咀rreeComputers &-lndustrial Engineering, 2008,54 (4) : 737-stage no-idle flow shop [ 1]. Computer百&lndustrial Engi›749. neering，2∞3 ,44 (3) :425434.
