與位置相關并帶有拒絕的不同類型機排序問題

伏娟

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

關鍵詞：不同類型機排序 與位置相關 拒絕 排序

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

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

1 問題描述

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

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

2 主要性質

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

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

定理1.問題存在時間復雜性為的最優算法。

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

則帶有拒絕的目標函數可化簡為：

（1）

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

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

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

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

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

3 結論

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

參考文獻

[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.