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

高 潔, 趙玉芳

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

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

高 潔, 趙玉芳

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

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

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

0 引 言

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

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

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

1 問題描述

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

不失一般性,對于任意一個給定的排序π,本文涉及的符號表示如下:

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

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

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

2.1最大完工時間

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

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

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

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

2.2總完工時間和TADC

證明

證明 TADC表示工件完工時間的絕對差之和,

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

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

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

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

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

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

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

其中

3 實 例

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

4 結(jié) 語

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

[ 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].沈陽航空航天大學(xué)學(xué)報,2013,30(5):83-87.

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

[10]王吉波,王建軍,何平. 具有共同松弛時間的惡化型工件排序問題研究[J]. 大連理工大學(xué)學(xué)報, 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]郭玲,趙傳立. 在退化維修下帶有交貨期指派和加工時間可控的單機(jī)排序問題[J]. 沈陽師范大學(xué)學(xué)報: 自然科學(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ù)研究項目(L2014433)。

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

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

1673-5862(2014)04-0476-06

O223

: A

10.3969/ j.issn.1673-5862.2014.04.005