伏娟

摘 要：排序問題是一類具有廣泛實際背景的組合最優(yōu)化問題，應(yīng)用于眾多領(lǐng)域。隨著現(xiàn)代工業(yè)的發(fā)展，排序模型被不斷突破。在一些排序模型中，如果所有工件都不被拒絕，當(dāng)一個工件的加工時間或加工費用太大時，將導(dǎo)致完工時間變大或費用太大，因此需要考慮該工件是否被加工。若工件被拒絕則有一個懲罰費用。該文研究帶有拒絕的不同類型機排序問題，工件的實際加工時間是與工件位置的一般函數(shù)，目標函數(shù)是極小化接受工件的排序指標與拒絕工件總懲罰之和。

關(guān)鍵詞：不同類型機排序 與位置相關(guān) 拒絕 排序

中圖分類號：O2 文獻標識碼：A 文章編號：1674-098X（2015）07（b）-0214-02

排序問題也稱調(diào)度問題或時間表理論，是運籌學(xué)的一個分支，有特別廣闊的實際背景和應(yīng)用前景。鐵路上的火車調(diào)度，公共服務(wù)問題，宇宙飛船的飛行計劃，學(xué)校課程表的制定等等，都要用到排序理論。在工業(yè)生產(chǎn)過程中，工件的加工時間往往依賴于工件的實際加工位置。Mosheiov[1]提出工件的實際加工時間是與工件原有加工時間和位置相關(guān)的函數(shù)，其中，給出了總時間表長，總完工時間的多項式時間算法。Gordon[2]提出工件的實際加工時間是與工件原有加工時間和位置指數(shù)相關(guān)的函數(shù)，其中，并給出了總時間表長，總完工時間的多項式時間算法。Wang等[3]研究了加工時間與開始加工時間相關(guān)的，三臺機器同順序流水作業(yè)的排序問題，目標函數(shù)為最大完工時間。Gerstl等[4]研究了工件的加工時間與位置相關(guān)的、帶有拒絕的平行機排序問題，目標函數(shù)為總完工時間。研究表明當(dāng)機器的數(shù)量固定時，此問題可以轉(zhuǎn)化成指派問題。Wang等[5]研究了帶有指數(shù)學(xué)習(xí)效應(yīng)和一般函數(shù)退化效應(yīng)的單機排序問題，其中工件的加工時間是由工件的開始加工時間和工件的位置決定的，目標函數(shù)分別為最大完工時間和總完工時間，證明了它們是多項式時間可解的。Kuo等[6]證明了問題是多項式時間可解的，算法復(fù)雜性為。Kuo等[7]證明了在給定每臺機器加工的工件數(shù)前提下，問題是多項式時間可解的。

1 問題描述

假設(shè)有個工件，需要在臺變速處理機上被加工。在工件存在拒絕的情況下，即工件可能不被加工，但由此可能產(chǎn)生已定的代價。其中接受工件的個數(shù)為，拒接工件個數(shù)為，。接受工件在臺變速處理機上加工，每臺處理機的容量是一定的，分別為，且。如果工件被拒絕，則有一個懲罰費用。

工件的實際加工時間與工件的基本加工時間和其在處理機上的位置相關(guān)，即。工件的總完工時間為。該文研究帶有拒絕情況下，加工時間與位置相關(guān)的不同類型機排序問題，運用三參數(shù)表示法，表示為：

2 主要性質(zhì)

假設(shè)1.在工件的加工過程中，機器無空閑。即工件在第臺處理機第個位置加工，第位置不能為空，若為空，工件必須放置在第個位置。

引理1.工件在每臺工件上的完工時間分別為：

定理1.問題存在時間復(fù)雜性為的最優(yōu)算法。

證明：工件的總完工時間為：

則帶有拒絕的目標函數(shù)可化簡為：

（1）

由上式可知，這個問題可以轉(zhuǎn)化成指派問題。矩陣的行表示被加工工件，矩陣的列表示工件可能被加工的位置。矩陣包含兩塊（接受矩陣和拒絕矩陣），分別表示有個加工工件和個拒絕工件。對于一個給定向量，機器有列個位置分配。由于不知道工件被拒絕的數(shù)量，第二塊包含列，第二塊的維數(shù)為。因此，指派矩陣的總維數(shù)為。

下面，先定義矩陣的費用值。第一塊包含工件的加工時間與它們在相應(yīng)機器上位置權(quán)的乘積。通過等式（1），在機器上位置的位置權(quán)：

第二塊對角線上的值為，其余均為無窮。為了方便起見，定義第二塊（也就是拒絕工件）作為第臺機器。這臺機器包含個可能排列的位置，這意味著這塊包含列，位置從到。定義的值：

它表示把工件指派在機器上位置的費用。另外，令為變量，如果工件排在機器上位置時，；否則。因此，上面討論的排序問題可以歸結(jié)為下面的指派問題：

對于一個給定的向量，當(dāng)時，可能取值為。如果已知前臺機器的工件數(shù)且，那么最后一臺機器加工的工件數(shù)也唯一確定。得出分配向量的數(shù)量上界為。該過程需要重復(fù)執(zhí)行所有可能的次，（）。因此，該問題要運行的總次數(shù)為。已知指派問題的算法復(fù)雜性為，因此問題存在時間復(fù)雜性為的多項式時間算法。

3 結(jié)論

該文研究帶有拒絕的不同類型機排序問題，工件的實際加工時間是與工件位置的一般函數(shù)，目標函數(shù)是極小化接受工件的排序指標與拒絕工件總懲罰之和。通過將問題轉(zhuǎn)化為指派問題，證明了問題是多項式可解的。對于其他目標函數(shù)，如最大完工時間，總誤工工件數(shù)和最大延誤時間等，也可進行研究，我們將繼續(xù)努力。

參考文獻

[1]Mosheiov G. A note on scheduling deteriorating jobs[J].Mathematical and ComputeModelling，2005， 41（8）：883-886.

[2]Gordon V S， Potts C N， Strusevich V A， et al. Single machine scheduling models with deterioration and learning： handling precedence constraints via priority generation[J].Journal of Scheduling，2008， 11（5）：357-370.

[3]WANG Jibo， WANG Mingzheng. Minimizing makespan in three-machine flow shops with deteriorating jobs[J].Comput Oper Res，2013， 40（2）：547-557.

[4]Gerstl E， Mosheiov G. Scheduling on parallel identical machines with job-rejection and position-dependent processing times[J].Inf Process Lett， 2012，112（19）：743-747.

[5]WANG Jibo， Hsu C J， Yang D L. Single-machine scheduling with effects of exponential learning and general deterioration[J].Appl Math Modell，2013，37（4）：2293-2299.

[6]Kuo W H， Yang D L. Parallel-machine scheduling with time dependent processing times[J]. Theor Comput Sci，2008，393（1）：204-210.

[7]Kuo W H， Hsu C J， Yang D L. A note on unrelated parallel machine scheduling with time-dependent processing times[J].J Oper Res Soc， 2008，60（3）：431-434.