考慮作業(yè)釋放時(shí)間和機(jī)器數(shù)量變化的同型機(jī)調(diào)度問(wèn)題

趙福強(qiáng), 劉桂慶

(合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院,安徽 合肥 230009)

考慮作業(yè)釋放時(shí)間和機(jī)器數(shù)量變化的同型機(jī)調(diào)度問(wèn)題

趙福強(qiáng), 劉桂慶

(合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院,安徽 合肥 230009)

同型機(jī)調(diào)度;機(jī)器影響;釋放時(shí)間;可中斷;最大完工時(shí)間

0 引 言

生產(chǎn)調(diào)度問(wèn)題是一類典型的組合優(yōu)化問(wèn)題,它旨在利用現(xiàn)有資源,在滿足一些必要條件基礎(chǔ)上完成一定任務(wù)并達(dá)到特定的調(diào)度目標(biāo)。在現(xiàn)代生產(chǎn)制造中,企業(yè)投入生產(chǎn)的機(jī)器數(shù)量是制造加工系統(tǒng)的一個(gè)重要特征,因此研究機(jī)器數(shù)量投入對(duì)企業(yè)生產(chǎn)效率的影響具有重要意義。當(dāng)企業(yè)接收一批訂單后,雖然有足夠的機(jī)器資源去加工這些訂單,但如果投入很多機(jī)器處理這些訂單,很可能造成資源浪費(fèi)。另外,機(jī)器數(shù)量變化調(diào)度問(wèn)題不同于傳統(tǒng)調(diào)度問(wèn)題。因此,該項(xiàng)研究?jī)?nèi)容具有重要的理論價(jià)值和現(xiàn)實(shí)意義。

關(guān)于作業(yè)帶有釋放時(shí)間且允許中斷的2臺(tái)同型機(jī)的最小化完工時(shí)間和問(wèn)題,文獻(xiàn)[6]提出了一個(gè)啟發(fā)式算法,并證明了某些特殊的實(shí)例,該算法能夠得到最優(yōu)調(diào)度,指出了當(dāng)有n個(gè)作業(yè)時(shí)該算法的最壞情況誤差界為2(1-1/n)。關(guān)于作業(yè)帶有釋放時(shí)間且允許中斷m個(gè)同型機(jī)的最小化最大完工時(shí)間問(wèn)題,文獻(xiàn)[7]構(gòu)造了改進(jìn)的McNaughton規(guī)則,并證明該規(guī)則可以求出該問(wèn)題的最優(yōu)解。另外,有些學(xué)者研究了考慮釋放時(shí)間其他目標(biāo)函數(shù)的平行機(jī)調(diào)度問(wèn)題。例如,文獻(xiàn)[8]基于SPT和ERD規(guī)則的綜合改進(jìn),為作業(yè)帶有釋放時(shí)間單機(jī)最小化完工時(shí)間和問(wèn)題提出一種INSERT算法,并運(yùn)用大量實(shí)驗(yàn)數(shù)據(jù)證明了其性能更優(yōu)。關(guān)于作業(yè)帶有釋放時(shí)間的m個(gè)同型機(jī)的最小化完工時(shí)間和問(wèn)題,文獻(xiàn)[9]將此問(wèn)題松弛成可中斷的問(wèn)題加以解決,再將松弛問(wèn)題的解可行化,提出了一個(gè)競(jìng)爭(zhēng)比為7/3的近似算法;文獻(xiàn)[10]運(yùn)用作業(yè)分割技術(shù)為此問(wèn)題建立下界,進(jìn)而構(gòu)造分枝定界算法,能夠解決2臺(tái)機(jī)器100個(gè)作業(yè)規(guī)模的問(wèn)題。

1 問(wèn)題描述

本文研究的問(wèn)題基于以下幾點(diǎn)假設(shè):

(1) 機(jī)器的生產(chǎn)能力有限,機(jī)器在工作時(shí)間一直處于啟動(dòng)狀態(tài),且不考慮設(shè)備故障。

(2) 每個(gè)作業(yè)在任一臺(tái)機(jī)器上的加工順序都有且只有一個(gè),每臺(tái)機(jī)器任一時(shí)刻只能加工一個(gè)作業(yè),任一作業(yè)同一時(shí)刻只能被一臺(tái)機(jī)器加工,機(jī)器在沒(méi)有安排作業(yè)或作業(yè)沒(méi)有到達(dá)時(shí)是空閑的。

(3) 不考慮原材料短缺和操作人員空缺的情況。

