同時(shí)具有學(xué)習(xí)和惡化效應(yīng)的不同工期指派問(wèn)題研究

王吉波，牛玉萍，劉 璐，郭 倩

（1.沈陽(yáng)航空航天大學(xué) 經(jīng)濟(jì)與管理學(xué)院，沈陽(yáng) 110136；2.沈陽(yáng)航空航天大學(xué) 理學(xué)院，沈陽(yáng) 110136）

0 引 言

排序問(wèn)題是一類重要的組合最優(yōu)化問(wèn)題，多年來(lái)人們一直在運(yùn)籌學(xué)、管理科學(xué)、系統(tǒng)工程、計(jì)算機(jī)科學(xué)等領(lǐng)域致力于該問(wèn)題的研究。在大多數(shù)排序問(wèn)題中，工件的加工時(shí)間是一個(gè)獨(dú)立的且與開工時(shí)間和加工位置無(wú)關(guān)的常數(shù)。不過(guò)，在所知的一些實(shí)際問(wèn)題中，由于工人（機(jī)器）在很長(zhǎng)的時(shí)間加工相同或類似的工件時(shí)，加工效率有可能逐漸提高，因而使得后面加工的工件的加工時(shí)間縮短，這種現(xiàn)象被稱作具有學(xué)習(xí)效應(yīng)［1］。另一方面，在實(shí)際生產(chǎn)中，工件的實(shí)際加工時(shí)間會(huì)因工件開始時(shí)間的推遲而延長(zhǎng)，這種現(xiàn)象被稱為具有惡化效應(yīng)［2－3］。

Biskup［4］、Cheng等［5］首先研究了這類具有學(xué)習(xí)效應(yīng)的單機(jī)排序問(wèn)題。在Biskup的文章中，他證明了在具有學(xué)習(xí)效應(yīng)的工件排序情況下，當(dāng)目標(biāo)函數(shù)為極小化共同工期偏差與完工時(shí)間和時(shí)，這類單機(jī)排序問(wèn)題是多項(xiàng)式時(shí)間可解的。Cheng等［5］研究了工件加工時(shí)間具有學(xué)習(xí)效應(yīng)的單機(jī)排序問(wèn)題，其中工件的學(xué)習(xí)效應(yīng)模型為一個(gè)分片線性加工時(shí)間函數(shù)，目標(biāo)函數(shù)為極小化最大延誤時(shí)間。他們證明了此問(wèn)題是強(qiáng)NP－難的，并給出了2個(gè)多項(xiàng)式時(shí)間可解的特殊情況。同時(shí)，還提出了2個(gè)啟發(fā)式算法，并分析了它們的最壞情況界。孫林輝等［6］研究了具有學(xué)習(xí)效應(yīng)的流水作業(yè)排序問(wèn)題，對(duì)總完工時(shí)間極小化問(wèn)題，給出了數(shù)學(xué)規(guī)劃模型和3個(gè)啟發(fā)式算法。Mosheiov［7］對(duì)其他的一些單機(jī)排序問(wèn)題進(jìn)行了研究，得出了使用最小加工時(shí)間優(yōu)先規(guī)則（SPT）可以獲得最大完工時(shí)間問(wèn)題的最優(yōu)排序。Biskup［8］對(duì)這類具有學(xué)習(xí)效應(yīng)的排序問(wèn)題進(jìn)行了綜述。最近關(guān)于學(xué)習(xí)效應(yīng)的排序成果，讀者可參考文獻(xiàn)［9－14］。Gawiejnowic［15］給出了關(guān)于工件具有惡化效應(yīng)排序問(wèn)題的綜述。最近關(guān)于惡化效應(yīng)的排序成果，讀者可參考文獻(xiàn)［16－19］。Lee首次提出了工件同時(shí)具有學(xué)習(xí)和惡化效應(yīng)的排序問(wèn)題模型［20］，接著Wang［21－28］，Low 等［29］研究了不同的模型。

王吉波等［19］研究了工件具有不同工期的排序問(wèn)題，其中工件的加工時(shí)間具有惡化效應(yīng)。但現(xiàn)實(shí)的生產(chǎn)過(guò)程中存在著工件加工同時(shí)具有學(xué)習(xí)效應(yīng)和惡化效應(yīng)的情況（Wang［21－22］，Wang等［23］），因此本文研究工件加工同時(shí)具有學(xué)習(xí)效應(yīng)和惡化效應(yīng)的不同工期排序問(wèn)題，證明了此問(wèn)題依然多項(xiàng)式時(shí)間可解。

1 問(wèn)題模型

其中α，β和γ分別表示每一時(shí)間單元的提前、延誤和工期懲罰。

2 主要結(jié)論

引理2 （Wang［21］）對(duì)于排序問(wèn)題1｜pj＝（aj＋bt）rθ｜Cmax，最優(yōu)排序能通過(guò)把工件按照aj的非減順序排列得到（SPT規(guī)則）。

