與位置相關(guān)并帶有拒絕的不同類(lèi)型機(jī)排序問(wèn)題

伏娟

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

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

中圖分類(lèi)號(hào)：O2 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2015）07（b）-0214-02

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

1 問(wèn)題描述

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

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

2 主要性質(zhì)

假設(shè)1.在工件的加工過(guò)程中，機(jī)器無(wú)空閑。即工件在第臺(tái)處理機(jī)第個(gè)位置加工，第位置不能為空，若為空，工件必須放置在第個(gè)位置。

引理1.工件在每臺(tái)工件上的完工時(shí)間分別為：

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

證明：工件的總完工時(shí)間為：

則帶有拒絕的目標(biāo)函數(shù)可化簡(jiǎn)為：

（1）

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

下面，先定義矩陣的費(fèi)用值。第一塊包含工件的加工時(shí)間與它們?cè)谙鄳?yīng)機(jī)器上位置權(quán)的乘積。通過(guò)等式（1），在機(jī)器上位置的位置權(quán)：

第二塊對(duì)角線上的值為，其余均為無(wú)窮。為了方便起見(jiàn)，定義第二塊（也就是拒絕工件）作為第臺(tái)機(jī)器。這臺(tái)機(jī)器包含個(gè)可能排列的位置，這意味著這塊包含列，位置從到。定義的值：

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

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

3 結(jié)論

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

參考文獻(xiàn)

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