金 亭, 趙傳立

(沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽 110034)

?

帶有學(xué)習(xí)效應(yīng)和退化效應(yīng)的可拒絕排序問題

金 亭, 趙傳立

(沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽 110034)

討論了具有學(xué)習(xí)效應(yīng)和退化效應(yīng)的多窗口的可拒絕單機(jī)排序問題。工件的實(shí)際加工時(shí)間與開始加工時(shí)間和所排位置有關(guān)。工件集分為接受工件集和拒絕工件集,對于被拒絕加工的工件而言,它的費(fèi)用只與工件有關(guān),目標(biāo)是確定接受工件集的最優(yōu)加工順序和拒絕費(fèi)用,從而極小化2個(gè)費(fèi)用函數(shù)。考慮2個(gè)問題,第1個(gè)問題的目標(biāo)函數(shù)是與提前、延誤、窗口的開始時(shí)間、窗口的大小以及拒絕費(fèi)用有關(guān)的函數(shù),第2個(gè)問題的目標(biāo)函數(shù)是與提前、延誤工件數(shù)、窗口的開始時(shí)間、窗口的大小以及拒絕費(fèi)用有關(guān)的函數(shù),并且針對這2個(gè)問題分別給出了多項(xiàng)式時(shí)間算法。

單機(jī); 排序; 學(xué)習(xí)效應(yīng); 退化效應(yīng); 拒絕

0 引 言

近年來,帶有學(xué)習(xí)效應(yīng)和退化效應(yīng)的多窗口的可拒絕單機(jī)排序問題備受關(guān)注。Wang等[1]提出了同時(shí)帶有安裝時(shí)間、學(xué)習(xí)效應(yīng)和退化效應(yīng)的單機(jī)排序問題,目標(biāo)是極小化總完工時(shí)間等。Cheng等[2]分析了具有退化效應(yīng)的工件可拒絕排序問題,其目標(biāo)是確定接受工件的最大完工時(shí)間和拒絕費(fèi)用以及加權(quán)總完工時(shí)間和拒絕費(fèi)用。Zhao等[3]等提出了具有多個(gè)工期和多窗口的可拒絕單機(jī)排序,目標(biāo)是極小化提前、延誤、周期和拒絕的懲罰,對不同的問題給出不同的多項(xiàng)式算法。Shabtay[4]提出了和拒絕有關(guān)的單機(jī)排序問題,目標(biāo)是確定接受工件集的最優(yōu)加工順序,從而極小化2個(gè)費(fèi)用函數(shù)。Cheng等[5-6]研究了具有退化效應(yīng)的工期指派問題。Mor等[7]研究了具有交貨期窗口和維修活動(dòng)的單機(jī)排序問題,目標(biāo)是極小化總加權(quán)總完工時(shí)間。趙傳立等[8]討論了帶有不同的交貨期窗口和工件可拒絕的單機(jī)排序問題,需要確定接受工件集的最優(yōu)加工順序和拒絕工件集的懲罰費(fèi)用,并運(yùn)用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。Mosheiov等[11]討論了具有多窗口的可拒絕單機(jī)排序問題,目標(biāo)是確定接受工件集的最優(yōu)加工順序和拒絕費(fèi)用,從而極小化2個(gè)費(fèi)用函數(shù)。

本文考慮帶有學(xué)習(xí)效應(yīng)和退化效應(yīng)的多窗口的可拒絕單機(jī)排序問題。將學(xué)習(xí)效應(yīng)和退化效應(yīng)與多窗口相結(jié)合,目標(biāo)是確定被接受工件的最優(yōu)加工順序和拒絕費(fèi)用,從而極小化2個(gè)費(fèi)用函數(shù)?？紤]2個(gè)問題,第1個(gè)問題的目標(biāo)函數(shù)是與提前、延誤、窗口的開始時(shí)間、窗口的大小以及拒絕有關(guān)的函數(shù),第2個(gè)問題的目標(biāo)函數(shù)是與提前、延誤工件數(shù)、窗口的開始時(shí)間、窗口的大小以及拒絕費(fèi)用有關(guān)的函數(shù),針對這2個(gè)問題分別給出了多項(xiàng)式時(shí)間算法。

