具有指數學習效應和惡化效應的可拒絕單機排序問題

趙玉芳, 李明澤

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

具有指數學習效應和惡化效應的可拒絕單機排序問題

趙玉芳, 李明澤

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

討論了帶有工期窗口的單機排序問題。規定每個被接受的工件都有1個待定的交貨期窗口,且所有工件的交貨期窗口大小相同。工件的實際加工時間為與其開始時間和位置有關的指數函數。1個工件或者被拒絕,或者被接受。被拒絕就要支付拒絕的費用;被接受就會產生相應的提前、延誤懲罰以及最大加工時間的懲罰。研究了2個問題,都需要確定工件的最優排序和窗口的開始時間,第1個問題的目標函數是與窗口的開始時間、窗口的大小、提前時間、延誤時間、最大完工時間以及拒絕費用有關的函數。第2個問題的目標函數是與窗口的開始時間、窗口的大小、提前和延誤的工件數、最大完工時間以及拒絕費用有關的函數。該問題在多項式時間可解,給出了問題的多項式時間算法。

排序; 單機; 指數學習效應; 交貨期窗口; 拒絕

0 引 言

在經典排序理論中,工件的實際加工時間通常沒有考慮與工件實際加工位置的關系。然而,在實踐過程中,許多工件的加工時間都會隨著諸多因素,如:技術工人熟練程度的提高,機器磨合度的增加等而減小,這就是所熟知的學習效應。Biskup[1]首先提出了加工工件具有學習效應的排序問題。Moshevio[2]等擴大了研究范圍,考慮了在實際環境中,機器或者工人的學習過程應該是比較緩慢的因素,解釋了在生產加工過程中一些工件的學習效應比其他工件學習效應快的可能性。Biskup[3]對加工工件具有學習效應的排排序總是給出了全面的綜述。另一種情況是工件的加工時間與其開工時間有關。Cheng等[4]對這一問題的研究給出了綜述。有些研究則考慮同時具有學習和惡化兩種效應的問題。Lee[5]研究了同時具有學習和惡化效應的排序問題。Yang[6]考慮了具有學習和惡化效應的單機排序問題。Cheng等[7]研究了工件的加工時間為pjr=(aj+bjt)·αr-1的排序問題。這一方面的其他研究還有[8-9]。

近年,有關交貨期的排序問題也是備受關注,交貨期的問題是指:若某個工件在交貨期內完工,則不產生任何懲罰費用,如果工件在窗口之前或者之后完工,則會產生提前或者延誤的費用。Saring等[10]研究了具有工期窗口的單機線性排序問題。Zhao等[11]研究了帶有學習效應和退化效應的工期窗口排序問題,目標函數是極小化提前、延誤、工期和拒絕的懲罰,對不同的問題給出不同的多項式算法。

可拒絕問題指的是:在工件的實際加工過程中,某些工件因為外界和自身的因素可能被拒絕加工,并支付相應的懲罰費用。金亭等[12]研究了帶有學習效應和退化效應的可拒絕排序問題,確定被接受工件的最優排序,極小化總費用,證明該問題是多項式時間可解的。Gao等研究了帶有拒絕的單機和同型機排序問題,目標為最小化時間表長與懲罰費用之和。

Mosheiov等[14]研究了工件具有多窗口的單機排序問題,目標是確定接受工件集的最優排序,從而極小化2個費用函數。Mosheiov等[15]研究了單機、帶有工期窗口,并且帶有維修活動的排序問題,目標是極小化與窗口的開始時間、窗口的大小、提前、延誤以及拒絕有關的總費用函數。Wang等[16]討論了單機并且帶有學習效應和惡化效應的排序問題,目標函數是極小化最大完工時間。Yin等[17]研究了具有交貨期窗口的單機排序問題,并且加工時間可控。Shabtay[18]研究了帶有工期指派和資源約束的單機排序問題。文獻[19-22]給出了其他相關研究工作。

本文研究帶有指數學習效應和惡化效應的可拒絕排序問題。將指數學習效應和惡化效應與多窗口相結合,分別研究了2個總費用函數。第1個函數是與窗口的開始時間、窗口的大小、提前、延誤、最大完工時間以及拒絕費用有關的函數;第2個函數是與提前、延誤的工件數、窗口的開始時間、窗口的大小、最大完工時間以及拒絕費用有關的函數。證明了該問題在多項式時間可解,并針對2個問題給出多項式時間算法。

1 問題描述

研究單機問題,工件集J={J1,J2,…,Jn}包含n個相互獨立的工件。所有工件不允許中斷,并且在0時刻均可加工。工件Jj的基本加工時間為pj,其開始時間為t。若Jj排在第r個位置,那么工件Jj的實際加工時間可以表示為

