王吉波，張 博，劉巍巍

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

1 提出描述

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

(1)

和

2 主要結(jié)論

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

(2)

和

(3)

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

假設(shè)一個(gè)虛擬的任務(wù)J0，其權(quán)重是ω0，處理時(shí)間是p0=0(任務(wù)J0在0時(shí)刻調(diào)度，即π(0)=0)，可以得到：

(4)

證明：與文獻(xiàn)BRUCKER[20]的證明方法類似。

(5)

證明：與文獻(xiàn)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)

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

(8)

對(duì)于松弛工期(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

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

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

(10)

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

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

(11)

S.T.

(12)

(13)

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

(14)

其中

(15)

Ωr由式(7)給出。

通過(guò)以上引理和分析，對(duì)問(wèn)題

算法1

步驟1 對(duì)于CON共同工期指派問(wèn)題，通過(guò)引理3計(jì)算k；對(duì)于SLK松弛工期指派問(wèn)題，通過(guò)引理4計(jì)算l；

步驟2 通過(guò)式(11)～(15)解決線性指派問(wèn)題，從而得到最優(yōu)排序；

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

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

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

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

為了詳細(xì)說(shuō)明算法1的計(jì)算過(guò)程，我們舉出如下的例子：

例1：本例僅考慮共同工期的情況(松弛工期情況計(jì)算步驟相似)。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é)論