具有學習效應且工件可拒絕單機排序問題探討

余英　羅永超

摘要：文章對工件具有與已加工工件有關的安裝時間且工件的加工時間具有學習效應的工件可拒絕的排序問題進行了研究；對目標函數為極小化最大完工時間與總拒絕費用之和以及極小化完工時間和與總拒絕費用之和分別給出了一個動態規劃算法。

關鍵詞：單機排序；學習效應；工件可拒絕；動態規劃算法；目標函數 文獻標識碼：A

中圖分類號：O223 文章編號：1009-2374（2015）29-0078-02 DOI：10.13535/j.cnki.11-4406/n.2015.29.039

具有學習效應的排序問題首先由Biskup提出，他假設工件的加工時間隨著熟練程度的提高而越來越短，即工件越往后加工，所需的時間將減少。隨后，Mosheiov和Sidney、Biskup和Simons、Koulamas和Kyparisis等進行了相關的研究。更多相關研究可參考文獻[5]至參考文獻[9]。

王吉波研究了工件的加工時間與已加工工件有關的學習效應的排序問題，并指出最小化最大完工時間、完工時間和以及完工時間平方和是多項式時間可求解的，而最小化加權完工時間和、最大延誤在一定條件下是多項式時間可求解的。

工件可拒絕的排序模型首先由Y.Bartal等提出，他們分別研究了離線情形和在線情形下的的排序模型。S.S.Selden等探討了極小化總拒絕費用和最大完工時間之和的可中斷平行機模型。Y.He和X.Min研究了兩臺同類機以及三臺同類機可拒絕的排序的一個特殊情形。D.Engels等證明了是NP-困難的，并給出了偽多項式時間的動態規劃算法和FPTAS算法。S.Sengupta對目標函數為極小化總拒絕費用與最大延遲/延誤的可拒絕排序模型進行了研究。

本文在參考文獻[10]的模型的基礎上，研究了工件可拒絕的排序問題，對原有理論進行了擴展。

1 問題假設

有一工件集需要在一臺機器上加工，機器一次只能加工一個工件，且工件加工不可中斷。工件排在第個位置加工的實際加工時間為，其中為工件的正常加工時間，為排在第個位置的工件的正常加工時間，，為常數。任一工件在加工前有一安裝時間，第個位置的工件的安裝時間為，且有，其中為常數，為排在第個位置工件的實際加工時間。以下將這類安裝時間簡記為。工件在加工過程中，由于有的工件加工時間非常長或費用很大，因此采取不加工此工件，而是通過支付一定的費用后送到外面去“外加工”或購買更合算。假設工件的拒絕費用為，表示加工工件的集合，表示拒絕工件的集合，所研究問題用參數法表示為：

2 的動態規劃算法

引理：問題存在一個最優序，在該序中工件按的非降序排列。

證明：不妨假設工件序為，其中加工工件為，則：

，

所以的非降序為問題的一個最優序。

首先將工件按的非降序為工件編號。

用表示已加工工件數為個，且已排工件所對應的最優目標函數值，那么該動態規劃算法的邊界條件為：

現在考慮對于工件且加工工件個數為的任意最優排序。對于工件，此時有兩種選擇，即拒絕加工或者加工。

當加工工件時，，其中表示已加工工件中排在第個位置的工件的正常加工時間，表示已加工工件中排在第個位置的工件的實際加工時間。

當拒絕加工時，。

綜合以上兩種情況有：

該問題的最優值為。

在這個動態規劃算法中，我們需要計算個的值，其中計算每個值需要的時間，所以這個動態規劃算法的計算復雜性為。

3 的動態規劃算法

引理：問題存在一個最優序，在該序中工件按的非降序排列。

證明：不妨假設工件序為，其中加工工件為，則：

可知的非降序為問題的一個最優序。

首先將工件按的非降序為工件編號。

用表示已加工工件數為個，且已排工件所對應的最優目標函數值，那么該動態規劃算法的邊界條件為：

現在考慮對于工件且加工工件個數為的任意最優排序，對于工件，此時有兩種選擇，即拒絕加工或者加工。

當加工工件時，，其中表示已加工工件中排在第個位置的工件的實際加工時間。

當拒絕加工時，。

綜合以上兩種情況有：

該問題的最優值為。

在這個動態規劃算法中，我們需要計算個的值，其中計算每個值需要的時間，所以這個動態規劃算法的計算復雜性為。

4 結語

本文對可拒絕加工的一類排序問題進行了研究，其中工件的加工時間具有學習效應，安裝時間與已加工工件有關，對兩類目標函數分別給出了動態規劃算法。讀者可以繼續研究多機環境下相關的問題。

參考文獻

[1] Bisup D.Single machine scheduling with learning considerationgs[J].European Journal of Operational Research，1999，115（1）.

[2] Mosheiov G.Sidney J B.Scheduling with general job-dependent learning curve[J].European Journal of Operational Research，2003，147（3）.

[3] Bisup D，Simons D.Common due date scheduling with autonomous and induced learning[J].European Journal of Operational Research，2004，159（3）.

[4] Koulamas C，Kyparisis G J.Single-machine and two-machine flowshop scheduling with general learning functions[J].European Journal of Operational Research，2007，178（2）.

[5] Kuo W H，Yang D L.Single machine scheduling with past sequence-dependent setup times and learning effects

[J].Information Processing Letters，2007，102.

[6] Jiang Z Y，Chen F F，Kang H Y.Single-machine scheduling problem with actual time-dependent and job-dependent learning effect[J].European Journal of Operational Research，2013，227.

[7] Kuo W H，Yang D L.Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect[J].European Journal of Operational Research，2006，（174）.

[8] Li S.Single-machine scheduling problem with deteriorating jobs and learning effects[J].Computer and Indusrial engineering，2009，57.

[9] 程明寶.工件具有指數學習效應的流水作業排序問題[J].暨南大學學報（自然科學版），2008，29（1）.

[10] Wang J B.Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect[J].Computers and Industrial Engineering，2008，55.

[11] Y.Bartal，S.Leonardi，A.Marchctti-Spaccamela，

J.Sgall and L.Stougie.Multiprocessor scheduling with rejection[J].SIAM Journal of Discrete Maths，2000，（13）.

[12] S.S.Seiden.Preemptive multiprocessor scheduling with rejection[J].Theoretical Computer Science，2001，2621.

[13] Y.He and x.Min.On-line uniform machine scheduling with rejection[J].Computin，2000，65.

基金項目：1.貴州凱里學院院級科研課題重點課題：基于非恒定加工時間的若干排序問題的研究（Z1402）；2.貴州省科學技術基金項目：基于共同交貨期的提前延誤排序問題（黔科合LH字[2014]7232）；3.凱里學院2014年重點學科（數學）（KZD2014004）。

作者簡介：余英（1981-），女，浙江桐廬人，凱里學院數學科學學院教師，副教授，碩士，研究方向：排序理論和組合最優化。

（責任編輯：秦遜玉）