本文研究問(wèn)題描述如下:有n個(gè)作業(yè)J={Jj|j=1,2,…,n;n≥m}在m臺(tái)機(jī)器M={Mi|i=1,2,…,m;m≥2}上加工(不妨設(shè)每臺(tái)機(jī)器的速度為單位速度),每個(gè)作業(yè)有釋放時(shí)間rj(rj≥0),加工時(shí)間pj(pj>0),各作業(yè)之間相互獨(dú)立。每個(gè)作業(yè)要在釋放時(shí)間后才能被加工,加工過(guò)程可以中斷,作業(yè)在任何時(shí)間都可以被中斷,也可以在任何時(shí)間繼續(xù)加工且中斷后再加工時(shí)不接受懲罰,目標(biāo)是最優(yōu)化機(jī)器影響,具體可表示為:

(1)

2 問(wèn)題分析及算法設(shè)計(jì)

2.1 問(wèn)題分析

基于以上解決思路,本文將作業(yè)按釋放時(shí)間單調(diào)不減的順序排列,即r1≤r2≤…≤rn。設(shè)rj(j=1,2,…,n)中有k個(gè)不同的數(shù),記為r1=t1

2.2 算法P

(1) 若將Ti中的作業(yè)按加工時(shí)間單調(diào)不增排序得到新的作業(yè)集Si,設(shè)ni為Si中作業(yè)的個(gè)數(shù),即|Si|=ni,則Si中的作業(yè)加工時(shí)間滿足pi1≥pi2≥…≥pini。當(dāng)i=1,2,…,k-1,若存在xi(1≤xi

(2) 若xi≥m,則將Si中前m個(gè)作業(yè)按順序排在m臺(tái)機(jī)器上加工,此時(shí)對(duì)應(yīng)的作業(yè)調(diào)度即為區(qū)間[ti,ti+1](i=1,2,…,k-1)上作業(yè)在m臺(tái)機(jī)器上的調(diào)度。令pil=pil-li(l=1,2,…,m),Ti+1=Ti+1∪{pi1,pi2,…,pim,…,pini},i=i+1,轉(zhuǎn)步驟(1)。若xi

(5) 令Ti+1=Ti+1∪{pini},Ti=Ti-{pini},轉(zhuǎn)步驟(1)。

步驟(2)保證當(dāng)前可以在加工作業(yè)集Ti中大于或等于區(qū)間長(zhǎng)度的作業(yè),超出區(qū)間長(zhǎng)度的那部分作業(yè)中斷,放到下一個(gè)區(qū)間加工。如果機(jī)器還有空閑,步驟(3)～步驟(5)討論如何加工Ti中其余作業(yè)。

證明由題設(shè)條件可知:

則在區(qū)間[ti,ti+1](i=1,2,…,k-1)上,

引理1 對(duì)問(wèn)題Pm|rj,pmtn|Cmax,若一個(gè)可行調(diào)度Sp滿足如下條件:

(1) 在調(diào)度Sp中的每一個(gè)區(qū)間[t1,t2],[t2,t3],…,[tk-1,tk]上機(jī)器無(wú)空閑,或當(dāng)前區(qū)間可以加工的作業(yè)已經(jīng)加工完成。

(2) 在調(diào)度Sp中的最后一個(gè)區(qū)間[tk,tk+1)上,最大加工時(shí)間pk1具有如下性質(zhì)之一:①pk1的準(zhǔn)備時(shí)間為tk,即此作業(yè)在前k-1個(gè)區(qū)間都不能被加工；②pk1是被中斷后的剩余加工時(shí)間,而且從它的釋放時(shí)間開(kāi)始就一直被加工。

(3) 在調(diào)度Sp中的最后一個(gè)區(qū)間[tk,tk+1)上,設(shè)還沒(méi)加工作業(yè)的時(shí)間為pk1,pk2,…,pknk,此調(diào)度下得到的時(shí)間表長(zhǎng)為Cmax(Sp),且有：

則同時(shí)具備以上3個(gè)條件的調(diào)度Sp為最優(yōu)調(diào)度。

由條件(2)知,加工時(shí)間pk1被中斷的可能性最小。

故同時(shí)具備以上3個(gè)條件的調(diào)度為問(wèn)題Pm|rj,pmtn|Cmax的最優(yōu)調(diào)度。證畢。

證明設(shè)算法P得到的調(diào)度結(jié)果是S*。根據(jù)算法P的步驟可以看出,調(diào)度S*具備引理的是3個(gè)條件,因此調(diào)度S*為最優(yōu)調(diào)度。證畢。

3 算 例

表1 作業(yè)信息

在區(qū)間[3,8]上,T2={12,8,2}∪{4,1}∪{3},S2={12,8,4,3,2,1},l2=5。依次將前2個(gè)作業(yè)安排在2臺(tái)機(jī)器上加工,超過(guò)區(qū)間范圍的就此中斷,則中斷剩余的作業(yè)時(shí)間為{7,3},余下的作業(yè)時(shí)間為{4,3,2,1},此區(qū)間機(jī)器被排滿。

在區(qū)間[8,14]上,T3={15,8,5,3}∪{4,3,2,1}∪{7,3},S3={15,8,7,5,4,3,3,3,2,1},l3=6。依次將前2個(gè)作業(yè)安排在2臺(tái)機(jī)器上加工,超過(guò)區(qū)間范圍的就此中斷,則中斷剩余的作業(yè)時(shí)間為{9,2},余下的作業(yè)時(shí)間為{7,5,4,3,3,3,2,1},此區(qū)間機(jī)器被排滿。

在區(qū)間[14,21]上,T4={13,10,6,4}∪{9,2}∪{7,5,4,3,3,3,2,1},S4={13,10,9,7,6,5,4,4,3,3,3,2,2,1},l4=7。依次將前2個(gè)作業(yè)安排在2臺(tái)機(jī)器上加工,超過(guò)區(qū)間范圍的就此中斷,則中斷剩余的作業(yè)時(shí)間為{6,3},余下的作業(yè)時(shí)間為{9,7,6,5,4,4,3,3,3,2,2,1},此區(qū)間機(jī)器被排滿。

I(2,2)=66/66=1。

作業(yè)最優(yōu)調(diào)度方案如下:

具體如圖1所示。

圖時(shí),作業(yè)最優(yōu)調(diào)度的Gantt chart

具體如圖2所示。

圖時(shí),作業(yè)最優(yōu)調(diào)度的Gantt chart

具體如圖3所示。

圖時(shí),作業(yè)最優(yōu)調(diào)度的Gantt chart

具體如圖4所示。

圖時(shí),作業(yè)最優(yōu)調(diào)度的Gantt chart

圖5 機(jī)器影響隨機(jī)器數(shù)量變化曲線

4 結(jié) 論

本文作業(yè)加工過(guò)程是可中斷的,當(dāng)作業(yè)中斷后恢復(fù)再加工,是否接受一定的懲罰是企業(yè)制造需要考慮的問(wèn)題;對(duì)于作業(yè)不可中斷情形,也有待進(jìn)一步的討論?？紤]到機(jī)器環(huán)境情況,對(duì)應(yīng)的同類機(jī)調(diào)度問(wèn)題也是值得研究的課題。

