徐海燕

(金陵科技學院公共基礎(chǔ)課部, 中國 南京 211169)

組合優(yōu)化中有一類非常重要的問題就是排序,它廣泛存在于生產(chǎn)調(diào)度、管理科學與工程、計算機科學與工程等眾多領(lǐng)域中.經(jīng)典的排序問題中工件的加工時間是一個固定不變的常數(shù).但是,在某些實際生活中,工件的實際加工時間由于人的參與或者其他的原因會隨著開始加工時間以及加工位置等不同而變化,這就是常常遇到的學習或惡化效應[1].

近年來,很多學者致力于調(diào)度問題中的學習效應和惡化效應的研究.Biskup[2]把學習效應模型分為基于時間和基于位置兩種.基于位置的學習主要是由于處理某工件前的數(shù)量,而基于時間的學習主要是由于處理某工件前的工作時間.Biskup[3]首次把基于位置的學習效應引入到排序問題中,提出的學習函數(shù)為pir=pira,a<0,其中pir,pi分別表示被安排在r位置的工件i的實際加工時間和基本加工時間,并證明了在此模型下最小化總完工時間和具有一個公共的截止時間的總延誤時間是多項式時間內(nèi)可解的.類似地,Mosheiov[4-5]討論了另外的一些單機調(diào)度問題和以目標函數(shù)為最小化總完工時間的并行機調(diào)度問題,Lee等[6]研究了同時考慮最小化總完工時間和總延遲時間的雙目標問題在單機環(huán)境下的調(diào)度,Lee[7]提出了一個具有S型的學習函數(shù)的學習效應模型并在此模型下研究了一些調(diào)度問題.Kuo[8]首次提出了基于時間的學習效應模型.Koulamas和Kyparisis[9]介紹一個同時考慮基于位置和時間的學習效應模型.Cheng[10]等建立了一種基于工件被安排加工的位置和對數(shù)加工時間之和的學習效應模型,研究了在此模型下一些單機和多機的調(diào)度問題.Jiang[11]等研究了一種具有依賴工件開工時間的學習效應的單機調(diào)度問題.證明了在此模型下最小化總完工時間和最小化總加權(quán)完工時間和問題是NP-難的,并提出3類問題是多項式時間內(nèi)可解的.Shen[12]等探討了一種同時依賴時間和工件加工位置的學習效應的一般模型的單機調(diào)度問題.

除了上面考慮的學習效應,惡化效應廣泛地存在于實際的調(diào)度中.Biskup[3]提出的學習函數(shù)為pir=pira,當a≥0時學習效應變?yōu)閻夯猍13].但是,文獻中很少有學者同時考慮學習效應和惡化效應.Toksari和Guner[14]構(gòu)造一個非線性混合整數(shù)規(guī)劃模型來解決目標函數(shù)為最小化延誤時間的并行機具有學習和惡化效應的調(diào)度問題. 在文獻[15]中，作者提出了一種啟發(fā)式方法來解決具有不同的釋放時間的單機調(diào)度問題.在文獻[16]中，作者提出了一些算法來解決具有基于時間的學習或惡化效應的單機調(diào)度問題.除了研究具有具體的學習函數(shù)的學習效應和惡化效應的模型之外,也有一些學者致力于研究通用函數(shù)的模型在單機調(diào)度中問題的求解[17].

基于位置的學習效應模型通常使用冪函數(shù)作為學習函數(shù).但是Hurley[18]指出如果使用冪函數(shù)作為學習函數(shù),當要被處理的工件的數(shù)量很大,按照冪函數(shù)的性質(zhì),處理工件的數(shù)量到一定時它的實際加工時間就接近于0了,這是不符合實際的.另外Lapre等人[19]研究得到學習函數(shù)該具有2種特性,其一,開始時為凹下降,其二到達一定時候不再變化或者變化很小.考慮到[18-19]所述內(nèi)容,在Lee提出的具有學習效應的通用模型基礎(chǔ)上[20],本文提出了一個同時具有學習和惡化效應的的通用模型,目標函數(shù)為極小化最大完工時間和最小化總完工時間,極小化延誤時間，最小化總延誤時間等問題,該模型具有更廣的適用范圍和實際意義.

1 問題描述

為了更好地表述，接下來給出一些符號說明:

