趙玉芳, 李明澤

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

具有指數(shù)學(xué)習(xí)效應(yīng)和惡化效應(yīng)的可拒絕單機(jī)排序問題

趙玉芳, 李明澤

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

討論了帶有工期窗口的單機(jī)排序問題。規(guī)定每個(gè)被接受的工件都有1個(gè)待定的交貨期窗口,且所有工件的交貨期窗口大小相同。工件的實(shí)際加工時(shí)間為與其開始時(shí)間和位置有關(guān)的指數(shù)函數(shù)。1個(gè)工件或者被拒絕,或者被接受。被拒絕就要支付拒絕的費(fèi)用;被接受就會(huì)產(chǎn)生相應(yīng)的提前、延誤懲罰以及最大加工時(shí)間的懲罰。研究了2個(gè)問題,都需要確定工件的最優(yōu)排序和窗口的開始時(shí)間,第1個(gè)問題的目標(biāo)函數(shù)是與窗口的開始時(shí)間、窗口的大小、提前時(shí)間、延誤時(shí)間、最大完工時(shí)間以及拒絕費(fèi)用有關(guān)的函數(shù)。第2個(gè)問題的目標(biāo)函數(shù)是與窗口的開始時(shí)間、窗口的大小、提前和延誤的工件數(shù)、最大完工時(shí)間以及拒絕費(fèi)用有關(guān)的函數(shù)。該問題在多項(xiàng)式時(shí)間可解,給出了問題的多項(xiàng)式時(shí)間算法。

排序; 單機(jī); 指數(shù)學(xué)習(xí)效應(yīng); 交貨期窗口; 拒絕

0 引 言

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

近年,有關(guān)交貨期的排序問題也是備受關(guān)注,交貨期的問題是指:若某個(gè)工件在交貨期內(nèi)完工,則不產(chǎn)生任何懲罰費(fèi)用,如果工件在窗口之前或者之后完工,則會(huì)產(chǎn)生提前或者延誤的費(fèi)用。Saring等[10]研究了具有工期窗口的單機(jī)線性排序問題。Zhao等[11]研究了帶有學(xué)習(xí)效應(yīng)和退化效應(yīng)的工期窗口排序問題,目標(biāo)函數(shù)是極小化提前、延誤、工期和拒絕的懲罰,對(duì)不同的問題給出不同的多項(xiàng)式算法。

可拒絕問題指的是:在工件的實(shí)際加工過程中,某些工件因?yàn)橥饨绾妥陨淼囊蛩乜赡鼙痪芙^加工,并支付相應(yīng)的懲罰費(fèi)用。金亭等[12]研究了帶有學(xué)習(xí)效應(yīng)和退化效應(yīng)的可拒絕排序問題,確定被接受工件的最優(yōu)排序,極小化總費(fèi)用,證明該問題是多項(xiàng)式時(shí)間可解的。Gao等研究了帶有拒絕的單機(jī)和同型機(jī)排序問題,目標(biāo)為最小化時(shí)間表長與懲罰費(fèi)用之和。

Mosheiov等[14]研究了工件具有多窗口的單機(jī)排序問題,目標(biāo)是確定接受工件集的最優(yōu)排序,從而極小化2個(gè)費(fèi)用函數(shù)。Mosheiov等[15]研究了單機(jī)、帶有工期窗口,并且?guī)в芯S修活動(dòng)的排序問題,目標(biāo)是極小化與窗口的開始時(shí)間、窗口的大小、提前、延誤以及拒絕有關(guān)的總費(fèi)用函數(shù)。Wang等[16]討論了單機(jī)并且?guī)в袑W(xué)習(xí)效應(yīng)和惡化效應(yīng)的排序問題,目標(biāo)函數(shù)是極小化最大完工時(shí)間。Yin等[17]研究了具有交貨期窗口的單機(jī)排序問題,并且加工時(shí)間可控。Shabtay[18]研究了帶有工期指派和資源約束的單機(jī)排序問題。文獻(xiàn)[19-22]給出了其他相關(guān)研究工作。

