加工時(shí)間可控的單機(jī)排序問題

高 潔, 趙玉芳

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

加工時(shí)間可控的單機(jī)排序問題

高 潔, 趙玉芳

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

研究帶有學(xué)習(xí)效應(yīng)和惡化效應(yīng)的單機(jī)排序問題。在此模型中,工件的學(xué)習(xí)效應(yīng)是與工件加工位置相關(guān)的減函數(shù),工件的惡化效應(yīng)是與其開始加工時(shí)間相關(guān)的線性函數(shù)。在無(wú)資源約束的情況下,分別討論了目標(biāo)函數(shù)為最大完工時(shí)間、總完工時(shí)間及總完工時(shí)間的絕對(duì)差之和的排序問題,證明了這些問題都是多項(xiàng)式時(shí)間可解的。對(duì)于帶有資源約束問題,若分配一定的資源,工件加工時(shí)間會(huì)減少。討論了在線性資源分配情況下,帶有學(xué)習(xí)效應(yīng)、惡化效應(yīng)和資源分配量的交貨期排序問題,其中所有工件有一個(gè)共同的交貨期。目的是確定最優(yōu)交貨期、資源分配及工件的加工順序,使交貨期、提前、延誤和資源分配量之和最小,通過將其轉(zhuǎn)化為指派問題,證明問題是多項(xiàng)式時(shí)間可解的。

排序; 學(xué)習(xí)效應(yīng); 惡化效應(yīng); 資源分配; 指派問題

0 引 言

近年來(lái),帶有學(xué)習(xí)效應(yīng)和惡化效應(yīng)的排序問題受到了廣泛的關(guān)注。Lee[1]首先研究了單機(jī)帶有學(xué)習(xí)和惡化效應(yīng)的排序問題,分別提出實(shí)際加工時(shí)間為pir=αitra和pir=(p0+αit)ra的排序問題,其中αi0,表示工件的惡化效應(yīng);t表示工件的開始加工時(shí)間;a≤0表示工件的學(xué)習(xí)效應(yīng);r表示工件的實(shí)際加工位置;p0表示工件的基本加工時(shí)間,證明了最大完工時(shí)間和總完工時(shí)間是多項(xiàng)式時(shí)間可解的。Wang[2]研究了實(shí)際加工時(shí)間是與工件位置和開始加工時(shí)間有關(guān)的帶有學(xué)習(xí)效應(yīng)和惡化效應(yīng)的模型pjr=pj(α(t)+βra),其中pj表示工件的基本加工時(shí)間,給出了最大完工時(shí)間和總完工時(shí)間的多項(xiàng)式時(shí)間最優(yōu)算法。Wang等[3]研究了實(shí)際加工時(shí)間為pir=αi(b+ct)ra的單機(jī)排序問題,給出了最大完工時(shí)間,總完工時(shí)間和加權(quán)總完工時(shí)間的多項(xiàng)式時(shí)間的最優(yōu)算法。Zhang[4]對(duì)加工時(shí)間是與工件加工位置相關(guān)的指數(shù)函數(shù),給出了總完工時(shí)間的多項(xiàng)式時(shí)間算法。Yang等[5]研究了單機(jī)和流水作業(yè)加工時(shí)間為pir=pirb+αt的排序問題,其中b≤0,給出了最大完工時(shí)間和總完工時(shí)間的多項(xiàng)式時(shí)間最優(yōu)算法。Gordon等[6]對(duì)加工時(shí)間與開始時(shí)間及位置相關(guān)的單機(jī)排序問題進(jìn)行了綜述。Yang[7]研究了在帶有惡化維修情況下加工時(shí)間為pir=(pi+λt)ra的單機(jī)排序問題,證明了最大完工時(shí)間和總完工時(shí)間是多項(xiàng)式時(shí)間可解的。文獻(xiàn)[8-10]研究了帶有惡化的單機(jī)排序問題。交貨期排序問題也是排序問題中非常重要的問題。

