具有學(xué)習(xí)效應(yīng)且工件可拒絕單機(jī)排序問(wèn)題探討

1、 具有學(xué)習(xí)效應(yīng)且工件可拒絕單機(jī)排序問(wèn)題探討 余英羅永超Summary：文章對(duì)工件具有與已加工工件有關(guān)的安裝時(shí)間且工件的加工時(shí)間具有學(xué)習(xí)效應(yīng)的工件可拒絕的排序問(wèn)題進(jìn)行了研究；對(duì)目標(biāo)函數(shù)為極小化最大完工時(shí)間與總拒絕費(fèi)用之和以及極小化完工時(shí)間和與總拒絕費(fèi)用之和分別給出了一個(gè)動(dòng)態(tài)規(guī)劃算法。Key：?jiǎn)螜C(jī)排序；學(xué)習(xí)效應(yīng)；工件可拒絕；動(dòng)態(tài)規(guī)劃算法；目標(biāo)函數(shù) ：A：O223 ：1009-2374（2015）29-0078-02 DOI：10.13535/ki.11-4406/n.2015.29.039具有學(xué)習(xí)效應(yīng)的排序問(wèn)題首先由Biskup提出，他假設(shè)工件的加工時(shí)間隨著熟練程度的提高而越來(lái)越短，即工件越往后加

2、工，所需的時(shí)間將減少。隨后，Mosheiov和Sidney、Biskup和Simons、Koulamas和Kyparisis等進(jìn)行了相關(guān)的研究。更多相關(guān)研究可Reference5至Reference9。王吉波研究了工件的加工時(shí)間與已加工工件有關(guān)的學(xué)習(xí)效應(yīng)的排序問(wèn)題，并指出最小化最大完工時(shí)間、完工時(shí)間和以及完工時(shí)間平方和是多項(xiàng)式時(shí)間可求解的，而最小化加權(quán)完工時(shí)間和、最大延誤在一定條件下是多項(xiàng)式時(shí)間可求解的。工件可拒絕的排序模型首先由Y.Bartal等提出，他們分別研究了離線情形和在線情形下的的排序模型。S.S.Selden等探討了極小化總拒絕費(fèi)用和最大完工時(shí)間之和的可中斷平行機(jī)模型。Y.He和X

3、.Min研究了兩臺(tái)同類機(jī)以及三臺(tái)同類機(jī)可拒絕的排序的一個(gè)特殊情形。D.Engels等證明了是NP-困難的，并給出了偽多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法和FPTAS算法。S.Sengupta對(duì)目標(biāo)函數(shù)為極小化總拒絕費(fèi)用與最大延遲/延誤的可拒絕排序模型進(jìn)行了研究。本文在Reference10的模型的基礎(chǔ)上，研究了工件可拒絕的排序問(wèn)題，對(duì)原有理論進(jìn)行了擴(kuò)展。1 問(wèn)題假設(shè)有一工件集需要在一臺(tái)機(jī)器上加工，機(jī)器一次只能加工一個(gè)工件，且工件加工不可中斷。工件排在第個(gè)位置加工的實(shí)際加工時(shí)間為，其中為工件的正常加工時(shí)間，為排在第個(gè)位置的工件的正常加工時(shí)間，為常數(shù)。任一工件在加工前有一安裝時(shí)間，第個(gè)位置的工件的安裝時(shí)間為，

4、且有，其中為常數(shù)，為排在第個(gè)位置工件的實(shí)際加工時(shí)間。以下將這類安裝時(shí)間簡(jiǎn)記為。工件在加工過(guò)程中，由于有的工件加工時(shí)間非常長(zhǎng)或費(fèi)用很大，因此采取不加工此工件，而是通過(guò)支付一定的費(fèi)用后送到外面去“外加工”或購(gòu)買更合算。假設(shè)工件的拒絕費(fèi)用為，表示加工工件的集合，表示拒絕工件的集合，所研究問(wèn)題用參數(shù)法表示為：2 的動(dòng)態(tài)規(guī)劃算法引理：?jiǎn)栴}存在一個(gè)最優(yōu)序，在該序中工件按的非降序排列。證明：不妨假設(shè)工件序?yàn)?，其中加工工件為，則：，所以的非降序?yàn)閱?wèn)題的一個(gè)最優(yōu)序。首先將工件按的非降序?yàn)楣ぜ幪?hào)。用表示已加工工件數(shù)為個(gè)，且已排工件所對(duì)應(yīng)的最優(yōu)目標(biāo)函數(shù)值，那么該動(dòng)態(tài)規(guī)劃算法的邊界條件為：現(xiàn)在考慮對(duì)于工件且加工工件