證明 令S＝（π1，Ji，Jj，π2），其中，π1和π2分別為Ji之前加工的工件和Jj之后加工的工件，Ji和Jj分別位于第r和第r＋1個(gè)位置且ai＜aj。交換第r和第r＋1個(gè)位置上的工件，其他不變，得到排序S′＝ （π1，Jj，Ji，π2）。此外，假設(shè)A為部分排序π1中最后一個(gè)任務(wù)的完工時(shí)間。為了表明序列S優(yōu)于S′，需要證明 max（0，Ci（S）－d）＋max（0，Cj（S）－d）≤ max（0，C′j（S）－d）＋max（0，C′i（S）－d）。顯然

因?yàn)閍i＜aj，由引理2得Cj（S′）－Ci（S）＝（aj－ai）rθ＞0，即Ci（S）＜Cj（S′）Ci（S′）－Cj（S）＝（aj－ai）［rθ－（r＋1）θ＋brθ（r＋1）θ］＞0，即Ci（S′）＞Cj（S）。

下面將分6種情況進(jìn)行討論。

1）當(dāng)Ci（S′）≤d時(shí)，此時(shí)Cj（S）＜Ci（S′）≤d，Ci（S）＜Cj（S）＜d，所以

2）當(dāng)Ci（S）≥d時(shí)，此時(shí)Cj（S′）＞Ci（S）≥d，Ci（S′）＞Cj（S）＞d，所以

3）當(dāng)Ci（S）＜d且Cj（S′）＞d，Cj（S）＜d時(shí)，此時(shí)Ci（S′）＞Cj（S′）＞d，所以

4）當(dāng)Ci（S）＜d且Cj（S′）＞d，Cj（S）＞d時(shí)，此時(shí)Ci（S′）＞Cj（S）＞d，所以

5）當(dāng)Ci（S）＜d且Cj（S′）＜d，Cj（S）＞d時(shí)，此時(shí)Ci（S′）＞Cj（S）＞d，所以

6）當(dāng)Ci（S）＜d且Cj（S′）＜d，Cj（S）＜d，Ci（S′）＞d時(shí)

綜上所述，可以得到當(dāng)ai＜aj時(shí)，max（0，Ci（S）－d）＋max（0，Cj（S）－d）≤ max（0，C′j（S）－d）＋max（0，C′i（S）－d），即工件按照SPT規(guī)則排序可以得到最優(yōu)排序。證畢。

定理1 對(duì)于任意一個(gè)給定排序π＝ （J［1］，J［2］，…，J［n］），最優(yōu)排序滿足如下條件：如果β≥γ，＝C［i］，否則＝min｛A，C［i］｝，其中［r］表示工件排在第r個(gè)位置。

證明 過(guò)程完全類似于王吉波等［19］，Seidmann等［30］，故省略。

證明1）對(duì)于情況β≥γ，由定理1可知，對(duì)于任意給定排序，每個(gè)工件的工期應(yīng)等于它們各自的完工時(shí)間，所以沒有工件會(huì)提前完工和發(fā)生延遲，即Ej＝0，Tj＝0，j＝1，2，…，n，因此

因此目標(biāo)函數(shù)為最小化γ∑max（0，Cj－A），或最小化∑max（0，Cj－A）（因γ為常數(shù)）。通常公共工期的最大延遲問(wèn)題的模型為：∑max（0，Cj－d），如果其中的公共工期d被替換成本文中的A，則變成∑max（0，Cj－A），也就是筆者要求的最優(yōu)目標(biāo)函數(shù)，故由引理4，最優(yōu)排序能通過(guò)把工件按照aj的非減順序排列得到（SPT規(guī)則）。

2）對(duì)于情況β＜γ。

因?yàn)閐j＝min（A，Cj）（根據(jù)定理1），可以得出dj≤A和Aj＝0。此時(shí)提前完工時(shí)間為零，即Ej＝0。

在排序π中，工件i和工件j為2個(gè)連續(xù)加工的工件，并假設(shè)ai＞aj且工件i和工件j分別位于第［i］和第［i＋1］個(gè)位置，π1和π2分別為第［i］個(gè)位置之前的工件的加工順序和第［i＋1］個(gè)位置之后的工件的加工順序，故排序?yàn)椋é?，Ji，Jj，π2），現(xiàn)利用相鄰交換法來(lái)證明結(jié)論。

圖1描述了位置［i］和［i＋1］上的工件的完工時(shí)間和期望工期A之間的關(guān)系。見圖1a，可知

然后交換第［i］和第［i＋1］個(gè)位置上的工件，其他不變，故排序變?yōu)椋é?，Jj，Ji，π2），則

因?yàn)閍i＞aj，所以