(1)

其中:α為學習指數;bj≥0 為工件的惡化率。

如果工件Jj誤工,那么βj就表示誤工的懲罰費用。反之被接受,接受工件的總費用包括提前、延誤、交貨期窗口的開始時間、交貨期窗口的大小和工件的最大完工時間的總和。將工件集J劃分為接受工件集和拒絕工件集2個不相交的子集,分別用A和R來表示。

因此這2類問題的目標函數分別為

(2)

(3)

其中α,β,γ,δ,θ分別代表提前時間、延誤時間、交貨期窗口的開始時間、交貨期窗口的大小和完工時間的單位費用。

用三參數表示法,本文研究的問題可以記為

問題1:

(4)

問題2:

(5)

2 主要結果

下面將從工件被完全接受以及存在工件被拒絕2個方面討論。

1) 對于工件全部被接受的特殊情況,即π*=(J[1],J[2],…,J[n]),有如下性質:

性質3 在最優排序π=(J1,J2,…,Jn)中,存在某個k和 l,使得

證明 假設存在1個最優排序S,不具備如上性質。因此設

與Δ1、Δ2有關的目標函數可以化為如下形式:

根據以上性質1～性質4,對于任意給定的排序π=(J[1],J[2],…,J[n])。當Δ1、Δ2趨近于0時,可得

因此,可將目標函數化簡如下:

其中,

(11)

(12)

其中Wj=ψjαj-1,j=1,2,…,n

即

根據以上計算過程,給出解法如下:

算法:

步驟 2 根據公式Wj=ψrαr-1,r=1,2,…,n,計算位置權,將工件按照位置權非增的順序排序,即W1≥W2≥…≥Wn;

步驟3 將工件按照基本加工時間遞增的順序排序,即p[1]≤p[2]≤…≤p[n];

步驟4 將Wj與p[j]逆序相乘,即可得到問題1的最優值。

2) 對于工件中被接受工件個數為h的情況

因為h=0是平凡問題,所以設1≤h

針對問題1,當1≤h

針對接受工件數h

(a)Jj被拒絕

那么在前j-1個工件中,恰好有m個工件被接受,因此,目標函數值為

(b)Jj被接受

那么在前j-1個工件中,恰好有m-1個工件被接受,因此,目標函數值為

由此可得遞推公式如下:

因為被接受的工件數為h,故已考慮的被接受的m個工件同剩下的未考慮的(n-j)個工件之和應不少于h,即m≥h-(n-j)。故max(0,h-(n-j))≤m≤min(j,h)。

在以上2種分類的基礎上,給出動態規劃算法DP如下:

邊界條件:

遞推式:

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

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

其中:j≤n;m≤h≤n。故上述動態規劃算法DP中,j≤n,m≤h≤n,所以動態規劃算法DP在O(n2)時間內可解。對于h=1,2,…,n,分別運行算法1,比較所得結果,從中選取最小值,即為問題的最優解。

定理1 問題

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

3 問題2的討論

性質5 對于問題(2),存在最優排序π=(J1,J2,…,Jn)滿足如下性質:

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

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

性質6 給定1個排序π=(J1,J2,…,Jn),針對問題(2)其目標函數可以表示為

令

若h

設yrj∈{0,1},若工件Jj排在第r個位置上,則yrj=1,反之yrj=0,化成指派問題如下:

綜上所述,對于給定的h,計算所有可能的目標函數值,該指派問題在O(n3)時間內可解。

定理2 問題

存在算法復雜度為O(n5)的最優算法。

4 結 論

本文討論了帶有普通流的交貨期窗口問題,工件同時具有指數學習效應和惡化效應并且可拒絕。問題1的目標函數是確定工件的最優排序以及工期窗口的開始時間,極小化與窗口的開始時間、窗口的大小、提前、延誤、總加工時間以及拒絕懲罰總費用有關的函數。首先,證明了該問題在多項式內可解;接著,證明了這種計算方法可以拓展到帶有拒絕的問題上去,并給出了動態規劃算法。問題2的目標函數是與提前、延誤的工件數、窗口的開始時間、窗口的大小、總加工時間以及拒絕費用有關的函數。證明了該問題在時間O(n5)內得到最優解。對于其他同時具有指數學習效應和退化效應的帶有工期窗口的拒絕模型也是非常有價值的,還有待進一步研究。

[ 1 ]BISKUP D. Single-machine scheduling with learning consideration[J]. European Journal of Operational Research, 1999,115(1):173-178.

[ 2 ]MOSHEIOV G, SIDNEY J B. Scheduling with general job-dependent learning curves[J]. European Journal of Research, 2003,147(3):665-670.

