王洪武，賀小莉(天津科技大學(xué)理學(xué)院，天津 300457；天津科技大學(xué)經(jīng)濟管理學(xué)院，天津 300)

一類加工時間依賴資源的鏈約束排序問題

王洪武1，賀小莉2
(1天津科技大學(xué)理學(xué)院，天津 300457；2天津科技大學(xué)經(jīng)濟管理學(xué)院，天津 300222)

考慮了一類工件的加工時間依賴資源，工件具有鏈約束，目標(biāo)函數(shù)為極小化加權(quán)完工時間和的單機排序問題，給出了一個有效的下降算法。

資源約束；排序問題；加權(quán)完工時間和；算法。

0 引言

在實際排序問題中，除了處理機外，還需要另外的附加資源。我們把這類排序問題稱為具有資源約束的排序問題。一般的有資源約束的排序問題是NP困難的。不可再生資源，工件的加工時間受資源約束，目標(biāo)函數(shù)為最大完工時間的一些排序問題已有多項式時間算法。Blazewicz等在文獻[1]中給出了問題的復(fù)雜性為O(n2) 的多項式時間算法，文獻[2]中給出了復(fù)雜性為 O(nlogn)的多項式時間算法。對于目標(biāo)函數(shù)為最小化加權(quán)完工時間和的問題，目前其復(fù)雜性還未解決。文獻 [3]中對提到了一個非常有效的下降算法。本文將該算法推廣到工件具有鏈約束的情況，對鏈不可中斷和鏈可中斷兩種情況分別給出了近似算法。

1 模型描述

對于單臺機器的排序問題，工件Jj的加工時間為Pj=bj-ajuj，(1≤j≤n)，滿足uj≤uj≤，≤U，其中uj是待確定的對工件Jj的資源分配量，aj＞0，bj＞0，為已知常數(shù)，∈[0,bj/aj]，為資源分配量的下限和上限，是資源總量。用三階段法可將我們研究的問題記為