對于一個調(diào)度序列π=(J1,J2,…,Jn),記:Cj=Cj(π)表示調(diào)度序列π中工件Jj的結(jié)束時間;Cmax=Cmax(π)=max{Cj(π)|j=1,2,…,n}表示序列π中的工件最大完工時間;∑Cj=∑Cj(π)表示序列π中工件完工時間之和;∑wjCj=∑wjCj(π)表示序列π中工件加權(quán)總完工時間和;Lmax=Lmax(π)=max{Cj(π)-dj|j=1,2,…,n}表示序列π中工件最大延遲時間;Tmax=Tmax(π)=max{0,Lj(π)|j=1,2,…,n}表示序列π中工件最大延誤時間;∑Tj=∑Tj(π)表示序列π中工件延誤時間和.

2 問題的求解

圖1 交換相鄰兩個工件前后的調(diào)度序列對比Fig.1 A pairwise interchange of adjacent jobs

給出兩個序列π=(S1,i,j,S2),π′=(S1,j,i,S2),其中Ji在序列π中位于第r個位置,Jj在序列π中位于第r+1個位置,同時Jj在序列π′中位于第r個位置,Ji在序列π′中位于第r+1個位置,S1中含有r-1個工件,S2中含有n-r-1個工件,如圖1所示:

假設(shè)S1中所有工件完成操作的時間為t0,由此可以得到,序列π中Ji和Jj的完工時間為

相應地,序列π′中Ji和Jj的完工時間為

在這里,假設(shè)pi≤pj,為了方便描述,使用現(xiàn)在通用的Graham等[21]提出的三域表示法來描述調(diào)度問題.

證利用多元函數(shù)的偏導數(shù)的性質(zhì)和中值定理顯然可得.

證先證明序列π=(S1,i,j,S2)優(yōu)于π′=(S1,j,i,S2).分3部分證明.

1) 證明?l∈S1,Cl(π)=Cl(π′).

由于S1中所有的工件都是一樣的,所以?l∈S1,Cl(π)=Cl(π′).

2) 證明Cj(π)≤Ci(π′).

3) 證明?l∈S2,Cl(π)≤Cl(π′).

假設(shè)l是S2中第1個工件,

由Cmax=max{Cj|j=1,2,…,n}得到序列π=(S1,i,j,S2)優(yōu)于π′=(S1,j,i,S2),只要將工件按pi非減的順序(SPT)排列得到的最優(yōu)排序.

證由定理2可以得到結(jié)論.

證

∑wjCj(π′)-∑wjCj(π)=w1C1(π′)+…+wjCj(π′)+wiCi(π′)+…+wnCn(π′)-

證因為Li(π)=Ci(π)-di,Lj(π)=Cj(π)-dj,Li(π′)=Ci(π′)-di,Lj(π′)=Cj(π′)-dj,

由pi≤pj,di≤dj以及Ci(π)≤Cj(π)≤Ci(π′)可知

Li(π)=Ci(π)-di≤Cj(π)-di≤Ci(π′)-di=Li(π′),Lj(π)=Cj(π)-dj≤Cj(π)-di≤

Ci(π′)-di=Li(π′)，

max{Li(π),Lj(π)}≤Li(π′).

由于?l∈S1,Cl(π)=Cl(π′),?l∈S2,Cl(π)≤Cl(π′),可知

Lmax(π′)=max{L1(π′),…,Li(π′),Lj(π′),…,Ln(π′)}=

max{L1(π′),…,max{Li(π′),Lj(π′)},…,Ln(π′)}≥

max{L1(π),…,max{Li(π),Lj(π)},…,Ln(π)}=Lmax(π).

即序列π=(S1,i,j,S2)優(yōu)于π′=(S1,j,i,S2),

因而只要將工件按非減順序(EDD)排列即得到最優(yōu)排序.

證

當Ci(π)-di≤0,Cj(π)-dj≤0時或者Ci(π)-di≥0,Cj(π)-dj≤0時或者當Ci(π)-di≤0,Cj(π)-dj≥0時，顯然有：Ti(π′)+Tj(π′)-Ti(π)-Tj(π)≥0,當Ci(π)-di≥0,Cj(π)-dj≥0時，分兩種情況討論.

綜上所述,序列π=(S1,i,j,S2)優(yōu)于π′=(S1,j,i,S2),

