同時具有學習和惡化效應的不同工期指派問題研究

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

（1.沈陽航空航天大學 經濟與管理學院，沈陽 110136；2.沈陽航空航天大學 理學院，沈陽 110136）

0 引 言

排序問題是一類重要的組合最優化問題，多年來人們一直在運籌學、管理科學、系統工程、計算機科學等領域致力于該問題的研究。在大多數排序問題中，工件的加工時間是一個獨立的且與開工時間和加工位置無關的常數。不過，在所知的一些實際問題中，由于工人（機器）在很長的時間加工相同或類似的工件時，加工效率有可能逐漸提高，因而使得后面加工的工件的加工時間縮短，這種現象被稱作具有學習效應［1］。另一方面，在實際生產中，工件的實際加工時間會因工件開始時間的推遲而延長，這種現象被稱為具有惡化效應［2－3］。

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

王吉波等［19］研究了工件具有不同工期的排序問題，其中工件的加工時間具有惡化效應。但現實的生產過程中存在著工件加工同時具有學習效應和惡化效應的情況（Wang［21－22］，Wang等［23］），因此本文研究工件加工同時具有學習效應和惡化效應的不同工期排序問題，證明了此問題依然多項式時間可解。

1 問題模型

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

2 主要結論

引理2 （Wang［21］）對于排序問題1｜pj＝（aj＋bt）rθ｜Cmax，最優排序能通過把工件按照aj的非減順序排列得到（SPT規則）。

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

因為ai＜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種情況進行討論。

1）當Ci（S′）≤d時，此時Cj（S）＜Ci（S′）≤d，Ci（S）＜Cj（S）＜d，所以

2）當Ci（S）≥d時，此時Cj（S′）＞Ci（S）≥d，Ci（S′）＞Cj（S）＞d，所以

3）當Ci（S）＜d且Cj（S′）＞d，Cj（S）＜d時，此時Ci（S′）＞Cj（S′）＞d，所以

4）當Ci（S）＜d且Cj（S′）＞d，Cj（S）＞d時，此時Ci（S′）＞Cj（S）＞d，所以

5）當Ci（S）＜d且Cj（S′）＜d，Cj（S）＞d時，此時Ci（S′）＞Cj（S）＞d，所以

6）當Ci（S）＜d且Cj（S′）＜d，Cj（S）＜d，Ci（S′）＞d時

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

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

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

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

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

2）對于情況β＜γ。

因為dj＝min（A，Cj）（根據定理1），可以得出dj≤A和Aj＝0。此時提前完工時間為零，即Ej＝0。

在排序π中，工件i和工件j為2個連續加工的工件，并假設ai＞aj且工件i和工件j分別位于第［i］和第［i＋1］個位置，π1和π2分別為第［i］個位置之前的工件的加工順序和第［i＋1］個位置之后的工件的加工順序，故排序為（π1，Ji，Jj，π2），現利用相鄰交換法來證明結論。

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

然后交換第［i］和第［i＋1］個位置上的工件，其他不變，故排序變為（π1，Jj，Ji，π2），則

因為ai＞aj，所以

1）因為交換后不影響π1中的工件，所以目標函數的提前成本和延遲成本為零，而機會成本則沒有發生變化，因此，總成本不變。

2）下面，來討論一下交換工件Ji和Jj后對總成本的影響。

ⅰ）當C′［i］≤A時，對于工件Ji來說，交換前Ji的懲罰成本為β（C［i］－A），交換后的懲罰成本為β（－A）；對于工件Jj來說，交換前Jj的懲罰成本為β（C［i＋1］－A），交換后的懲罰成本為零，所以交換后對總成本的影響將會變小。

ⅱ）當C′［i］＞A時，對于工件Ji來說，交換前Ji的懲罰成本為β（C［i］－A），交換后的懲罰成本為β（C′［i＋1］－A）；對于工件Jj來說，交換前Jj的懲罰成本為β（C［i＋1］－A），交換后的懲罰成本為β（C′［i］－A）或為零，所以交換后對總成本的影響將會變小。

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

圖1 A的不同位置情況

算法1

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

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

例1 考慮6個工件J＝｛J1，J2，J3，J4，J5，J6｝的排序問題，其中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，因此最優排序為（J6，J3，J2，J1，J5，J4）；

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

下面給出王吉波等［19］類似的算例來說明算法1是如何求解問題

例2 考慮6個工件J＝（J1，J2，J3，J4，J5，J6）的排序問題，其中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，因此最優排序為｛J6，J3，J2，J1，J5，J4｝；

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

3 結論與展望

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

［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］孫林輝，王丹，王吉波.具有學習效應的總完工時間流水作業問題［J］.系統管理學報，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］王吉波，劉璐.帶準備時間的任務單機學習效應排序問題［J］.大連理工大學學報，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］王吉波，王建軍，何平.具有共同松弛時間的惡化型工件排序問題研究［J］.大連理工大學學報，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］王吉波，劉璐，許揚韜，等.具有惡化工件的不同工期指派問題研究［J］.沈陽航空航天大學學報，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.