1 問題描述

給定一臺(tái)機(jī)器和一個(gè)工件集J={J1,J2,…,Jn},其中包含了n個(gè)相互獨(dú)立的,無優(yōu)先約束的工件,所有工件在零時(shí)刻到達(dá),不允許中斷。工件Jj的基本加工時(shí)間為pj,若Jk排在第r個(gè)位置,其開始時(shí)間為t,工件Jj的實(shí)際加工時(shí)間可以表示為

其中:r表示工件Jj的加工位置;a≤0表示工件Jj的學(xué)習(xí)指標(biāo);b≥0表示工件的惡化率。

對于給定的排序σ=(J[1],J[2],…,J[h]),將工件集J劃分為A和R兩個(gè)不相交的子集,其中A表示接受工件集,R表示拒絕工件集。若工件Jj被接受,工件集A的費(fèi)用可以描述為:

若工件Jj被拒絕,則產(chǎn)生相應(yīng)的費(fèi)用為ej,j=1,2,…,n。工件集R的費(fèi)用可以描述為:

這2類問題的目標(biāo)函數(shù)分別是:

用三參數(shù)的表示法,本文考慮的問題可以記為如下形式:

2 問題1

首先,考慮工件全部接受的特殊情況,即:σ=(J[1],J[2],…,J[n]),此時(shí)有

引理1 對于問題(4),存在最優(yōu)排序σ=(J[1],J[2],…,J[n])滿足以下性質(zhì):

引理2 對于問題(4),在最優(yōu)排序σ*=(J[1],J[2],…,J[n])中,存在某個(gè)k和l使得

對于任意一個(gè)給定的排序σ=(J[1],J[2],…,J[n]),由引理1,2,3的相關(guān)性質(zhì)可將目標(biāo)函數(shù)作如下化簡:

綜上可得:

其中

表示在排序σ中排在第j個(gè)位置上的工件的位置權(quán)。容易驗(yàn)證上述結(jié)論對這個(gè)問題也同樣適用。

由式(6)及性質(zhì)可知,式(2)可表示為:

其中Wj=jaΩj(j=1,2,3,…,n),即

1) 對于工件全部接受的情況,給出如下求解方法:

2) 討論接受工件集A中工件個(gè)數(shù)為h的情況,由于h=0是平凡問題,所以設(shè)1≤h

此處

Wj=jaΩj(j∈A)

表示在排序σ中排在第j個(gè)位置上的工件的位置權(quán)。則

當(dāng)1≤h

算法1:

步驟3 將工件按照SPT規(guī)則排序,即:p[1]≤p[2]≤…≤p[h];

步驟4 通過解決動(dòng)態(tài)規(guī)劃問題來確定最優(yōu)排序。

對于給定的h,設(shè)Fj(m)是極小化部分排序σ=(J1,J2,…,Jj)的目標(biāo)函數(shù),其中有m個(gè)工件恰好被接受。在任意一個(gè)這樣的排序中,把工件Jj分2種情況討論:Jj被拒絕或者Jj被接受并在機(jī)器上加工。

1) 若Jj被拒絕。此時(shí)在前j-1個(gè)工件中,已有m個(gè)工件被接受,因此目標(biāo)函數(shù)值表示為:

Fj(m)=Fj-1(m)+ej

2) 若Jj被接受。此時(shí)在前j-1個(gè)工件中,恰好有m-1個(gè)工件被接受,因此目標(biāo)函數(shù)值表示為:

綜上所述,有如下遞推公式:

注意:

已考慮的工件中被接受的m個(gè)工件與余下未考慮的(n-j)個(gè)工件之和應(yīng)該不少于h,即m≥h-(n-j)。