1）因?yàn)榻粨Q后不影響π1中的工件，所以目標(biāo)函數(shù)的提前成本和延遲成本為零，而機(jī)會(huì)成本則沒有發(fā)生變化，因此，總成本不變。

2）下面，來(lái)討論一下交換工件Ji和Jj后對(duì)總成本的影響。

?。┊?dāng)C′［i］≤A時(shí)，對(duì)于工件Ji來(lái)說(shuō)，交換前Ji的懲罰成本為β（C［i］－A），交換后的懲罰成本為β（－A）；對(duì)于工件Jj來(lái)說(shuō)，交換前Jj的懲罰成本為β（C［i＋1］－A），交換后的懲罰成本為零，所以交換后對(duì)總成本的影響將會(huì)變小。

ⅱ）當(dāng)C′［i］＞A時(shí)，對(duì)于工件Ji來(lái)說(shuō)，交換前Ji的懲罰成本為β（C［i］－A），交換后的懲罰成本為β（C′［i＋1］－A）；對(duì)于工件Jj來(lái)說(shuō)，交換前Jj的懲罰成本為β（C［i＋1］－A），交換后的懲罰成本為β（C′［i］－A）或?yàn)榱?，所以交換后對(duì)總成本的影響將會(huì)變小。

3）雖然交換后不影響π2中的工件，但交換后C［i＋1］＞C′［i＋1］，使得π2中工件的實(shí)際加工時(shí)間縮短，因此，總成本將會(huì)變小。

圖1 A的不同位置情況

算法1

第1步 把工件按照SPT規(guī)則進(jìn)行排序，即按照a［1］≤a［2］≤…≤a［n］進(jìn)行排序。

第2步 比較β，γ的大小關(guān)系，如果β≥γ，＝C［i］，否則＝min｛A，C［i］｝。

例1 考慮6個(gè)工件J＝｛J1，J2，J3，J4，J5，J6｝的排序問(wèn)題，其中a1＝10，a2＝8，a3＝7，a4＝15，a5＝14，a6＝3，α＝15，β＝20，γ＝5，b＝0.05，a＝－0.322，A＝30。

解 第1步 由于a6≤a3≤a2≤a1≤a5≤a4，因此最優(yōu)排序?yàn)椋↗6，J3，J2，J1，J5，J4）；

第2步 因β≥γ，d6＝C6＝3，d3＝C3＝3＋（7＋0.05×3）×2－0.322＝8.719 7，

下面給出王吉波等［19］類似的算例來(lái)說(shuō)明算法1是如何求解問(wèn)題

例2 考慮6個(gè)工件J＝（J1，J2，J3，J4，J5，J6）的排序問(wèn)題，其中a1＝10，a2＝8，a3＝7，a4＝15，a5＝14，a6＝3，α＝15，β＝20，γ＝25，b＝0.05，a＝－0.322，A＝30。

解 第1步 由于a6≤a3≤a2≤a1≤a5≤a4，因此最優(yōu)排序?yàn)椋鸍6，J3，J2，J1，J5，J4｝；

第2步 因β＜γ，根據(jù)例1和算法1得

3 結(jié)論與展望

本文研究了工件同時(shí)具有學(xué)習(xí)和惡化效應(yīng)的不同工期指派排序問(wèn)題，其中機(jī)器限定為1臺(tái)，目標(biāo)函數(shù)為最小化提前成本、延遲成本和交貨期成本的加權(quán)和。證明了該問(wèn)題是多項(xiàng)式可解的并給出了最優(yōu)算法。對(duì)于工件同時(shí)具有學(xué)習(xí)效應(yīng)和惡化效應(yīng)的排序問(wèn)題，還有許多研究工作可做，比如研究多機(jī)（平行機(jī)或流水作業(yè)）問(wèn)題，研究工期給定的排序問(wèn)題，或者研究一般的惡化函數(shù)和學(xué)習(xí)效應(yīng)函數(shù)等，探討這些問(wèn)題的可解情況以及對(duì)于NP－難的問(wèn)題建立有效的近似算法和設(shè)計(jì)其他更好更快的算法是進(jìn)一步研究中有意義的工作。

［1］BADIRU A B.Computational survey of univariate and multivariate learning curve models［J］.IEEE Trans Eng Manage，1992，39（2）：176－188.

［2］GUPTA J N D，GUPTA S K.Single facility scheduling with nonlinear processing times［J］.Comput Ind Eng，1988，14（4）：387－393.

［3］BROWNE S，YECHIALI U.Scheduling deteriorating jobs on a single processor［J］.Oper Res，1990，38（3）：495－498.

［4］BISKUP D.Single－machine scheduling with learning considerations［J］.Eur J Oper Res，1999，115（1）：173－178.

