胡晨晨, 趙玉芳

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

?

同時(shí)帶有安裝時(shí)間和送出時(shí)間的單機(jī)排序問(wèn)題

胡晨晨, 趙玉芳

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

在實(shí)際生產(chǎn),如鋼鐵和冶金工業(yè)生產(chǎn)過(guò)程中,工件在加工之前需要預(yù)熱或安裝必要的夾具和固定裝置,在加工之后工件需要進(jìn)行冷卻處理等,也就是工件在進(jìn)行加工時(shí)常常帶有安裝時(shí)間和送出時(shí)間。討論帶有學(xué)習(xí)效應(yīng)、安裝時(shí)間和送出時(shí)間的單機(jī)排序問(wèn)題。在這一模型中,工件的實(shí)際加工時(shí)間是與工件的基本加工時(shí)間和工件的實(shí)際加工位置相關(guān)的一般函數(shù)。工件的安裝時(shí)間和送出時(shí)間均依賴于已加工完的工件的實(shí)際加工時(shí)間,即p-s-d形式。目標(biāo)函數(shù)分別為最大完工時(shí)間、總完工時(shí)間、加權(quán)總完工時(shí)間、總延誤時(shí)間、最大延誤時(shí)間和最大延遲時(shí)間,提出了上述問(wèn)題的最優(yōu)排序規(guī)則。

排序; 單機(jī); 學(xué)習(xí)效應(yīng); 安裝時(shí)間; 送出時(shí)間

0 引 言

在工業(yè)生產(chǎn)中,工件到達(dá)后不一定可以馬上進(jìn)行加工,常常在加工前需要進(jìn)行一些準(zhǔn)備工作,如安裝夾具或固定裝置等。處理這些準(zhǔn)備工作需要消耗一定的安裝時(shí)間,因此考慮加工工件具有一定的安裝時(shí)間是十分必要的,它對(duì)工件的最大完工時(shí)間、總完工時(shí)間等問(wèn)題產(chǎn)生影響。Koulamas等[9]首次提出了一種安裝時(shí)間(p-s-d),它依賴于所有已加工完的工件。Kuo等[10]研究了帶有學(xué)習(xí)效應(yīng)和安裝時(shí)間的單機(jī)排序問(wèn)題,目標(biāo)函數(shù)分別為最大完工時(shí)間和總完工時(shí)間,并對(duì)上述問(wèn)題提出了多項(xiàng)式時(shí)間算法。Wang[11]研究了帶有安裝時(shí)間,且學(xué)習(xí)效應(yīng)與時(shí)間相關(guān)的單機(jī)排序問(wèn)題。目標(biāo)函數(shù)分別為最大完工時(shí)間,總完工時(shí)間,加權(quán)總完工時(shí)間,最大延遲時(shí)間。證明了上述問(wèn)題都是多項(xiàng)式時(shí)間可解的。Lee[12]研究了同時(shí)帶有安裝時(shí)間,學(xué)習(xí)效應(yīng)和退化效應(yīng)的單機(jī)排序問(wèn)題,其中工件的實(shí)際加工時(shí)間是與工件的基本加工時(shí)間和工件的實(shí)際加工位置相關(guān)的一般函數(shù)。目標(biāo)函數(shù)分別為最大完工時(shí)間,總完工時(shí)間,加權(quán)總完工時(shí)間,總延誤時(shí)間,最大延誤時(shí)間和最大延遲時(shí)間。提出了上述問(wèn)題的最優(yōu)排序規(guī)則,證明了它們都是多項(xiàng)式時(shí)間可解的。Hsu等[13]研究了帶有學(xué)習(xí)效應(yīng)和安裝時(shí)間的不同類型機(jī)排序問(wèn)題。目標(biāo)函數(shù)是總完工時(shí)間問(wèn)題。證明了上述問(wèn)題可以轉(zhuǎn)化成指派問(wèn)題,是多項(xiàng)式可解的,算法復(fù)雜性為o(n(m+2))。

