賈珊珊，嵇雯蕙，陳智斌

（昆明理工大學(xué) 理學(xué)院，云南 昆明 650500）

0 引言

排序問(wèn)題描述如下：若干個(gè)工件要在一些機(jī)器上進(jìn)行加工，如何安排機(jī)器和工件使某些要求（目標(biāo)函數(shù)）達(dá)到最優(yōu)。一個(gè)排序問(wèn)題可以用三元組

α

|

β

|

γ

來(lái)描述，其中

α

域描述機(jī)器環(huán)境，

β

域提供加工特征和約束細(xì)節(jié)，

γ

域描述最小化或最大化的目標(biāo)函數(shù)。對(duì)于平行機(jī)排序問(wèn)題，

α

域用

P

表示，

β

域可能包括多項(xiàng)，如提交日期、機(jī)器適用約束等；

γ

域一般采用最大完工時(shí)間

C

等作為目標(biāo)函數(shù)。經(jīng)典的平行機(jī)排序問(wèn)題（Multiprocessor Scheduling，MS）問(wèn)題可表示為

P||C

。根據(jù)實(shí)際情況研究人員相繼提出了帶懲罰費(fèi)用的排序問(wèn)題

P|rej|C

和帶等級(jí)約束的排序問(wèn)題

P|GoS|C

，本文研究的是帶等級(jí)約束的平行機(jī)排序問(wèn)題。在日常服務(wù)業(yè)中，通常把客戶(hù)歸類(lèi)為白金、黃金、白銀和正式成員，等級(jí)越高客戶(hù)享受越好的服務(wù)，提供區(qū)分服務(wù)的一個(gè)方法是給服務(wù)者（如：機(jī)器）和客戶(hù)（如：工件）貼上帶有服務(wù)等級(jí)的標(biāo)簽，并且服務(wù)者只為等級(jí)不低于自己的客戶(hù)提供服務(wù)，并希望在最短的時(shí)間內(nèi)為所有客戶(hù)完成服務(wù)。對(duì)于此類(lèi)有等級(jí)限制的問(wèn)題，經(jīng)典的平行機(jī)排序已經(jīng)不適用，需要考慮的是等級(jí)約束下的負(fù)載均衡問(wèn)題（

P|GoS|C

）。當(dāng)所有任務(wù)的服務(wù)等級(jí)都相同，并且任務(wù)的服務(wù)等級(jí)都大于等于機(jī)器的服務(wù)等級(jí)時(shí)，本文討論的問(wèn)題就變成了經(jīng)典的平行機(jī)排序問(wèn)題

P||C

，所以本文討論的問(wèn)題仍然是強(qiáng)NP-難的問(wèn)題。

1 符號(hào)說(shuō)明及問(wèn)題描述

1.1 符號(hào)說(shuō)明

部分符號(hào)說(shuō)明如下：

T

：所有工件的加工時(shí)間總和

S

、

S

：等級(jí)為1、等級(jí)為2 的工件集合

n

、

n

：等級(jí)為1、等級(jí)為2 的工件個(gè)數(shù)

D

：多出部分的工件集

1.2 帶服務(wù)等級(jí)的負(fù)載均衡問(wèn)題（P|GoS|Cmax）

本文考慮服務(wù)等級(jí)負(fù)載均衡問(wèn)題的一種特殊情況，3臺(tái)機(jī)器兩個(gè)等級(jí)約束的負(fù)載均衡問(wèn)題（

P

|GoS

|C

）。顯然，該問(wèn)題可分為以下4 種情況進(jìn)行討論：情況（1）：當(dāng)

g

(

M

)=

g

(

M

)=

g

(

M

)=1，

g

(

J

)=1或2時(shí)，所有工件都可放在這3臺(tái)機(jī)器上加工，等同于經(jīng)典平行機(jī)排序問(wèn)題。情況（2）：當(dāng)

g

(

M

)=

g

(

M

)=

g

(

M

)=2，

g

(

J

)=1或2時(shí)，只考慮

g

(

J

)=2 的工件，等同于經(jīng)典平行機(jī)排序問(wèn)題。情況（3）：當(dāng)

g

(

M

)=1，

g

(

M

)=

g

(

M

)=2 且

g

(

J

)=1或2 時(shí)，記該問(wèn)題為

P

|GoS

(

M

)

|C

。情況（4）：當(dāng)

g

(

M

)=

g

(

M

)=1，

g

(

M

)=2 且

g

(

J

)=1或2 時(shí)，記該問(wèn)題為

P

|GoS

(

M

)

|C

。

2 算法說(shuō)明

為了更好地說(shuō)明算法，首先介紹LPT算法。

算法1

最小時(shí)間跨度排序

將工件按照加工時(shí)間從大到小進(jìn)行排序

按照這個(gè)次序在機(jī)器上對(duì)工件排序，將工件放在當(dāng)前負(fù)載最小的機(jī)器上

下面圍繞情況（3）和情況（4）展開(kāi)，并針對(duì)這兩種情況設(shè)計(jì)近似算法。

2.1 P3|GoS(Mi)1,2,2|Cmax

2.2 P3|GoS(Mi)1,1,2|Cmax

算法3

問(wèn)題

P

|GoS

(

M

)

|C

的一個(gè)2-近似算法

3 算法近似比證明

3.1 等級(jí)約束為1、2、2 的3臺(tái)平行機(jī)

工件

J′

剛好出現(xiàn)在

M

上的情況，如圖1 所示。

Fig.1 Workpiece J′1 on machine M1圖1 工件J′1 在機(jī)器M1 上

Fig.2 Workpiece on machine M2圖2 工件在機(jī)器M2 上

Fig.3 Workpiece on machine M3圖3 工件 在機(jī)器M3 上

3.2 等級(jí)約束為1、1、2 的3臺(tái)平行機(jī)

Fig.4 General cases with level constraints of 1，1 and 2圖4 等級(jí)約束為1、1、2 的一般情況

4 結(jié)語(yǔ)

本文研究了具有等級(jí)約束的離線(xiàn)平行機(jī)排序問(wèn)題，目標(biāo)為最小化機(jī)器的最大完工時(shí)間。通過(guò)對(duì)LPT算法的深入研究，在該算法基礎(chǔ)上設(shè)計(jì)出新的算法，解決了3臺(tái)平行機(jī)上帶有2個(gè)服務(wù)等級(jí)的離線(xiàn)負(fù)載均衡問(wèn)題，并證明了近似比。但是本文只研究了3臺(tái)機(jī)器的情況，后續(xù)可以進(jìn)一步推廣到

m

臺(tái)機(jī)器。