故而只要將工件按di非減同時pi非減的順序(EDD)排列即得到最優(yōu)排序.

注定理2～6只是一個充分條件.

由于p2(=4)≤p3(=5)≤p1(=6),d2(=5)≤d3(=4)≤d1(=7),目標函數(shù)為Lmax,∑Ti的最優(yōu)序列為[J2,J3,J1].

3 結(jié)論

近幾十年來,很多學者研究具有學習函數(shù)或者惡化函數(shù)的模型,考慮到模型越是接近于實際,越是適用范圍廣,本文給出了一個具有一般性的函數(shù)模型,凡是滿足此模型中的條件,都可以用該模型表示.作者在本文中將學習效應和惡化效應有效地結(jié)合在一起,研究了極小化最大完工時間、總完工時間和加權(quán)總完工時間、最大延誤時間和總延誤時間和在單機中的調(diào)度問題,證明了在某種情況下一些單機調(diào)度問題可以多項式可解.

參考文獻：

[1] PINEDO M. Scheduling: theory, algorithms, and systems[M]. New York:Springer Science Business Media, 2012.

[2] BISKUP D. A state-of-the-art review on scheduling with learning effects[J]. Eur J Oper Res, 2008,188(2):315-329.

[3] BISKUP D. Single-machine scheduling with learning considerations[J].Eur J Oper Res, 1999，115(1):173-178.

[4] MOSHEIOV G. Scheduling problems with a learning effect[J]. Eur J Oper Res, 2001,132(3):687-693.

[5] MOSHEIOV G. Parallel machine scheduling with a learning effect[J]. J Oper Res Soc, 2001,52(10):1165-1169.

[6] LEE W C, WU C C, SUNG H J. A bi-criterion single-machine scheduling problem with learning considerations[J]. Acta Inform, 2004, 40(4):303-315.

[7] LEE W C. Scheduling with general position-based learning curves[J]. Inf Sci, 2011,181(24):5515-5522.

[8] KUO W H, YANG D L. Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect[J]. Eur J Oper Res, 2006,174(2):1184-1190.

[9] KOULAMAS C, KYPARISIS G J. Single-machine and two-machine flowshop scheduling with general learning functions[J]. Eur J Oper Res, 2007,178(2):402-407.

[10] CHENG T C E, KUO W H, YANG D L. Scheduling with a position-weighted learning effect based on sum-of-logarithm-processing-times and job position[J]. Inf Sci, 2012,221:490-500.

[11] JIANG Y Z, CHEN F F, KANG H Y. Single-machine scheduling problems with actual time-dependent and job-dependent learning effect[J]. Eur J Oper Res, 2013,227(1):76-80.

[12] SHEN L X, WU Y B. Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects[J]. Appl Math Model, 2013,37:5444-5451.

[13] GORDON V S, POTTS C N, STRUSEVICH VA,etal. Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation[J].J Sched, 2008,11(5):357-370.

[14] TOKSARI M D, GUNER E. Minimizing the earliness/tardiness costs on parallel machine with learning effects and deteriorating jobs: a mixed nonlinear integer programming approach[J]. Int J Adv Manuf Tech, 2008,38(7-8):801-808.

[15] TOKSARI M D. A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs[J]. Comput Oper Res, 2011,38(9):1361-1365.

[16] QIAN J B, STEINER G. Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine[J]. Eur J Oper Res, 2012,225(3):547-551.

[17] WANG J B, HSU C J, YANG D L. Single-machine scheduling with effects of exponential learning and general deterioration[J]. Appl Math Model, 2013,37(4):2293-2299.

[18] HURLEY W J. When are we going to change the learning curve lecture? [J]. Comput Oper Res, 1996,23(5):509-511.

[19] LAPRE M A, MUKHERJEE A S, WASSENHOVE L N V. Behind the learning curve: Linking learning activities to waste reduction[J]. Man Sci, 2000,46(5):597-611.

[20] HUANG X, WANG J B, WANG L Y,etal. Single machine scheduling with time-dependent deterioration and exponential learning effect[J]. Comput Ind Eng, 2010,58(1):58-63.

[21] GRAHAM R L, LAWLER E L, LENSTRA J K,etal, Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Ann Discrete Math, 1979,5(2):287-326.