同時(shí),在鋼鐵工業(yè)加工過(guò)程中,鋼鐵由于在加工完成后溫度極高,不會(huì)馬上送出,這就需要一定時(shí)間來(lái)進(jìn)行冷卻,因此工件的等待時(shí)間會(huì)對(duì)工件的總完工時(shí)間產(chǎn)生不利的影響,Koulamas等[14]提出了這樣的不利影響被認(rèn)為是與過(guò)去排序相關(guān)的(p-s-d)送出時(shí)間。為了分析方便,通常假設(shè)送出時(shí)間與工件的等待時(shí)間是成比例的。Rustogi等[15]對(duì)加工時(shí)間為一般函數(shù)的排序問(wèn)題作了綜述。Zhao等[16]研究了帶有送出時(shí)間的單機(jī)排序問(wèn)題。其中,送出時(shí)間是與過(guò)去排序相關(guān)的,加工時(shí)間是與位置相關(guān)的一般函數(shù),即pj,r=g(r)pj,目標(biāo)函數(shù)分別為最大完工時(shí)間和總完工時(shí)間。證明了上述問(wèn)題是多項(xiàng)式時(shí)間可解的。

1 問(wèn)題描述

假設(shè)有n個(gè)獨(dú)立的工件在一臺(tái)機(jī)器上需要被加工,記為J={J1,J2,…,Jn}。對(duì)于每個(gè)工件Jj,pj表示Jj的基本加工時(shí)間;wj表示Jj的權(quán);dj表示Jj的工期;Cj表示Jj的完工時(shí)間;Tj=max{0,Cj-dj}為Jj的延誤時(shí)間。工件的實(shí)際加工時(shí)間可表示成:

pj[r]=pjg(r),r=1,2,…,n

其中,g(r)表示與位置r相關(guān)的非負(fù)遞減函數(shù)。

在[9]中,工件Jj在排序中排在第r個(gè)位置的安裝時(shí)間表示為:

這里b≥0是常數(shù),p[k]表示排在第k個(gè)位置的實(shí)際加工時(shí)間。

在[14]中,工件Jj在排序中排在第r個(gè)位置的送出時(shí)間表示為:

這里γ≥0是常數(shù),p[k]表示排在第k個(gè)位置的實(shí)際加工時(shí)間。Cmax,∑Cj,∑wjCj和∑Tj分別表示最大完工時(shí)間,總完工時(shí)間,加權(quán)總完工時(shí)間和總延誤時(shí)間;Tmax和Lmax分別表示最大延誤時(shí)間和最大延遲時(shí)間。本文研究的問(wèn)題,用三參數(shù)表示法[17]分別表示為

這里disagr(pj,wj)表示工件的加工時(shí)間與權(quán)逆序,即對(duì)任意的工件Ji和Jj,若pi≤pj有wi≥wj;agr(pj,dj)表示工件的加工時(shí)間與工期同序,即對(duì)任意的工件Ji和Jj,若pi≤pj時(shí)有di≤dj。

2 主要性質(zhì)

假設(shè)存在2個(gè)排序S=(π1,i,j,π2)和S′=(π1,j,i,π2),這里π1和π2分別表示部分序列,也就是排在工件Ji和Jj前工件的集合為π1,排在工件Ji和Jj后工件的集合為π2。工件Ji和Jj分別表示在S中第r和第r+1位置上的工件,也就是在π′中第r+1和第r位置上的工件。由于Cj(S)=Cj(S′),j=1,…,r-1,故設(shè)Cr-1(S)=Cr-1(S′)=t。在排序S中,工件Ji和Jj的完工時(shí)間分別為

同理,排序S′中,工件Jj和Ji的完工時(shí)間分別為

2.1 最大完工時(shí)間問(wèn)題

為了更好的說(shuō)明最大完工時(shí)間問(wèn)題,首先給出下列引理。

引理1[15]對(duì)于問(wèn)題1|pj[r]=pjg(r)|Cmax,工件按SPT規(guī)則排列得到最優(yōu)排序。

定理1 對(duì)于問(wèn)題1|pj[r]=pjg(r),spsd,qpsd|Cmax,工件按SPT規(guī)則排列得到最優(yōu)排序。

