余英　羅永超

摘要：文章對工件具有與已加工工件有關(guān)的安裝時間且工件的加工時間具有學(xué)習(xí)效應(yīng)的工件可拒絕的排序問題進(jìn)行了研究；對目標(biāo)函數(shù)為極小化最大完工時間與總拒絕費(fèi)用之和以及極小化完工時間和與總拒絕費(fèi)用之和分別給出了一個動態(tài)規(guī)劃算法。

關(guān)鍵詞：單機(jī)排序；學(xué)習(xí)效應(yīng)；工件可拒絕；動態(tài)規(guī)劃算法；目標(biāo)函數(shù) 文獻(xiàn)標(biāo)識碼：A

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

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

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

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

本文在參考文獻(xiàn)[10]的模型的基礎(chǔ)上，研究了工件可拒絕的排序問題，對原有理論進(jìn)行了擴(kuò)展。

1 問題假設(shè)

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

2 的動態(tài)規(guī)劃算法

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

在這個動態(tài)規(guī)劃算法中，我們需要計算個的值，其中計算每個值需要的時間，所以這個動態(tài)規(guī)劃算法的計算復(fù)雜性為。

4 結(jié)語

本文對可拒絕加工的一類排序問題進(jìn)行了研究，其中工件的加工時間具有學(xué)習(xí)效應(yīng)，安裝時間與已加工工件有關(guān)，對兩類目標(biāo)函數(shù)分別給出了動態(tài)規(guī)劃算法。讀者可以繼續(xù)研究多機(jī)環(huán)境下相關(guān)的問題。

參考文獻(xiàn)

[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] 程明寶.工件具有指數(shù)學(xué)習(xí)效應(yīng)的流水作業(yè)排序問題[J].暨南大學(xué)學(xué)報（自然科學(xué)版），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.貴州凱里學(xué)院院級科研課題重點(diǎn)課題：基于非恒定加工時間的若干排序問題的研究（Z1402）；2.貴州省科學(xué)技術(shù)基金項目：基于共同交貨期的提前延誤排序問題（黔科合LH字[2014]7232）；3.凱里學(xué)院2014年重點(diǎn)學(xué)科（數(shù)學(xué)）（KZD2014004）。

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

（責(zé)任編輯：秦遜玉）