［5］CHENG T C E，Wang Guoqing.Single machine scheduling with learning effect considerations［J］.Ann Oper Res，2000，98（1／2／3／4）：273－290.

［6］孫林輝，王丹，王吉波.具有學(xué)習(xí)效應(yīng)的總完工時(shí)間流水作業(yè)問(wèn)題［J］.系統(tǒng)管理學(xué)報(bào)，2011，20（1）：114－118.

［7］MOSHEIOV G.Scheduling problems with a learning effect［J］.Eur J Oper Res，2001，132（3）：687－693.

［8］BISKUP D.A state－of－the－art review on scheduling with learning effects［J］.Eur J Oper Res，2008，188（2）：315－329.

［9］RUDEK R.Computational complexity and solution algorithms for flowshop scheduling problems with the learning effect［J］.Comput Ind Eng，2011，61（1）：20－31.

［10］王吉波，劉璐.帶準(zhǔn)備時(shí)間的任務(wù)單機(jī)學(xué)習(xí)效應(yīng)排序問(wèn)題［J］.大連理工大學(xué)學(xué)報(bào)，2013，53（6）：930－936.

［11］WANG Jibo，WANG Mingzheng.Worst－case analysis for flow shop scheduling problems with an exponential learning effect［J］.J Oper Res Soc，2012，63（1）：130－137.

［12］WANG Xiaoyuan，ZHOU Zhili，ZHANG Xi，et al.Several flow shop scheduling problems with truncated positionbased learning effect［J］.Comput Oper Res，2013，40（12）：2906－2929.

［13］LI Gang，WANG Xiaoyuan，WANG Jibo，et al.Worst case analysis of flow shop scheduling problems with a timedependent learning effect［J］.Int J Prod Econ，2013，142（1）：98－104.

［14］LEE Wenchiung，CHUNG Yuhsiang.Permutation flowshop scheduling to minimize the total tardiness with learning effects［J］.Int J Prod Econ，2013，141（1）：327－334.

［15］GAWIEJNOWICZ S.Time－dependent scheduling［M］.Berlin：Springer，2008.

［16］WANG Jibo，WANG Jianjun，JI Ping.Scheduling jobs with chain precedence constraints and deteriorating jobs［J］.J Oper Res Soc，2011，62（9）：1765－1770.

［17］王吉波，王建軍，何平.具有共同松弛時(shí)間的惡化型工件排序問(wèn)題研究［J］.大連理工大學(xué)學(xué)報(bào)，2012，52（6）：932－936.

［18］WANG Jibo，WANG Mingzheng.Minimizing makespan in three－machine flow shops with deteriorating jobs［J］.Comput Oper Res，2013，40（2）：547－557.

［19］王吉波，劉璐，許揚(yáng)韜，等.具有惡化工件的不同工期指派問(wèn)題研究［J］.沈陽(yáng)航空航天大學(xué)學(xué)報(bào)，2013，30（5）：81－87.

［20］LEE Wenchiung.A note on deteriorating jobs and learning in single－machine scheduling problems［J］.Int J Business Econ，2004，3（1）：83－89.

［21］WANG Jibo.A note on scheduling problems with learning effect and deteriorating jobs［J］.Int J Syst Sci，2006，37（12）：827－833.

［22］WANG Jibo.Single－machine scheduling problems with the effects of learning and deterioration［J］.Omega，2007，35（4）：397－402.

［23］WANG Jibo，CHENG T C Edwin.Scheduling problems with the effects of deterioration and learning［J］.Asia Pac J Oper Res，2007，24（2）：245－261.

［24］WANG Jibo.Single machine scheduling with a time－dependent learning effect and deteriorating jobs［J］.J Oper Res Soc，2009，60（4）：583－586.

［25］WANG Jibo，HUANG Xue，WANG Xiaoyuan，et al.Learning effect and deteriorating jobs in the single machine scheduling problems［J］.Appl Math Model，2009，33（10）：3848－3853.

［26］WANG Jibo，GUO Qian.A due－date assignment problem with learning effect and deteriorating jobs［J］.Appl Math Model，2010，34（2）：309－313.

［27］WANG Jibo，WANG Cheng.Single－machine due－window assignment problem with learning effect and deteriorating jobs［J］.Appl Math Model，2011，35（8）：4017－4022.

［28］WANG Jibo，WANG Mingzheng，JI Ping.Single machine total completion time minimization scheduling with a timedependent learning effect and deteriorating jobs［J］.Int J Syst Sci，2012，43（5）：861－868.

［29］LOW Chinyao，LIN Wenyi.Some scheduling problems with time－dependent learning effect and deteriorating jobs［J］.Appl Math Model，2013，37（20）：8865－8875.

［30］SEIDMANN A，PANWALKAR S S，Smith M L.Optimal assignment of due－dates for a single processor scheduling problem［J］.Int J Prod Res，1981，19（4）：393－399.