交貨期排序問題也是排序問題中非常重要的問題,工件在其交貨期前完工需被儲(chǔ)存,將花費(fèi)一定的儲(chǔ)存費(fèi)用;在其交貨期后完工將引發(fā)懲罰。Panwalkar等[11]對(duì)共同交貨期提前與延誤懲罰函數(shù)進(jìn)行研究,得到了共同交貨期懲罰函數(shù)的重要結(jié)論,即工件的共同交貨期為某個(gè)工件的完工時(shí)間,且按時(shí)完工的工件個(gè)數(shù)只與懲罰系數(shù)和工件的總數(shù)有關(guān),而與工件本身無(wú)關(guān)。對(duì)于具有可控加工時(shí)間的交貨期指派問題也已被廣泛研究。Ventur等[12]研究了工件的釋放時(shí)間是依賴資源的單機(jī)共同交貨期指派問題,并給出了其擬多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃算法。Ng等[9]研究了工件的加工時(shí)間是資源分配量的線性非增函數(shù),并給出共同交貨期與資源分配之和的多項(xiàng)式時(shí)間算法。Yin等[13]研究了加工時(shí)間依賴資源的單機(jī)交貨期窗口問題,給出了資源分配及工件的加工順序,使交貨期、提前、延誤和資源分配之和的多項(xiàng)式時(shí)間算法。Yin等[14]研究了帶有可控加工時(shí)間和學(xué)習(xí)效應(yīng)的單機(jī)排序問題,目標(biāo)函數(shù)是最小化時(shí)間表長(zhǎng)、總的完工時(shí)間、總的完工時(shí)間的絕對(duì)差和總的壓縮費(fèi)用。通過將問題轉(zhuǎn)化為指派問題,證明了這個(gè)問題是多項(xiàng)式時(shí)間可解的。郭玲和趙傳立[15]研究了退化維修情況下,帶有三種交貨期指派和加工時(shí)間可控的單機(jī)排序問題,證明了當(dāng)維修固定時(shí),問題可轉(zhuǎn)化為指派問題,得到O(n3)的多項(xiàng)式時(shí)間最優(yōu)算法。

本文研究同時(shí)帶有與工件位置相關(guān)的學(xué)習(xí)效應(yīng)和與工件開始時(shí)間相關(guān)的惡化效應(yīng)的單機(jī)排序問題。工件的加工實(shí)際時(shí)間是與工件基本加工時(shí)間,工件的加工位置及工件的開始加工時(shí)間相關(guān)的函數(shù)。本文首先對(duì)于無(wú)資源約束的問題,討論了工件的學(xué)習(xí)效應(yīng)是以工件加工位置為指數(shù)的減函數(shù),工件的惡化效應(yīng)是其開始加工時(shí)間的線性函數(shù),目標(biāo)函數(shù)分別為最大完工時(shí)間、總完工時(shí)間及總完工時(shí)間的絕對(duì)差之和的單機(jī)排序問題。隨后,對(duì)于帶有資源約束問題,討論了在線性資源分配情況下,帶有學(xué)習(xí)效應(yīng)、惡化效應(yīng)和資源分配的交貨期排序問題,目的是確定最優(yōu)交貨期、資源分配及工件的加工順序,使交貨期、提前、延誤和資源分配之和最小。

1 問題描述

給定n個(gè)獨(dú)立的工件,記為J={J1,J2,…,Jn}。工件的實(shí)際加工時(shí)間可表示為pjr=pjar-1+bt,其中pj表示工件Jj的基本加工時(shí)間;b表示工件的惡化系數(shù),且b0;t表示工件的開始加工時(shí)間;ar-1表示與位置相關(guān)學(xué)習(xí)效應(yīng)模型,其中:0

不失一般性,對(duì)于任意一個(gè)給定的排序π,本文涉及的符號(hào)表示如下:

本文研究帶有學(xué)習(xí)效應(yīng)和惡化效應(yīng)的單機(jī)排序問題。對(duì)于無(wú)資源約束的問題,討論了工件的學(xué)習(xí)效應(yīng)是以工件加工位置為指數(shù)的減函數(shù),工件的惡化效應(yīng)是其開始加工時(shí)間的線性函數(shù),目標(biāo)函數(shù)分別為最大完工時(shí)間、總完工時(shí)間及總完工時(shí)間的絕對(duì)差之和的單機(jī)排序問題。對(duì)于帶有資源約束問題,討論了在線性資源分配情況下,帶有學(xué)習(xí)效應(yīng)、惡化效應(yīng)和資源分配的交貨期排序問題,目的是確定最優(yōu)交貨期、資源分配及工件的加工順序,使交貨期、提前、延誤和資源分配之和最小。

