余英　羅永超

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

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

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

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

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

工件可拒絕的排序模型首先由Y.Bartal等提出，他們分別研究了離線情形和在線情形下的的排序模型。S.S.Selden等探討了極小化總拒絕費(fèi)用和最大完工時(shí)間之和的可中斷平行機(jī)模型。Y.He和X.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)行了研究。

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

1 問題假設(shè)

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

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

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

證明：不妨假設(shè)工件序?yàn)?，其中加工工件為，則：

，

所以的非降序?yà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ì)于工件且加工工件個(gè)數(shù)為的任意最優(yōu)排序。對(duì)于工件，此時(shí)有兩種選擇，即拒絕加工或者加工。

當(dāng)加工工件時(shí)，，其中表示已加工工件中排在第個(gè)位置的工件的正常加工時(shí)間，表示已加工工件中排在第個(gè)位置的工件的實(shí)際加工時(shí)間。

當(dāng)拒絕加工時(shí)，。

綜合以上兩種情況有：

該問題的最優(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ī)劃算法

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

證明：不妨假設(shè)工件序?yàn)?，其中加工工件為，則：

可知的非降序?yà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ì)于工件且加工工件個(gè)數(shù)為的任意最優(yōu)排序，對(duì)于工件，此時(shí)有兩種選擇，即拒絕加工或者加工。

當(dāng)加工工件時(shí)，，其中表示已加工工件中排在第個(gè)位置的工件的實(shí)際加工時(shí)間。

當(dāng)拒絕加工時(shí)，。

綜合以上兩種情況有：

該問題的最優(yōu)值為。

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

4 結(jié)語

本文對(duì)可拒絕加工的一類排序問題進(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)的問題。

參考文獻(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é)報(bào)（自然科學(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.

基金項(xiàng)目：1.貴州凱里學(xué)院院級(jí)科研課題重點(diǎn)課題：基于非恒定加工時(shí)間的若干排序問題的研究（Z1402）；2.貴州省科學(xué)技術(shù)基金項(xiàng)目：基于共同交貨期的提前延誤排序問題（黔科合LH字[2014]7232）；3.凱里學(xué)院2014年重點(diǎn)學(xué)科（數(shù)學(xué)）（KZD2014004）。

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

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