王吉波，張 博，劉巍巍

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

1 提出描述

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

(1)

和

2 主要結(jié)論

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

(2)

和

(3)

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

假設(shè)一個虛擬的任務(wù)J0，其權(quán)重是ω0，處理時間是p0=0(任務(wù)J0在0時刻調(diào)度，即π(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)求一階導數(shù)，并令導數(shù)式子等于0，就可以求得最優(yōu)uπ(i)，由此得到如下引理。

(10)

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

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

(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)解決線性指派問題，從而得到最優(yōu)排序；

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

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

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

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

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

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

表1 例子1的相關(guān)數(shù)據(jù)

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

3 結(jié)論