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

余英　羅永超

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

關鍵詞：單機排序；學習效應；工件可拒絕；動態規劃算法；目標函數 文獻標識碼：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]的模型的基礎上，研究了工件可拒絕的排序問題，對原有理論進行了擴展。……