本文研究帶有指數(shù)學(xué)習(xí)效應(yīng)和惡化效應(yīng)的可拒絕排序問題。將指數(shù)學(xué)習(xí)效應(yīng)和惡化效應(yīng)與多窗口相結(jié)合,分別研究了2個(gè)總費(fèi)用函數(shù)。第1個(gè)函數(shù)是與窗口的開始時(shí)間、窗口的大小、提前、延誤、最大完工時(shí)間以及拒絕費(fèi)用有關(guān)的函數(shù);第2個(gè)函數(shù)是與提前、延誤的工件數(shù)、窗口的開始時(shí)間、窗口的大小、最大完工時(shí)間以及拒絕費(fèi)用有關(guān)的函數(shù)。證明了該問題在多項(xiàng)式時(shí)間可解,并針對(duì)2個(gè)問題給出多項(xiàng)式時(shí)間算法。

1 問題描述

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

(1)

其中:α為學(xué)習(xí)指數(shù);bj≥0 為工件的惡化率。

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

因此這2類問題的目標(biāo)函數(shù)分別為

(2)

(3)

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

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

問題1:

(4)

問題2:

(5)

2 主要結(jié)果

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

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

性質(zhì)3 在最優(yōu)排序π=(J1,J2,…,Jn)中,存在某個(gè)k和 l,使得

證明 假設(shè)存在1個(gè)最優(yōu)排序S,不具備如上性質(zhì)。因此設(shè)

與Δ1、Δ2有關(guān)的目標(biāo)函數(shù)可以化為如下形式:

根據(jù)以上性質(zhì)1～性質(zhì)4,對(duì)于任意給定的排序π=(J[1],J[2],…,J[n])。當(dāng)Δ1、Δ2趨近于0時(shí),可得

因此,可將目標(biāo)函數(shù)化簡如下:

其中,

(11)

(12)

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

即

根據(jù)以上計(jì)算過程,給出解法如下:

算法:

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

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

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

2) 對(duì)于工件中被接受工件個(gè)數(shù)為h的情況

因?yàn)閔=0是平凡問題,所以設(shè)1≤h

針對(duì)問題1,當(dāng)1≤h

針對(duì)接受工件數(shù)h

(a)Jj被拒絕

那么在前j-1個(gè)工件中,恰好有m個(gè)工件被接受,因此,目標(biāo)函數(shù)值為

(b)Jj被接受

那么在前j-1個(gè)工件中,恰好有m-1個(gè)工件被接受,因此,目標(biāo)函數(shù)值為

由此可得遞推公式如下:

因?yàn)楸唤邮艿墓ぜ?shù)為h,故已考慮的被接受的m個(gè)工件同剩下的未考慮的(n-j)個(gè)工件之和應(yīng)不少于h,即m≥h-(n-j)。故max(0,h-(n-j))≤m≤min(j,h)。

在以上2種分類的基礎(chǔ)上,給出動(dòng)態(tài)規(guī)劃算法DP如下:

邊界條件:

遞推式:

對(duì)于已經(jīng)給定的h,目標(biāo)函數(shù)值可以表示如下:

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

其中:j≤n;m≤h≤n。故上述動(dòng)態(tài)規(guī)劃算法DP中,j≤n,m≤h≤n,所以動(dòng)態(tài)規(guī)劃算法DP在O(n2)時(shí)間內(nèi)可解。對(duì)于h=1,2,…,n,分別運(yùn)行算法1,比較所得結(jié)果,從中選取最小值,即為問題的最優(yōu)解。

定理1 問題

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

3 問題2的討論

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

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

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

性質(zhì)6 給定1個(gè)排序π=(J1,J2,…,Jn),針對(duì)問題(2)其目標(biāo)函數(shù)可以表示為

令

若h

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

綜上所述,對(duì)于給定的h,計(jì)算所有可能的目標(biāo)函數(shù)值,該指派問題在O(n3)時(shí)間內(nèi)可解。

定理2 問題

存在算法復(fù)雜度為O(n5)的最優(yōu)算法。

4 結(jié) 論

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

[ 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]金亭,趙傳立. 帶有學(xué)習(xí)效應(yīng)和退化效應(yīng)的可拒絕單機(jī)排序問題[J].沈陽師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 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。

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

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

1673-5862(2017)01-0047-08

O223

A

10.3969/ j.issn.1673-5862.2017.01.009

運(yùn)籌學(xué)與控制論