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

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

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

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

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

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

0 引 言

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

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

1 問題描述

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

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

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

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

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

(1)

2 問題分析及算法設(shè)計

2.1 問題分析

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

2.2 算法P

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

(2) 若xi≥m,則將Si中前m個作業(yè)按順序排在m臺機(jī)器上加工,此時對應(yīng)的作業(yè)調(diào)度即為區(qū)間[ti,ti+1](i=1,2,…,k-1)上作業(yè)在m臺機(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ū)間長度的作業(yè),超出區(qū)間長度的那部分作業(yè)中斷,放到下一個區(qū)間加工。如果機(jī)器還有空閑,步驟(3)～步驟(5)討論如何加工Ti中其余作業(yè)。

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

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

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

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

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

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

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

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

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

證明設(shè)算法P得到的調(diào)度結(jié)果是S*。根據(jù)算法P的步驟可以看出,調(diào)度S*具備引理的是3個條件,因此調(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個作業(yè)安排在2臺機(jī)器上加工,超過區(qū)間范圍的就此中斷,則中斷剩余的作業(yè)時間為{7,3},余下的作業(yè)時間為{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個作業(yè)安排在2臺機(jī)器上加工,超過區(qū)間范圍的就此中斷,則中斷剩余的作業(yè)時間為{9,2},余下的作業(yè)時間為{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個作業(yè)安排在2臺機(jī)器上加工,超過區(qū)間范圍的就此中斷,則中斷剩余的作業(yè)時間為{6,3},余下的作業(yè)時間為{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所示。

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

具體如圖2所示。

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

具體如圖3所示。

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

具體如圖4所示。

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

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

4 結(jié) 論

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

[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ī)上在線排序問題的近似算法[J].運籌與管理,2004,13(6):11-15,95.

[6] 程貞敏,張喜娟,李洪興.工件帶準(zhǔn)備時間的平行機(jī)調(diào)度問題的一個近似算法[J].北京師范大學(xué)學(xué)報(自然科學(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á)時間的單機(jī)調(diào)度問題的改進(jìn)算法[J].中國機(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é)科點專項科研基金資助項目(20120111120013)

趙福強(qiáng)(1989-),男,安徽阜陽人,合肥工業(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é)任編輯 萬倫來)