運(yùn)用三參數(shù)表示法,問題分別表示為

2 相關(guān)結(jié)論

2.1最大完工時(shí)間

為了解決最大完工時(shí)間問題,首先必須知道工件的實(shí)際加工時(shí)間。不失一般性,令p[r]表示第r個(gè)位置上工件的基本加工時(shí)間,p[1]1表示第一個(gè)位置工件的實(shí)際加工時(shí)間表示,即p[1]1=p[1]ar-1+b×0=p[1];第一個(gè)工件的完工時(shí)間為C[1],C[1]=p[1]。類似地,有

第i個(gè)工件Ji的加工時(shí)間及完工時(shí)間可轉(zhuǎn)化為:

引理1 在最優(yōu)排序的加工過程中,任意2個(gè)工件之間沒有空閑,且第1個(gè)工件的開始加工時(shí)間為零。

證明 由式(1)工件的總完工時(shí)間為C[n],

2.2總完工時(shí)間和TADC

證明

證明 TADC表示工件完工時(shí)間的絕對(duì)差之和,

2.3與資源相關(guān)的交貨期排序問題

本節(jié)討論線性資源分配情況下,帶有學(xué)習(xí)效應(yīng)、惡化效應(yīng)和資源分配的交貨期排序問題,目的是確定最優(yōu)共同交貨期,資源分配及工件的加工順序,使共同交貨期、提前、延誤和資源分配量之和最小。

引理2[8]在共同交貨期指派問題的一個(gè)最優(yōu)排序π中,工件的最優(yōu)交貨期為第l*個(gè)工件的完工時(shí)間或0,即d*=C[l*]或d*=0(此時(shí)l*=0),其中

由式(2)可知,l*只與提前,延誤懲罰的系數(shù)有關(guān),與工件的加工時(shí)間和加工順序無(wú)關(guān)。那么對(duì)于任意資源分配u及工件的排序π,有

由式(3)～式(6)可知帶有資源分配的共同交貨期指派的目標(biāo)函數(shù)可轉(zhuǎn)化為:

由上式工件的實(shí)際加工時(shí)間可知,問題的目標(biāo)函數(shù)可轉(zhuǎn)化為

證明 由式(7)可知,問題可轉(zhuǎn)化為指派問題

其中

3 實(shí) 例

解p[1]1表示第1個(gè)位置工件的實(shí)際加工時(shí)間表示,即p[1]1=p[1]ar-1+b×0=p[1];第1個(gè)工件的完工時(shí)間為C[1],C[1]=p[1]。

4 結(jié) 語(yǔ)

在實(shí)際生產(chǎn)過程,工件很可能帶有學(xué)習(xí)效應(yīng)和惡化效應(yīng),因此在理論研究中帶有重要意義。本文研究了同時(shí)帶有學(xué)習(xí)效應(yīng)和惡化效應(yīng)的單機(jī)排序問題,給出了求解工件的最大完工時(shí)間和工件的總完工時(shí)間時(shí)間復(fù)雜性為O(nlogn)的多項(xiàng)式時(shí)間算法。并將工件的加工時(shí)間與線性資源分配結(jié)合在一起,目的是確定最優(yōu)交貨期,資源分配及工件的加工順序,使交貨期、提前、延誤和資源分配之和最小,并將問題轉(zhuǎn)化為指派問題,給出了帶有資源的交貨期指派問題時(shí)間復(fù)雜性為O(n3)的多項(xiàng)式時(shí)間算法。

[ 1 ]LEE W C. A note on deteriorating jobs and learning in single-machine scheduling problems[J]. Int J Business Econ, 2004,3(1):83-89.

