王 方,趙傳立
(沈陽(yáng)師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院,沈陽(yáng) 110034)
帶有可控加工時(shí)間的排序問(wèn)題[1-10],自1980年以來(lái)備受關(guān)注,并取得了許多研究成果。本文將學(xué)習(xí)效應(yīng)與可控加工時(shí)間相結(jié)合,拓展了文獻(xiàn)[7]的主要結(jié)果。問(wèn)題可描述如下。
設(shè)有n個(gè)相互獨(dú)立的工件的集合,記為{J1,J2,…,Jn},工件在0時(shí)都已到達(dá),且加工過(guò)程中中斷不被允許。工件J[j]的正常加工時(shí)間為P[j],需要確定工件的加工順序、劃分、工期和資源分配量,極小化一個(gè)包含加權(quán)總誤工數(shù)、工期分派、最大完工時(shí)間,和總資源消耗的費(fèi)用函數(shù)。即目標(biāo)函數(shù)為以下形式:
其中,Cj是工件Jj的完工時(shí)間是最大完工時(shí)間。Uj是工件Jj的延誤指示變量,即當(dāng)Cj>dj時(shí),置Uj=1;否則,置Uj=0,dj≥0是工件Jj的工期。αj是工件Jj的延誤費(fèi)用,非負(fù)參數(shù)α和β分別表示工期的單位費(fèi)用和最大完工時(shí)間的費(fèi)用。uj是分配到工件Jj上的資源量,vj是分配到工件Jj上的資源量的單位費(fèi)用。
研究帶有以下兩種工期分派方法的問(wèn)題。
1)CON型:共同工期分派方法。這里所有工件都分派一個(gè)共同工期,即dj=d,j=1,2,…,n
2)SLK型:松弛工期分派方法。這里所有工件都有一個(gè)相同的松弛時(shí)間,即dj=pj+slk,這里slk≥0是一個(gè)確定的變量。
文獻(xiàn)[11]考慮了一種機(jī)器具有學(xué)習(xí)效應(yīng)的模型,當(dāng)工件Jj排在序列的第r個(gè)位置時(shí),其實(shí)際加工時(shí)間為pj=,aj≤0是一個(gè)與工件相關(guān)的學(xué)習(xí)指標(biāo)。本文中工件Jj的實(shí)際加工時(shí)間為:
I線(xiàn)性資源消耗函數(shù):
凸資源消耗函數(shù):
式中,k是一個(gè)正的常數(shù)。
容易驗(yàn)證,帶有CON型和SLK型工期分派方法的加工時(shí)間為常量的排序問(wèn)題中的某些結(jié)論,仍然可以推廣到可控加工時(shí)間的情形。并且?guī)в蠸LK型的問(wèn)題與CON型類(lèi)似,因此以下本文均以CON型為例討論。
在CON型工期分派方法下,工件可以劃分為2個(gè)相鄰的集合:
1)集合E。這里所有工件的加工時(shí)間總和定義為工期d的值,且這里的工件都在它的工期前完工,故稱(chēng)E為提前工件集合。
2)集合T。這里所有工件都在它的工期后完工,故稱(chēng)T為延誤工件集合。
引理1 在CON型工期分派方法下,存在一個(gè)最優(yōu)排序,任意兩個(gè)工件的加工過(guò)程之間都沒(méi)有空閑時(shí)間,且第一個(gè)工件的開(kāi)始時(shí)間為零。
文中帶有[j]的下標(biāo)均表示工件排在第j個(gè)位置。
引理2 存在一個(gè)最優(yōu)排序,在CON型工期分派方法下,集合E排在集合T前。
在CON型工期分派方法下,當(dāng)資源分配與工件所排位置確定后,工件的加工時(shí)間被固定,就簡(jiǎn)化為找最優(yōu)劃分τ*和工期d,極小化這個(gè)問(wèn)題已被文獻(xiàn)[12]解決,并在O(n)時(shí)間內(nèi)給出以下算法。
算法1:
步驟2 集合E排在T之前,并且每個(gè)集合內(nèi)部的次序無(wú)關(guān)。
步驟3 最優(yōu)工期為集合E的完工時(shí)間,即
由算法1可知,最優(yōu)工期和工件的劃分是由加工時(shí)間決定的。然而,當(dāng)加工時(shí)間由式(2)和式(3)確定時(shí),意味著最優(yōu)工期和工件的劃分還將與工件所排位置和分配的資源有關(guān)。
由于對(duì)任意一種給定的劃分、排序和資源分配,相應(yīng)的最優(yōu)工期就可以確定,因此,以下這個(gè)問(wèn)題旨在確定最優(yōu)的劃分、排序和資源分配。
對(duì)任意一個(gè)給定的劃分和排序,目標(biāo)函數(shù)式(1)可變形為:
假定|E|=l,|T|=n-l.則上式又可變形為:
當(dāng)加工時(shí)間為一個(gè)線(xiàn)性資源消耗函數(shù)式(2)時(shí),目標(biāo)函數(shù)式(4)變?yōu)椋?/p>
對(duì)于SLK型工期分派方法,帶有固定加工時(shí)間的相關(guān)結(jié)論文獻(xiàn)[8]中已做了詳細(xì)分析。
引理3 在CON型工期分派方法下,對(duì)于任意給定的劃分和工件序列,最優(yōu)資源分配作為劃分和工件序列的一個(gè)函數(shù),可以這樣得到:
證明 對(duì)式(5)關(guān)于u[j]求導(dǎo)得證。
由以上分析可知,對(duì)于任意給定的劃分和排序,最優(yōu)資源分配都可以由引理3求出,那么,這個(gè)問(wèn)題就簡(jiǎn)化為求一個(gè)最優(yōu)劃分和最優(yōu)序列的排序問(wèn)題。
然而,對(duì)于任意一個(gè)給定的劃分,最優(yōu)排序可以通過(guò)在O(n3)時(shí)間內(nèi)解一個(gè)指派問(wèn)題得到,分析如下:
根據(jù)前面在CON型工期分派方法下假定的劃分,對(duì)于目標(biāo)函數(shù)(5)式,當(dāng)l給定時(shí),令
其中,cij(l)依目標(biāo)函數(shù)式(5)中Wj的不同而不同。
定義xij為一個(gè)0-1變量,當(dāng)工件Ji排到第j個(gè)位置時(shí),xij=1;否則,xij=0。對(duì)于目標(biāo)函數(shù)式(5),指派問(wèn)題可表示如下:
引理4 對(duì)于目標(biāo)函數(shù)式(1),任意給定一種劃分τ,在CON型工期分派方法下,當(dāng)加工時(shí)間由式(2)確定時(shí),相關(guān)最優(yōu)排序可以通過(guò)解一個(gè)指派問(wèn)題在O(n3)時(shí)間內(nèi)得到。
根據(jù)以上的分析,對(duì)于任意一個(gè)給定的劃分,都可以通過(guò)解指派問(wèn)題找到最優(yōu)排序。因此,這個(gè)問(wèn)題又進(jìn)一步簡(jiǎn)化為找最優(yōu)劃分τ*的問(wèn)題。
因?yàn)閘的值有n種可能的取法,所以為了找最優(yōu)的劃分,只有取遍所有l(wèi)可能值并解相應(yīng)的l值對(duì)應(yīng)的指派問(wèn)題,才能得到這個(gè)問(wèn)題的最優(yōu)解。這個(gè)問(wèn)題的最優(yōu)解總結(jié)為算法2。
算法2 求解帶有CON型工期分派方法的線(xiàn)性資源消耗函數(shù)最優(yōu)解的算法。
初始 置Z*=∞,l=0。
步驟1 當(dāng)l≤n時(shí):
步驟1.1 通過(guò)式(7)計(jì)算cij(l)的值;
步驟1.2 解指派問(wèn)題P1(l):,確定工件的最優(yōu)排序π*=[1],[2],…,[n]和極小化費(fèi)用Z(l);
步驟1.3 如果Z(l)<Z*,那么,置Z*=Z(l),l*=l,π*(l*)=π*(l);
步驟1.4l=l+1。
步驟2 當(dāng)l=l*,π*(l)=π*(l*)時(shí),通過(guò)引理3計(jì)算最優(yōu)資源分配u*(l),通過(guò)式(2)計(jì)算最優(yōu)加工時(shí)間
定理1 算法2在O(n4)時(shí)間內(nèi)解決了在CON型工期分派方法下,這個(gè)問(wèn)題的目標(biāo)函數(shù)為一個(gè)線(xiàn)性資源消耗函數(shù)時(shí)的最優(yōu)解。
當(dāng)加工時(shí)間為一個(gè)凸資源消耗函數(shù)式(3)時(shí),代入式(4),則目標(biāo)函數(shù)變?yōu)橐韵滦问剑?/p>
由目標(biāo)函數(shù)式(8)可以看出,在CON型工期分派方法下,任意給定一種劃分和排序,當(dāng)加工時(shí)間為一個(gè)凸資源消耗函數(shù)時(shí),這個(gè)問(wèn)題變?yōu)橐粋€(gè)關(guān)于資源分配的凸函數(shù)。因此,最優(yōu)資源分配可描述如下:
引理5 最優(yōu)資源分配u*(π,l),作為劃分和工件序列的一個(gè)函數(shù),是:
CON型:
把引理5中的最優(yōu)資源分配分別代入目標(biāo)函數(shù)式(8),得到
由于對(duì)于任意給定的劃分和排序,最優(yōu)資源分配都可以通過(guò)引理5得到。因此,這個(gè)問(wèn)題又簡(jiǎn)化為找最優(yōu)劃分和排序的問(wèn)題。
此時(shí),任意給定的一種劃分,最優(yōu)排序仍然可以通過(guò)解指派問(wèn)題,在O(n3)時(shí)間內(nèi)得到。分析如下:
根據(jù)前面在CON型工期分派方法下假定的劃分,對(duì)于目標(biāo)函數(shù)式(7),當(dāng)l給定時(shí),令
其中,cij(l)依目標(biāo)函數(shù)(9)式中Wj的不同而不同。
定義xij為一個(gè)0-1變量,當(dāng)工件Ji排到第j個(gè)位置時(shí),xij=1;否則,xij=0。對(duì)于目標(biāo)函數(shù)(9)式,指派問(wèn)題的表示同前面P1(t)的形式,不妨記為P2(t)。
引理6 對(duì)于這個(gè)問(wèn)題,任意給定一種劃分τ,在CON型工期分派方法下,當(dāng)加工時(shí)間由式(3)確定時(shí),相關(guān)最優(yōu)排序可以通過(guò)解一個(gè)指派問(wèn)題在O(n3)時(shí)間內(nèi)得到。
由以上的分析,有下面的結(jié)論
對(duì)于任意一個(gè)給定的劃分,都可以通過(guò)解指派問(wèn)題找到最優(yōu)排序。因此,這個(gè)問(wèn)題的最優(yōu)解又進(jìn)一步簡(jiǎn)化為找最優(yōu)劃分τ*的問(wèn)題。
同樣,因?yàn)閘的值有n種可能的取法,只有取遍的所有l(wèi)的可能值并解相應(yīng)的l值對(duì)應(yīng)的指派問(wèn)題,才能得到這個(gè)問(wèn)題的最優(yōu)解。因此,當(dāng)加工時(shí)間為一個(gè)凸資源消耗函數(shù)時(shí),在CON型工期分派方法下,這個(gè)問(wèn)題的最優(yōu)解總結(jié)為算法3。
算法3 求解帶有CON型工期分派方法的凸資源消耗函數(shù)最優(yōu)解的算法。
初始 置Z*=∞,l=0。
步驟1 當(dāng)l≤n時(shí):
步驟1.1 通過(guò)式(10)計(jì)算cij(l)的值;
步驟1.2 解指派問(wèn)題P2(l),確定工件的最優(yōu)排序π*=[1],[2],…,[n]和極小化費(fèi)用Z(l);
步驟1.3 如果Z(l)<Z*,那么,置Z*=Z(l),l*=l,π*(l*)=π*(l);
步驟1.4l=l+1。
步驟2 當(dāng)l=l*,π*(l)=π*(l*)時(shí),通過(guò)引理5計(jì)算最優(yōu)資源分配u*(l),通過(guò)式(3)計(jì)算最優(yōu)加工時(shí)間
定理2 算法3在O(n4)時(shí)間內(nèi)解決了在CON型工期分派方法下,這個(gè)問(wèn)題的目標(biāo)函數(shù)為一個(gè)凸資源消耗函數(shù)時(shí)的最優(yōu)解。
現(xiàn)實(shí)生活中,學(xué)習(xí)效應(yīng)是普遍存在的,本文將學(xué)習(xí)效應(yīng)與可控加工時(shí)間相結(jié)合,使得問(wèn)題更具有廣泛應(yīng)用性和實(shí)際意義。這個(gè)問(wèn)題在多機(jī)環(huán)境下或者加工時(shí)間為其他資源消耗函數(shù)的情形有待進(jìn)一步研究。
[1]LEYVAND Y,SHABTAY D,STEINER G A.A unified approach for scheduling with conwex resource consumption functions using positional penalties[J].Eur J Oper Res,2010,206(2):301-312.
[2]SU L H,LIEN C Y.Scheduling parallel machines with resource dependent processing times[J].Int J Prod Econ,2009,117(2):256-266.
[3]SHABTAY D,STEINER G.A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assignable due dates[J].J Sched,2011,14(5):455-469.
[4]SHABTAY D,STEINER G.A survey of scheduling with controllable processing times[J].Disc Appl Math,2007,155(13):1643-1666.
[5]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.
[6]CHENG T C E,OGAZ C,QI X D.Due-date assignment and single scheduling with compressible processing times[J].Int J Prod Econ,1996,43(1):29-35.
[7]SHABTAY D,STEINER G.Optimal due date assignment and resource allocation to minimize the weighted number of tardy jobs on a single machine[J].Manuf Serv Oper Manage,2007,9(3):332-350.
[8]BISKUP D.Single-machine scheduling with learning considerations[J].Eur J Oper Res,1999,115(1):173-178.
[9]BISKUP D.A state-of-the-art review on scheduling with learning effect[J].Eur J Oper Res,2008,188(2):315-329.
[10]WANG D,WANG M Z,WANG Jibo.Single-machine scheduling with learning effect and resource-dependent processing times[J].Comput indust Eng,2010,59(3):458-462.
[11]MOSHEIOV G,SIDNE J B.Scheduling with general job-dependent learning curves[J].Eur J Oper Res,2003,147(3):665-670.
[12]KAHLBACHER H G,CHENG T C E.Parallel machine scheduling to minimize costs for earliness and number of tardy jobs[J].Disc Appl Math,1993,47(2):139-164.