證明 用反證法。假設(shè)存在最優(yōu)排序S=(π1,i,j,π2),其中2個(gè)相鄰工件Ji和Jj分別在第r和第r+1個(gè)位置上加工,且pi>pj,而S′=(π1,j,i,π2),則由等式(1)～式(4)有

故

Cj(S)-Ci(S′)=(pi-pj)[g(r)-g(r+1)]+(b+γ)(pi-pj)g(r)

由假設(shè)pi>pj,且g(r)為與位置r相關(guān)的非負(fù)遞減函數(shù),帶入等式(4)中,有

即交換后工件Ji和Jj的完工時(shí)間變小了,也就是排在Ji和Jj后工件的開(kāi)始加工時(shí)間變小了,故變換后的最大完工時(shí)間變小了。這與假設(shè)S是最優(yōu)排序矛盾。

2.2 加權(quán)總完工時(shí)間問(wèn)題

當(dāng)wj=1時(shí),加權(quán)總完工時(shí)間問(wèn)題即為總完工時(shí)間問(wèn)題,它與最大完工時(shí)間問(wèn)題類似。為了更好的說(shuō)明總完工時(shí)間問(wèn)題,給出下列引理。

引理2[15]對(duì)于問(wèn)題1|pj[r]=pjg(r)|∑Cj,工件按SPT規(guī)則排列得到最優(yōu)排序。

定理2 對(duì)于問(wèn)題1|pj[r]=pjg(r),spsd,qpsd|∑Cj,工件按SPT規(guī)則排列得到最優(yōu)排序。

證明 與定理1類似,假設(shè)存在最優(yōu)排序S,其中2個(gè)相鄰工件Ji和Jj分別在第r和第r+1個(gè)位置上加工,且pi>pj,在其他工件位置不變的情況下,只交換工件Ji和Jj的位置,得到排序S′,比較等式(1)～式(4)有

由假設(shè)pi>pj,且g(r)為與位置r相關(guān)的非負(fù)遞減函數(shù),帶入等式(6)中,有Ci(S)+Cj(S)>Ci(S′)+Cj(S′)。即交換后工件Ji和Jj的完工時(shí)間和變小了;再由(5)可知,Cj(S)>Ci(S′),也就是排在Ji和Jj后工件的開(kāi)始加工時(shí)間變小了,則它們的完工時(shí)間不會(huì)增加。而排在工件Ji和Jj前工件的完工時(shí)間不變,故交換后的總完工時(shí)間變小了。這與假設(shè)S是最優(yōu)排序矛盾。

根據(jù)以上分析,下面對(duì)目標(biāo)函數(shù)為加權(quán)總完工時(shí)間的問(wèn)題進(jìn)行討論:

定理3 在問(wèn)題1|pj[r]=pjg(r),spsd,qpsd,disagr(pj,wj)|∑wjCj中,工件按照pj/wj非減的順序(WSPT規(guī)則)排列可得到最優(yōu)排序;其中disagr(pj,wj)表示工件的加工時(shí)間與權(quán)是逆序的,即對(duì)任意的工件Ji和Jj,若pi≤pj有wi≥wj。

證明 假設(shè)pi≤pj,由定理1可知Cj(S)≤Ci(S′),欲證S優(yōu)于S′,則只需證明wiCi(S)+wjCj(S)≤wiCi(S′)+wjCj(S′)即可。由等式(1)～式(4),有

因?yàn)閜i≤pj,而工件的加工時(shí)間與權(quán)逆序,則wi≥wj,即wipj≥wjpi。又因?yàn)間(r)為與位置r相關(guān)的非負(fù)遞減函數(shù),帶入等式(7)中,有wiCi(S)+wjCj(S)≤wiCi(S′)+wjCj(S′)。

下面討論目標(biāo)函數(shù)與工期有關(guān)的問(wèn)題, 主要考慮總延誤時(shí)間問(wèn)題,最大延誤時(shí)間問(wèn)題和最大延遲時(shí)間問(wèn)題。

2.3 總延誤時(shí)間問(wèn)題

