帶有學習效應和退化效應的可拒絕排序問題

金 亭, 趙傳立

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

?

帶有學習效應和退化效應的可拒絕排序問題

金 亭, 趙傳立

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

討論了具有學習效應和退化效應的多窗口的可拒絕單機排序問題。工件的實際加工時間與開始加工時間和所排位置有關。工件集分為接受工件集和拒絕工件集,對于被拒絕加工的工件而言,它的費用只與工件有關,目標是確定接受工件集的最優加工順序和拒絕費用,從而極小化2個費用函數。考慮2個問題,第1個問題的目標函數是與提前、延誤、窗口的開始時間、窗口的大小以及拒絕費用有關的函數,第2個問題的目標函數是與提前、延誤工件數、窗口的開始時間、窗口的大小以及拒絕費用有關的函數,并且針對這2個問題分別給出了多項式時間算法。

單機; 排序; 學習效應; 退化效應; 拒絕

0 引 言

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

本文考慮帶有學習效應和退化效應的多窗口的可拒絕單機排序問題。將學習效應和退化效應與多窗口相結合,目標是確定被接受工件的最優加工順序和拒絕費用,從而極小化2個費用函數。考慮2個問題,第1個問題的目標函數是與提前、延誤、窗口的開始時間、窗口的大小以及拒絕有關的函數,第2個問題的目標函數是與提前、延誤工件數、窗口的開始時間、窗口的大小以及拒絕費用有關的函數,針對這2個問題分別給出了多項式時間算法。

1 問題描述

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

其中:r表示工件Jj的加工位置;a≤0表示工件Jj的學習指標;b≥0表示工件的惡化率。

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

若工件Jj被拒絕,則產生相應的費用為ej,j=1,2,…,n。工件集R的費用可以描述為:

這2類問題的目標函數分別是:

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

2 問題1

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

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

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

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

綜上可得:

其中

表示在排序σ中排在第j個位置上的工件的位置權。容易驗證上述結論對這個問題也同樣適用。

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

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

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

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

此處

Wj=jaΩj(j∈A)

表示在排序σ中排在第j個位置上的工件的位置權。則

當1≤h

算法1:

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

步驟4 通過解決動態規劃問題來確定最優排序。

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

1) 若Jj被拒絕。此時在前j-1個工件中,已有m個工件被接受,因此目標函數值表示為:

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

2) 若Jj被接受。此時在前j-1個工件中,恰好有m-1個工件被接受,因此目標函數值表示為:

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

注意:

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

因此,有

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

綜合以上2種情況,給出以下動態規劃算法DP:

邊界條件:

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

遞推式:

對于給定的h,目標函數值表示如下:

F*(h)=Fn(h)

最優的目標函數值F*可以表示如下:

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

對于給定的h,上述動態規劃算法DP中有j≤n,m≤h≤n,所以動態規劃算法DP在O(n2)時間內可解。對于h=1,2,…,n,分別運行算法1,從得到的解中選取最小的目標函數值,即得到問題的最優解。

定理1 問題

存在計算復雜性是O(n2)的最優算法。

3 問題2

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

1) 所有工件都連續加工,機器無空閑,且第一個工件在零時刻開始加工。

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

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

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

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

根據引理3,目標函數可以經過推導整理成如下形式:

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

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

定理2 問題

存在計算復雜性是O(n5)的最優算法。

4 結 論

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

[ 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 ]陳東,趙傳立. 帶有維修活動和工件可拒絕的單機排序問題[J]. 沈陽師范大學學報:自然科學版, 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]范雁鵬,趙傳立. 帶有學習效應和加工時間可控的單機排序問題[J]. 沈陽師范大學學報:自然科學版, 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。

遼寧省教育廳科學研究一般項目(L2014433)。

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

1673-5862(2015)03-0358-07

O223

A

10.3969/ j.issn.1673-5862.2015.03.009