3臺平行機上帶有2個服務等級的離線負載均衡

賈珊珊，嵇雯蕙，陳智斌

（昆明理工大學 理學院，云南 昆明 650500）

0 引言

排序問題描述如下：若干個工件要在一些機器上進行加工，如何安排機器和工件使某些要求（目標函數）達到最優。一個排序問題可以用三元組

α

|

β

|

γ

來描述，其中

α

域描述機器環境，

β

域提供加工特征和約束細節，

γ

域描述最小化或最大化的目標函數。對于平行機排序問題，

α

域用

P

表示，

β

域可能包括多項，如提交日期、機器適用約束等；

γ

域一般采用最大完工時間

C

等作為目標函數。經典的平行機排序問題（Multiprocessor Scheduling，MS）問題可表示為

P||C

。根據實際情況研究人員相繼提出了帶懲罰費用的排序問題

P|rej|C

和帶等級約束的排序問題

P|GoS|C

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

P|GoS|C

）。當所有任務的服務等級都相同，并且任務的服務等級都大于等于機器的服務等級時，本文討論的問題就變成了經典的平行機排序問題

P||C

，所以本文討論的問題仍然是強NP-難的問題。

1 符號說明及問題描述

1.1 符號說明

部分符號說明如下：

T

：所有工件的加工時間總和

S

、

S

：等級為1、等級為2 的工件集合

n

、

n

：等級為1、等級為2 的工件個數

D

：多出部分的工件集

1.2 帶服務等級的負載均衡問題（P|GoS|Cmax）

本文考慮服務等級負載均衡問題的一種特殊情況，3臺機器兩個等級約束的負載均衡問題（

P

|GoS

|C

）。顯然，該問題可分為以下4 種情況進行討論：情況（1）：當

g

(

M

)=

g

(

M

)=

g

(

M

)=1，

g

(

J

)=1或2時，所有工件都可放在這3臺機器上加工，等同于經典平行機排序問題。情況（2）：當

g

(

M

)=

g

(

M

)=

g

(

M

)=2，

g

(

J

)=1或2時，只考慮

g

(

J

)=2 的工件，等同于經典平行機排序問題。情況（3）：當

g

(

M

)=1，

g

(

M

)=

g

(

M

)=2 且

g

(

J

)=1或2 時，記該問題為

P

|GoS

(

M

)

|C

。情況（4）：當

g

(

M

)=

g

(

M

)=1，

g

(

M

)=2 且

g

(

J

)=1或2 時，記該問題為

P

|GoS

(

M

)

|C

。

2 算法說明

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

算法1

最小時間跨度排序

將工件按照加工時間從大到小進行排序

按照這個次序在機器上對工件排序，將工件放在當前負載最小的機器上

下面圍繞情況（3）和情況（4）展開，并針對這兩種情況設計近似算法。

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

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

算法3

問題

P

|GoS

(

M

)

|C

的一個2-近似算法

3 算法近似比證明

3.1 等級約束為1、2、2 的3臺平行機

工件

J′

剛好出現在

M

上的情況，如圖1 所示。

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

Fig.2 Workpiece on machine M2圖2 工件在機器M2 上

Fig.3 Workpiece on machine M3圖3 工件 在機器M3 上

3.2 等級約束為1、1、2 的3臺平行機

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

4 結語

本文研究了具有等級約束的離線平行機排序問題，目標為最小化機器的最大完工時間。通過對LPT算法的深入研究，在該算法基礎上設計出新的算法，解決了3臺平行機上帶有2個服務等級的離線負載均衡問題，并證明了近似比。但是本文只研究了3臺機器的情況，后續可以進一步推廣到

m

臺機器。