定義1 對于給定的工件集J={J1,J2,…,，用z=(z1,z2,…,zn)表示確定工件可行排序的工件下標(biāo)對應(yīng)的一個排列，Z是所有可行排序的集合。滿足資源約束的分配向量記為u=(u1,u2,…,un)，所有的可行資源分配向量的集合記為U，使目標(biāo)函數(shù)達到最小的()稱為最優(yōu)解，z*稱為最優(yōu)排序，u*稱為最優(yōu)資源分配。

2 算法及復(fù)雜性

對于任意確定的一個滿足資源約束的下標(biāo)排列z∈Z，文獻[4]中給出了相應(yīng)于這一下標(biāo)排列的最優(yōu)資源分配的算法1，其復(fù)雜性為O(nlogn)。

算法1

算法1是對給定的下標(biāo)排列z求一個最優(yōu)的資源分配。由于集合Z在鏈不可中斷的情況下基數(shù)為m!，在鏈可中斷的情況下基數(shù)將更大，因此怎樣能盡快地求出最優(yōu)的下標(biāo)排列z*，是這類問題的困難所在。以下我們將分別對鏈不可中斷和鏈可中斷兩種情況構(gòu)造一個十分有效的下降算法。

2.1 鏈不可中斷的情況

則由工件J1,J2,…,Jk組成的鏈在由工件Jk+1,Jk+2,…,Jn組成的鏈之前加工。

定義2 對任一可行排列z∈Z，u*是對應(yīng)于可行排序z 的最優(yōu)資源分配，對z 中的第i條鏈z(i)，記

(1)取初始排序z0∈Z，置k=0；

(2)調(diào)用算法1，求相應(yīng)于zk的最優(yōu)資源分配uk；

定理2 算法2的目標(biāo)函數(shù)是下降的，算法最終得到的排序是穩(wěn)定的。

根據(jù)推論2.1我們可以對算法2作如下的改進，對鏈i定義

算法3

(1)將所有的鏈按α非增的順序排列，得到z0作為初始排序，置k=0；

i

(2)調(diào)用算法1，求相應(yīng)于zk的最優(yōu)資源分配uk；

(4)按α的非增順序重新排列得到zk+1，（若α=α，鏈i和j 的相對位置不變），如果zk+1=zk，算

z(ki)z(ki)z(kj )法終止；否則k:=k+1，轉(zhuǎn)(2)。

定理3 算法3的復(fù)雜性為O(m!mnlog(m+n))。

證明 算法3第一步的復(fù)雜性為O(mlogm), 第二步的復(fù)雜性為O(nlogn), 即每迭代一次的復(fù)雜性為O(mnlog(m+n)), 最多迭代m!次, 所以算法3的復(fù)雜性為O(m!mnlog(m+n))。證明完畢。

2.2 鏈可中斷的情況

類似于鏈不可中斷的情況，給出算法5，其復(fù)雜性為O(n!mnlog(m+n))。

我們將文獻[2]中給出了ρ因子概念推廣到工件的加工時間受資源約束的情況。

則上式左端的值稱為鏈J1→J2→…→Jk的ρ因子，記為ρ(1,2,…,k )，Jl*稱為決定該鏈ρ因子的工件。

引理2[2]對確定的資源分配u，如果Jl*是決定鏈J1→J2→…→Jk的ρ因子的工件，則存在一個最優(yōu)的排序，在該排序中工件J1,J2,…,Jl*連續(xù)加工而不被其它鏈的工件打斷。

對于工件的加工時間確定、鏈可中斷的排序問題(1)，文獻[5]給出了一個最優(yōu)算法。

算法4[5]

(1)在當(dāng)前未加工的鏈中選擇ρ因子最大的那個鏈加工；

(2)連續(xù)加工已選定的鏈，直到加工完決定該鏈ρ因子的工件；

(3)若已加工完全部工件，則停止；否則，轉(zhuǎn)(1)。

下面給出求解工件加工時間受資源約束時的算法。

算法5

(2)調(diào)用算法1確定排序zk的最優(yōu)資源分配u，更新P，j=1,2,…,n；

(3)調(diào)用算法4確定所有鏈的最優(yōu)排序zk；

(4)如果zk+1=zk算法終止；否則k:=k+1，令所有的工件為未加工的，轉(zhuǎn)(2)。

定理4 由算法5得到的排序zk(k=1,2,…)的目標(biāo)函數(shù)是逐步下降的，算法5的復(fù)雜性為

3 進一步的工作

數(shù)值例子的計算表明算法3和5是非常有效的。對大部分實例，算法3和5得到的穩(wěn)定排序就是最優(yōu)排序。然而，文獻[2]中提到對于無鏈約束的情況，已找到反例，并得到了穩(wěn)定排序并不是最優(yōu)排序的充分條件。因為該反例也可以作為本文所研究問題的一個反例，所以排序是穩(wěn)定的和最優(yōu)排序之間的關(guān)系這一問題還有待進一步的研究。

[1] BLAZEWICZ J, LENSTRA J K, RINNOY KAN A H G. Scheduling subject to resource constraints: classification and complexity[J]. Discrete Applied Mathematics, 1983,5: 11－24.

[2] 唐恒永, 趙傳立. 排序引論[M]. 北京: 科學(xué)出版社, 2002.

[3] 唐國春, 張峰, 羅守成, 等.現(xiàn)代排序論[M]. 上海: 上海科學(xué)技術(shù)出版社,2003.

[4] JANIAK A. Time-optimal control in a single machine problem resource constrains[J]. Automatica,1986, 22:745－747.

[5] MICHAEL P. Scheduling: theory, algorithms, and systems[M]. New Jersey: Prentice hall, Englewood cliffs, 1995.

A Kind of Resource-constrained Scheduling Problem with Chains Precedence Constraints

WANG Hong-wu1，HE Xiao-li2
(1 College of Science, Tianjin University of Science & Technology Tianjin 300457, P. R. China 2 College of Economics and Management, Tianjin University of Science & Technology Tianjin 300222, P. R. China)

A kind of resource-constrained scheduling problem in which the processing time has relation to the resources and the job has chains precedence constraints is proposed. The objective is to minimize the total weighted completion time. An effective algorithm is given.

resource-constrained；scheduling problem；the total weighted completion time; algorithm

O223

A

1001-4543(2010)01-0067-04

2009-08-11;

2010-01-14

王洪武（1980－），男，山東壽光人，講師，碩士，主要研究方向為組合最優(yōu)化，電子郵件：wanghw@tust.edu.cn。

天津科技大學(xué)科學(xué)研究基金（項目編號：No.20090217）