[1] BREHOB M,TORNG E,UTHAISOMBUT P.Applying extra-resource analysis to load balancing[J].Journal of Scheduling,2000,3(5):273-288.

[2] GRAHAM R L.Bounds for certain multiprocessing anomalies[J].Bell System Technical Journal,1966,45(9):1563-1581.

[3] CHEN B,VAN VLIET A,WOEGINGER G.An optimal algorithm for preemptive on-line scheduling[J].Operations Research Letters,1995,18(3):127-131.

[4] RUSTOGI K,STRUSEVICH V A.Parallel machine scheduling:impact of adding extra machines[J].Operations Research,2013,61(5):1243-1257.

[5] 魯習(xí)文.同型平行機(jī)上在線排序問(wèn)題的近似算法[J].運(yùn)籌與管理,2004,13(6):11-15,95.

[6] 程貞敏,張喜娟,李洪興.工件帶準(zhǔn)備時(shí)間的平行機(jī)調(diào)度問(wèn)題的一個(gè)近似算法[J].北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,45(4):350-354.

[7] HONG K S,LEUNG J Y T.On-line scheduling of real-time tasks[J].IEEE Transactions on Computers,1992,41(10):1326-1331.

[8] 李凱,馬華偉,楊善林.含作業(yè)到達(dá)時(shí)間的單機(jī)調(diào)度問(wèn)題的改進(jìn)算法[J].中國(guó)機(jī)械工程,2008,19(8):929-932.

[9] PHILLIPS C A,SCHULZ A S,SHMOYS D B,et al.Improved bounds on relaxations of a parallel machinescheduling problem[J].Journal of Combinatorial Optimization,1998,1(4):413-426.

[10] YALAOUI F,CHU C.New exact method to solve thePm|rj|∑Cjschedule problem[J].International Journal of Production Economics,2006,100(1):168-179.

Identicalparallelmachineschedulingproblemwithreleasedatesandthechangeofthenumberofmachines

ZHAO Fuqiang, LIU Guiqing

(School of Mathematics, Hefei University of Technology, Hefei 230009, China)

identical parallel machine scheduling; machine impact; release date; preemptive; makespan

2016-04-21；

2016-08-17

教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20120111120013)

趙福強(qiáng)(1989-),男,安徽阜陽(yáng)人,合肥工業(yè)大學(xué)碩士生;

劉桂慶(1978-),女,安徽和縣人,博士,合肥工業(yè)大學(xué)副教授,碩士生導(dǎo)師，通訊作者：E-mail:769450363@qq.com.

10.3969/j.issn.1003-5060.2017.09.025

O223

A

1003-5060(2017)09-1283-06

(責(zé)任編輯 萬(wàn)倫來(lái))