定理4 在問(wèn)題1|pj[r]=pjg(r),spsd,qpsd,agr(pj,dj)|∑Tj中,工件按照dj非減順序(EDD規(guī)則)排列可得到最優(yōu)排序;其中agr(pj,dj)表示工件的加工時(shí)間與工期是同序的,即對(duì)任意的工件Ji和Jj,若pi≤pj時(shí)有di≤dj。

證明 假設(shè)pi≤pj,則有di≤dj。對(duì)于排序S=(π1,i,j,π2)和S′=(π1,j,i,π2),由于排序π1中的加工順序相同,則總延誤是相等的。由定理1可知,最大完工時(shí)間按SPT規(guī)則排序最優(yōu),因此S中部分序列π2的總延誤不會(huì)大于S′中部分序列π2的總延誤。為了證明序列S的總延誤小于或等于序列S′的總延誤,只需證Ti(S)+Tj(S)≤Ti(S′)+Tj(S′)。

為了分別比較序列S和S′中工件Ji、Jj的總延誤,考慮2種情況。

和

假設(shè)Ti(S)≠0且Tj(S)≠0,由定理1,di≤dj和pi≤pj有

假設(shè)Ti(S)≠0且Tj(S)≠0,由定理1,di≤dj和pi≤pj有

因此,Ti(S)+Tj(S)≤Ti(S′)+Tj(S′)。

根據(jù)上述問(wèn)題的討論,對(duì)于最大延誤問(wèn)題,有如下結(jié)論:

推論 在問(wèn)題1|pj[r]=pjg(r),spsd,qpsd,agr(pj,dj)|Tmax中,工件按照dj非減順序(EDD規(guī)則)排列可得到最優(yōu)排序。

證明 與定理4的證明類似,省略。

2.4 最大延遲時(shí)間問(wèn)題

定理5 在問(wèn)題1|pj[r]=pjg(r),spsd,qpsd,agr(pj,dj)|Lmax中,工件按照dj非減順序(EDD規(guī)則)排列可得到最優(yōu)排序。

在排序S和S′中分別有:

Li(S)=Ci(S)-di,Lj(S)=Cj(S)-dj,Li(S′)=Ci(S′)-di,Lj(S′)=Cj(S′)-dj。

2.5 數(shù)值例子

解p[1]1表示第1個(gè)位置工件的實(shí)際加工時(shí)間,p[1]表示第1個(gè)位置工件的基本加工時(shí)間,則

3 結(jié) 論

在本文中,研究了帶有學(xué)習(xí)效應(yīng)、安裝時(shí)間和送出時(shí)間的單機(jī)排序問(wèn)題。工件的實(shí)際加工時(shí)間是與工件的基本加工時(shí)間和工件的實(shí)際加工位置相關(guān)的一般函數(shù)。工件的安裝時(shí)間和送出時(shí)間均依賴于已加工完的工件的實(shí)際加工時(shí)間的簡(jiǎn)單函數(shù)。目標(biāo)函數(shù)為最大完工時(shí)間,總完工時(shí)間,加權(quán)總完工時(shí)間,總延誤時(shí)間,最大延誤時(shí)間和最大延遲時(shí)間。證明了上述問(wèn)題都是多項(xiàng)式時(shí)間可解的。對(duì)于帶有學(xué)習(xí)效應(yīng)、安裝時(shí)間和送出時(shí)間問(wèn)題的其他目標(biāo)函數(shù),如總誤工工件數(shù),公共工期指派等問(wèn)題,也正在研究中。同時(shí),可將安裝時(shí)間和送出時(shí)間加入到退化效應(yīng)的函數(shù)中,也可將模型推廣到多機(jī)的問(wèn)題,有待進(jìn)一步研究。

[ 1 ]BISKUPD.Single-machineschedulingwithlearningconsiderations[J].EurJOperRes, 1999,115(1):173-178.

[ 2 ]MOSHEIOVG.Schedulingproblemswithalearningeffect[J].EurJOperRes, 2001,132(3):687-693.

[ 3 ]WANGJibo,MaLi,WangLiyan,etal.Twosinglemachineschedulingproblemswithalearningeffect[J].JDalianUniversityTechnol, 2008,48(6):932-936.