[ 3 ]BISKUP D. A state-of-the-art review on scheduling with learning effects[J]. European Journal of Operational Research, 2008,188:315-329.

[ 4 ]CHENG TCE,DING Q, LIN BM T. A concise survey of scheduling with time-dependent processing times[J]. Eur J Oper Res, 2004,152(1):1-13.

[ 5 ]LEE W C,LAI P J. Scheduling problems with general effects of deterioration and learning[J]. Inform Sci, 2011,181:1164-1170.

[ 6 ]YANG S J,Group scheduling problems with simultaneous considerations of learning and deterioration effects on a single machine[J]. Appl Math Model, 2011,35:4008-4016.

[ 7 ]CHENG Mingbao, SUN Shijie.The single-machine scheduling problems with deteriorating jobs and learning effect[J]. Zhejiang Univ SCIENCE A, 2006,7(4):597-601.

[ 8 ]WU Y B, WANG M Z, WANG J B.Some single-machine scheduling with both learning and deterioration effects[J]. Appl Math Model, 2011,35:3731-3736.

[ 9 ]YANG S J,YANG D L. Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities[J]. Comput Math Appl, 2010,60:2161-2169.

[10]MOSHEIOV G, SARIG A. Scheduling with a common due-window: Polynomially solvable case[J]. Information Sciences, 2010,180:1492-1505.

[11]ZHAO Chuanli, TANG Hengyong. Due-window assignment for a single machine scheduling with both deterioration and positional effects[J]. Asia-Pacific Journal of Operational Research,2015,32(3):1550014.

[12]金亭,趙傳立. 帶有學習效應和退化效應的可拒絕單機排序問題[J].沈陽師范大學學報(自然科學版), 2015,33(3):358-364.

[13]GAO Q, LU X W. Scheduling on single machine and identical machines with rejection[J]. Operations Research Transactions, 2014,18(4):1-10.

[14]MOSHEIOV G, ORON D. Job-dependent due-window assignment based on a common flow allowance[J]. Foundations of Computing and Decision Sciences, 2010,35(3):185-195.

[15]MOSHEIOV G, SARIG A. Scheduling a maintenance activity and due-window assignment on a single machine[J].Computers & Operations Research, 2009,36(9):2541-2545.

[16]WANG Xiuli, CHENG T C E. Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan[J]. European Journal of Operational Research, 2007,178(1):57-70.

[17]YIN Yunqiang, CHENG T C E, WU C C, et al. Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time[J]. Journal of the Operational Research Society, 2014,65(1):1-13.

[18]SHABTAY D, STEINER G. The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times[J]. Ann Oper Res, 2008,159(1):25-40.

[19]YANG Shengwu,WAN Long,YIN Na. Research on single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs[J]. Applied Mathematical Modelling, 2015,39(15):4593-4598.

[20]LI Gang, LUO Meiling, ZHANG Wenjie, et al. Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation[J]. International Journal of Production Research, 2015,53(4):1228-1241.

[21]WANG Jibo, WANG Mingzheng. Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times[J]. Asia-Pacific Journal of Operational Research, 2014,31(5):145003.

[22]WANG Jibo, HUANG Xue, WANG Xiaoyuan,et al. Learning effect and deteriorating jobs in the single machine scheduling problems[J]. Applied Mathematical Modelling, 2009,33(10):3848-3853.

Single-machine scheduling problems with rejection and both learning effect and deteriorating jobs

ZHAOYufang,LIMingze

(College of Mathematic and Systems science, Shenyang Normal University, Shenyang 110034, China)

This paper studies the single machine scheduling and due-window assignment problems with learning effect and deteriorating jobs. We assume that the jobs have multiple due windows. And all the due windows have the same size. The processing time of job are defined as functions of their start times and position in a sequence. A job will be rejected, or be accepted. The job which is refused have to pay the cost of the rejected. Jobs completed within the window incur no penalties, other jobs incur either earliness or tardiness penalties. The window location and size, along with the associated job schedule are to be determined to minimizes a certain cost function. The first function is made up of costs associated with the window location, window size, earliness, and tardiness and the makespan costs. The second function is made up of costs associated with the window location, window size, the number of earliness and tardiness jobs and makespan costs. We introduce a polynomial time algorithm for the problem.

scheduling; single machine; learning effect; due-window assignment; rejected

2016-10-12。

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

趙玉芳(1966-),女,遼寧遼陽人,沈陽師范大學副教授,博士。

1673-5862(2017)01-0047-08

O223

A

10.3969/ j.issn.1673-5862.2017.01.009

運籌學與控制論