5、個(gè)數(shù)為的任意最優(yōu)排序。對(duì)于工件，此時(shí)有兩種選擇，即拒絕加工或者加工。當(dāng)加工工件時(shí)，其中表示已加工工件中排在第個(gè)位置的工件的正常加工時(shí)間，表示已加工工件中排在第個(gè)位置的工件的實(shí)際加工時(shí)間。當(dāng)拒絕加工時(shí)，。綜合以上兩種情況有：該問(wèn)題的最優(yōu)值為。在這個(gè)動(dòng)態(tài)規(guī)劃算法中，我們需要計(jì)算個(gè)的值，其中計(jì)算每個(gè)值需要的時(shí)間，所以這個(gè)動(dòng)態(tài)規(guī)劃算法的計(jì)算復(fù)雜性為。3 的動(dòng)態(tài)規(guī)劃算法引理：?jiǎn)栴}存在一個(gè)最優(yōu)序，在該序中工件按的非降序排列。證明：不妨假設(shè)工件序?yàn)?，其中加工工件為，則：可知的非降序?yàn)閱?wèn)題的一個(gè)最優(yōu)序。首先將工件按的非降序?yàn)楣ぜ幪?hào)。用表示已加工工件數(shù)為個(gè)，且已排工件所對(duì)應(yīng)的最優(yōu)目標(biāo)函數(shù)值，那么該動(dòng)態(tài)規(guī)劃算法

6、的邊界條件為：現(xiàn)在考慮對(duì)于工件且加工工件個(gè)數(shù)為的任意最優(yōu)排序，對(duì)于工件，此時(shí)有兩種選擇，即拒絕加工或者加工。當(dāng)加工工件時(shí)，其中表示已加工工件中排在第個(gè)位置的工件的實(shí)際加工時(shí)間。當(dāng)拒絕加工時(shí)，。綜合以上兩種情況有：該問(wèn)題的最優(yōu)值為。在這個(gè)動(dòng)態(tài)規(guī)劃算法中，我們需要計(jì)算個(gè)的值，其中計(jì)算每個(gè)值需要的時(shí)間，所以這個(gè)動(dòng)態(tài)規(guī)劃算法的計(jì)算復(fù)雜性為。4 結(jié)語(yǔ)本文對(duì)可拒絕加工的一類排序問(wèn)題進(jìn)行了研究，其中工件的加工時(shí)間具有學(xué)習(xí)效應(yīng)，安裝時(shí)間與已加工工件有關(guān)，對(duì)兩類目標(biāo)函數(shù)分別給出了動(dòng)態(tài)規(guī)劃算法。讀者可以繼續(xù)研究多機(jī)環(huán)境下相關(guān)的問(wèn)題。Reference1 Bisup D.Single machine schedul

7、ing with learning considerationgsJ.European Journal of Operational Research，1999，115（1）.2 Mosheiov G.Sidney J B.Scheduling with general job-dependent learning curveJ.European Journal of Operational Research，2003，147（3）.3 Bisup D，Simons D.Common due date scheduling with autonomous and induced learnin

8、gJ.European Journal of Operational Research，2004，159（3）. 4 Koulamas C，Kyparisis G J.Single-machine and two-machine flowshop scheduling with general learning functionsJ.European Journal of Operational Research，2007，178（2）.5 Kuo W H，Yang D L.Single machine scheduling with past sequence-dependent setup

9、 times and learning effectsJ.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 effectJ.European Journal of Operational Research，2013，227.7 Kuo W H，Yang D L.Minimizing the total completion time

10、 in a single-machine scheduling problem with a time-dependent learning effectJ.European Journal of Operational Research，2006，（174）.8 Li S.Single-machine scheduling problem with deteriorating jobs and learning effectsJ.Computer and Indusrial engineering，2009，57.9 程明寶.工件具有指數(shù)學(xué)習(xí)效應(yīng)的流水作業(yè)排序問(wèn)題J.暨南大學(xué)學(xué)報(bào)（自然科學(xué)版

11、），2008，29（1）.10 Wang J B.Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effectJ.Computers and Industrial Engineering，2008，55.11 Y.Bartal，S.Leonardi，A.Marchctti-Spaccamela，J.Sgall and L.Stougie.Multiprocessor scheduling with rejectionJ.SIAM Journal of Discrete Maths，2000，（13）.12 S.S.Seiden.Preemptive multiprocessor scheduling with rejectionJ.Theoretical Computer Science，2001，2621.13 Y.He and x.Min.On-line uniform machin