[ 4 ]KUOWH,YANGDL.Minimizingthetotalcompletiontimeinasingle-machineschedulingproblemwithatime-dependentlearningeffect[J].EurJOperRes, 2006,174(2):1184-1190.

[ 5 ]CHENGMB,TADIKAMALLAPR,SHANGJ,etal.Singlemachineschedulingproblemswithexponentiallytime-dependentlearningeffects[J].JManufSyst, 2015,34:60-65.

[ 6 ]WANGJibo,HSUCJ,YANGDL.Single-machineschedulingwitheffectsofexponentiallearningandgeneraldeterioration[J].ApplMathModel, 2013,37(4):2293-2299.

[ 7 ]YINYunqiang,XUDehua,SUNKaibiao,etal.Someschedulingproblemswithgeneralposition-dependentandtime-dependentlearningeffects[J].InfSci, 2009,179(14):2416-2425.

[ 8 ]YANGDL,CHENGTCE,KUOWH.Schedulingwithagenerallearningeffect[J].IntJAdvManufTechnol, 2013,67(1/2/3/4):217-229.

[ 9 ]KOULAMASC,KYPARISISGJ.Single-machineschedulingproblemswithpast-sequence-dependentsetuptimes[J].EurJOperRes, 2008,187(3):1045-1049.

[10]KUOWH,YANGDL.Singlemachineschedulingwithpast-sequence-dependentsetuptimesandlearningeffects[J].InfProcessLett, 2007,102(1):22-26.

[11]WANGJibo.Single-machineschedulingwithpast-sequence-dependentsetuptimesandtime-dependentlearningeffect[J].ComputIndEng, 2008,55(3):584-591.

[12]LEEWC.Single-machineschedulingwithpast-sequence-dependentsetuptimesandgeneraleffectsofdeteriorationandlearning[J].OptimizationLett, 2014,8(1):135-144.

[13]HsuCJ,KuoWH,YangDL.Unrelatedparallelmachineschedulingwithpast-sequence-dependentsetuptimeandlearningeffects[J].ApplMathModel, 2011,35(3):1492-1496.

[14]KOULAMASC,KYPARISISGJ.Single-machineschedulingproblemswithpast-sequence-dependentdeliverytimes[J].IntJProducEcon, 2010,126(2):264-266.

[15]RUSTOGIK,STRUSEVICHVA.Simplematchingvslinearassignmentinschedulingmodelswithpositionaleffects:Acriticalreview[J].EurJOperRes, 2012,222(3):393-407.

[16]ZHAOChuanli,TANGHengyong.Singlemachineschedulingproblemswithgeneralposition-dependentprocessingtimesandpast-sequence-dependentdeliverytimes[J].JApplMathComput, 2014,45(1/2):259-274.

[17]GRAHAMRL,LAWLEREL,LENSTRAJK,etal.Optimizationandapproximationindeterministicsequencingandscheduling:asurvey[J].AnnDiscMath, 1979,5(1):287-326.

Single machine scheduling problems with setup time and delivery time

HUChenchen,ZHAOYufang

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

This paper studies the single machine scheduling problems with learning effect, setup time and delivery time. In this model, the actual processing time of a job is a general function of the normal processing time of the job and its scheduled position. The setup time and delivery time depend on a general function of the processing times of the jobs already processed and its scheduled position, i.e., the setup time and delivery time are past-sequence-dependent(p-s-d).The objectives are to minimize the makespan, the total completion time, the total weighted completion time, the total tardiness, the maximum tardiness, and the maximum lateness. We provide the optimal schedules for some single-machine problems and results show that they are solvable in polynomial time respectively.

scheduling; single machine; learning effect; setup times; delivery times

2014-11-18。

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

胡晨晨(1989-),女,遼寧錦州人,沈陽(yáng)師范大學(xué)碩士研究生; 通信作者: 趙玉芳(1966-),女,遼寧遼陽(yáng)人,沈陽(yáng)師范大學(xué)副教授,博士,碩士研究生導(dǎo)師。

1673-5862(2015)03-0351-07

O223

A

10.3969/ j.issn.1673-5862.2015.03.008