具有惡化效應與可控加工時間的工期指派排序問題研究

王吉波，張 博，劉巍巍

(1.沈陽航空航天大學 理學院，沈陽 110136；2.沈陽體育學院，管理與新聞傳播學院，沈陽 110102；3.東北大學，計算機科學與工程學院，沈陽 110169)

1 提出描述

設有n個工件J1,J2,,Jn要在一臺機器上加工，工件在加工過程中不可中斷，所有工件零時刻到達。本文研究工件的加工時間是消耗資源的線性函數的模型，即假定工件Ji的實際加工時間為

(1)

和

2 主要結論

引理1(WEI等[15]，WANG等[16])對于給定的排序π=[π(1),,π(n)]，工件π(i)的完成時間和實際加工時間分別是：

(2)

和

(3)

證明：與文獻BRUCKER[20]和LIU等[21]中的證明方法類似。

假設一個虛擬的任務J0，其權重是ω0，處理時間是p0=0(任務J0在0時刻調度，即π(0)=0)，可以得到：

(4)

證明：與文獻BRUCKER[20]的證明方法類似。

(5)

證明：與文獻LIU等[21]的證明方法類似。

(6)

其中

Ω1=λ1+bλ2+b(1+b)λ3++b(1+b)n-2λn

Ω2=λ2+bλ3+b(1+b)λ4++b(1+b)n-3λn

Ωn-1=λn-1+bλn

Ωn=λn

(7)

對于共同工期(CON)指派方法，

(8)

對于松弛工期(SLK)指派方法，

(9)

=δ(λ1+bλ2+b(1+b)λ3++b(1+b)n-2λn)(pπ(1)-βπ(1)uπ(1))+

δ(λ2+bλ3+b(1+b)λ4++b(1+b)n-3λn)(pπ(2)-βπ(2)uπ(2))+

δ(λ3+bλ4+b(1+b)λ5++b(1+b)n-4λn)(pπ(3)-βπ(3)uπ(3))++

δ(λn-1+bλn)(pπ(n-1)-βπ(n-1)uπ(n-1))+

δλn(pπ(n)-βπ(n)uπ(n))+

其中Ω1=λ1+bλ2+b(1+b)λ3++b(1+b)n-2λn

Ω2=λ2+bλ3+b(1+b)λ4++b(1+b)n-3λn

Ωn-1=λn-1+bλn

Ωn=λn

對于松弛工期(SLK)工期指派，證明方法相似。

從引理5，通過對式(6)中的uπ(i)(i=1,2,,n)求一階導數，并令導數式子等于0，就可以求得最優uπ(i)，由此得到如下引理。

(10)

其中Ωi(i=1,2,,n)是由式(7)給出。

設二進制變量Xir=1表示工件Ji排在位置r，否則Xir=0。從式(6)可知，最優排序(工件序列)能通過下面的線性指派問題得到。

(11)

S.T.

(12)

(13)

Xir=0或1,i,r=1,2,,n

(14)

其中

(15)

Ωr由式(7)給出。

通過以上引理和分析，對問題

算法1

步驟1 對于CON共同工期指派問題，通過引理3計算k；對于SLK松弛工期指派問題，通過引理4計算l；

步驟2 通過式(11)～(15)解決線性指派問題，從而得到最優排序；

步驟3 通過引理6(式(10))計算最優資源分配；

步驟4 對共同工期CON指派方法，計算工期dopt=Cπ(k)，對松弛工期SLK指派方法，計算qopt=Cπ(I)。

定理1算法1能在時間復雜度O(n3)內解決問題

證明根據引理1-6和線性指派問題，可得算法1的正確性。步驟2線性指派問題的復雜性為O(n3)，步驟1，3，4的復雜性為O(n)，因此算法1總的時間復雜性為O(n3)。

為了詳細說明算法1的計算過程，我們舉出如下的例子：

例1：本例僅考慮共同工期的情況(松弛工期情況計算步驟相似)。n=7，δ=0.5，b=0.05，位置權重分別是ω0=2,ω1=7,ω2=4,ω3=5,ω4=8,ω5=2,ω6=6,ω7=1，在表1中，給出了關于工件參數的其它數據。

表1 例子1的相關數據

表2 例1中λir的值(黑色字體為最優解)

3 結論