因此,有

max(0,h-(n-j))≤m≤min(j,h)

綜合以上2種情況,給出以下動(dòng)態(tài)規(guī)劃算法DP:

邊界條件:

F0(0)=0,Fj(m)=∞對于m=-1和j=m-1

遞推式:

對于給定的h,目標(biāo)函數(shù)值表示如下:

F*(h)=Fn(h)

最優(yōu)的目標(biāo)函數(shù)值F*可以表示如下:

其中j≤n,m≤h≤n。

對于給定的h,上述動(dòng)態(tài)規(guī)劃算法DP中有j≤n,m≤h≤n,所以動(dòng)態(tài)規(guī)劃算法DP在O(n2)時(shí)間內(nèi)可解。對于h=1,2,…,n,分別運(yùn)行算法1,從得到的解中選取最小的目標(biāo)函數(shù)值,即得到問題的最優(yōu)解。

定理1 問題

存在計(jì)算復(fù)雜性是O(n2)的最優(yōu)算法。

3 問題2

引理4 對于問題(5),存在最優(yōu)排序σ=(J[1],J[2],…,J[n])滿足如下性質(zhì):

1) 所有工件都連續(xù)加工,機(jī)器無空閑,且第一個(gè)工件在零時(shí)刻開始加工。

3)q(1)的最優(yōu)值等于C[k*-1],q(2)的最優(yōu)值等于C[l*-1],其中k*≤l*≤n,k*=max{n(δ-γ)/α,0}。

引理5 對于問題(2),存在最優(yōu)排序σ=(J[1],J[2],…,J[n])滿足:

其中:m1是滿足min{n(γ+αpj),nδ<βj}的工件數(shù);m2是滿足min{nγ,nδ}>βj的工件數(shù)。

引理6 對于問題(5),給定一個(gè)排序σ=(J[1],J[2],…,J[n]),給定l值,其目標(biāo)函數(shù)值可以表示為

根據(jù)引理3,目標(biāo)函數(shù)可以經(jīng)過推導(dǎo)整理成如下形式:

設(shè)yrj∈{0,1},如果工件Jj排在第r個(gè)位置上,則yrj=1,否則yrj=0,則有如下指派問題。

對于給定的h,上述指派問題在O(n3)時(shí)間內(nèi)可解。對于h=1,2,…,n,h需要n次的迭代,對于一個(gè)給定的l值,l至多也需要n次的迭代。并從得到的解中選取最小的目標(biāo)函數(shù)值,即得到問題的最優(yōu)解。

定理2 問題

存在計(jì)算復(fù)雜性是O(n5)的最優(yōu)算法。

4 結(jié) 論

本文討論了具有學(xué)習(xí)效應(yīng)和退化效應(yīng)的多窗口的可拒絕單機(jī)排序問題。把工件集分為接受工件集和拒絕工件集。目標(biāo)是確定接受工件集的最優(yōu)加工順序和拒絕費(fèi)用,從而極小化2個(gè)費(fèi)用函數(shù)。討論了2個(gè)問題,分別證明了問題1可以在時(shí)間O(n3)內(nèi)得到問題1的最優(yōu)解,問題2可以在時(shí)間O(n5)內(nèi)得到問題2的最優(yōu)解。對于其它類型的拒絕模型還有待更深入的討論。

[ 1 ]WANG Jibo, JIANG Yong, WANG Gang. Single-machine scheduling with past-sequence-de pendent setup times and effects of deterioration and learning[J]. Int J Adv Manuf Technol, 2009,41(11):1221-1226.

[ 2 ]CHENG Yushao, SUN Shijie. Scheduling linear deteriorating jobs with rejection on a single machine[J]. Eur J Oper Res, 2009,194(11):18-27.

[ 3 ]ZHAO Chuanli, YIN Yunqiang, CHENG T C E, et al. Single machine scheduling and due date assignment with rejection and position dependent processing times[J]. J Ind Manage Optim, 2014,10(3):691-700.