[ 2 ]WANG Jibo. Single-machine scheduling problems with the effects of learning and deterioration[J]. Omega, 2007,35(4):397-402.

[ 3 ]WANG Jibo, CHENG T C E. Scheduling problems with the effects of deterioration and learning[J]. Asia-Pac J Oper Res, 2007,24(2):245-261.

[ 4 ]ZHANG Xingong, YAN Guangle, HUANG Wanzhen, et al. Single-machine scheduling problems with time and position dependent processing times[J]. Ann Oper Res,2011,186(1):345-356.

[ 5 ]YANG D L, KUO W C. Some scheduling problems with deteriorating jobs and learning effects[J]. Comput Ind Eng, 2010,58(1):25-28.

[ 6 ]GORDON V S, Potts C N, STRUSEVICH V A, et al. Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation[J]. J Schedul, 2008,11(5):357-370.

[ 7 ]YANG S J. Single-machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activities consideration[J]. Comput Ind Eng, 2012,62(1):271-275.

[ 8 ]王吉波,劉璐,許揚(yáng)韜,等. 具有惡化工件的不同交貨期指派問題研究[J].沈陽(yáng)航空航天大學(xué)學(xué)報(bào),2013,30(5):83-87.

[ 9 ]王吉波,劉璐. 帶準(zhǔn)備時(shí)間的任務(wù)單機(jī)學(xué)習(xí)效應(yīng)排序問題[J]. 大連理工大學(xué)學(xué)報(bào), 2013,53(6):930-936.

[10]王吉波,王建軍,何平. 具有共同松弛時(shí)間的惡化型工件排序問題研究[J]. 大連理工大學(xué)學(xué)報(bào), 2012,52(6):932-936.

[11]PANWALKAR S S, SMITH M L, SEIDMANN A. Common due date assignment to minimize total penalty for the one machine scheduling problem[J]. Oper Res, 1982,30(2):391-399.

[12]VENTURA J A, KIM D, GARRIGA F.Single machine earliness-tardiness scheduling with resourcedependent release dates[J]. Eur J Oper Res, 2002,142(1):52-69.

[13]YIN Yongqiang, 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]. J Oper Res Soc, 2013,65(1):1-13.

[14]YIN Na, WANG Xiaoyuan. Single-machine scheduling with controllable processing times and learning effect[J]. Int J Adv Manu Tech, 2011,54(5/6/7/8):743-748.

[15]郭玲,趙傳立. 在退化維修下帶有交貨期指派和加工時(shí)間可控的單機(jī)排序問題[J]. 沈陽(yáng)師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 2013,31(3):341-347.

Singlemachineschedulingproblemwithcontrollableprocessingtimes

GAOJie,ZHAOYufang

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

This paper considers some single-machine scheduling problems of jobs with learning and deteriorating effects. In the model, the actual processing time of a job is a decreasing function of its position due to learning effects. The actual processing time of a job is a linear function of its starting time due to deteriorating effects. For the problems without resource allocation, we consider the problems of the makespan, the total completion times and total absolute differences in completion times, respectively. We show that these problems are polynomially solvable under the proposed model. Processing times may be reduced by allocating resources. For the controllable processing times problem with linear resource allocation, we consider a common due-date assignment problem with learning and deteriorating effect and resource allocation on a single machine, in which all jobs have a common due-date. The objective is to determine the optimal common due-date, the optimal sequence and the optimal resource allocation to minimize a total costs based on earliness, tardiness, common due-date, and resource consumption. We show that the problem is polynomially solvable by transforming this problem into an assignment problem.

scheduling; learning effects; deterioration effects; resource allocation; assignment problem

2014-05-01。

遼寧省教育廳科學(xué)技術(shù)研究項(xiàng)目(L2014433)。

高 潔(1989-),女,遼寧葫蘆島人,沈陽(yáng)師范大學(xué)碩士研究生;

:趙玉芳(1966-),女,遼寧遼陽(yáng)人,沈陽(yáng)師范大學(xué)副教授,博士,碩士研究生導(dǎo)師。

1673-5862(2014)04-0476-06

O223

: A

10.3969/ j.issn.1673-5862.2014.04.005