[ 4 ]SHABTAY D. The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost[J]. Eur J Oper Res, 2014,233(1):64-74.

[ 5 ]CHENG T C E, KANG L, NG C T. Single machine due-date scheduling of jobs with decreasing start-time dependent processing times[J]. Int Transact Oper Res, 2005,12(3):355-366.

[ 6 ]CHENG T C E, KANG L, NG C T. Due-date assignment and single machine scheduling with deteriorating jobs[J]. J Oper Res Soc, 2004,55:198-203.

[ 7 ]MOR B, MOSHEIOV G. Scheduling a maintenance activity and due-window assignment based on common flow allowance[J]. Int J Prod Econ, 2012,135(1):222-230.

[ 8 ]陳東,趙傳立. 帶有維修活動(dòng)和工件可拒絕的單機(jī)排序問題[J]. 沈陽師范大學(xué)學(xué)報(bào):自然科學(xué)版, 2014,32(2):187-191.

[ 9 ]SHABTAY D, GASPAR N, YEDIDSION L. A bicriteria approach to scheduling a single machine with job rejection and positional penalties[J]. J Comb Optim, 2012,23(4):395-424.

[10]YIN Y Q, CHENG T C E, WU C-C, CHENG S-R. Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time[J]. J Oper Res Soc, 2014,65(1):1-13.

[11]MOSHEIOV G, ORON D. Job-dependent due-window assignment based on a common flow allowance[J]. Foundat Comput De Sci, 2010,35(3):185-195.

[12]WANG Xiuli, CHENG T C E. Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan[J]. Eur J Oper Res, 2007,178(1):57-70.

[13]CHEN K, JIN M, GE J J. A note on scheduling a maintenance activity and due-window assignment based on common flow allowance[J]. Int J Prod Econ, 2013,145(2):645-646.

[14]WANG Jibo, GUO Qian. A due-date assignment problem with learning effect and deteriorating jobs[J]. App Math Model, 2010,34(2):309-313.

[15]WANG Jibo. Single-machine scheduling with the effects of learning and deterioration[J]. Int J Manage Sci, 35(4):397-402.

[16]LIMAN S D, PANWALKAR S S, THONGMEE S. Common due window size and location determination in a single machine scheduling problem[J]. J Oper Res Soc, 1998,49(9):1007-1010.

[17]范雁鵬,趙傳立. 帶有學(xué)習(xí)效應(yīng)和加工時(shí)間可控的單機(jī)排序問題[J]. 沈陽師范大學(xué)學(xué)報(bào):自然科學(xué)版, 2014,32(2):192-196.

Scheduling problems with both learning and deterioration effects and rejection

JINTing,ZHAOChuanli

(School of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110034, China)

We discuss single machine scheduling with both learning and deterioration effects and rejection, in which the jobs have multiple due windows. The actual processing time of accepted jobs is a function of its starting time and position in a sequence. We solve the problem by partitioning the jobs into a set of accepted and a set of rejected jobs. The objective is to determine the optimal sequence of accepted jobs and the cost of the rejected jobs, so as to minimize the total costs. We consider two versions of the problem. For the first version, the total cost includes earliness, tardiness, the starting time of due windows, the size of due windows and rejection cost. For the second version, it includes earliness, the number of tardy jobs, the starting time of due windows, the size of due windows and rejection cost. We present polynomial algorithms for two versions, respectively.

single machine; scheduling; learning effect; deterioration effect; rejection

2015-03-23。

遼寧省教育廳科學(xué)研究一般項(xiàng)目(L2014433)。

金 亭(1991-),女,遼寧興城人,沈陽師范大學(xué)碩士研究生; 通信作者: 趙傳立(1958-),男,黑龍江泰來人,沈陽師范大學(xué)教授,博士,碩士研究生導(dǎo)師。

1673-5862(2015)03-0358-07

O223

A

10.3969/ j.issn.1673-5862.2015.03.009