云制造環(huán)境下資源受限的同類機調(diào)度問題

，，

(浙江理工大學(xué)理學(xué)院，杭州 310018)

0 引 言

云制造(Cloud manufacturing)是一種新型制造模式，能夠把分散的資源整合在一起，然后經(jīng)過虛擬化實時發(fā)布資源的利用狀態(tài)，實現(xiàn)資源共享，提高資源的利用率。因此云制造對于我國的經(jīng)濟發(fā)展有著深遠(yuǎn)的意義。本文主要研究了在云制造背景下資源受限的同類平行機調(diào)度問題。機器的所有者通過云制造平臺把機器的現(xiàn)有狀態(tài)包括租用成本、加工速度、機器的使用情況進行虛擬化發(fā)布。生產(chǎn)方通過云制造平臺獲知機器的現(xiàn)有狀態(tài)，根據(jù)自己的成本預(yù)算選擇最適合自己的機器，并安排工件加工。

本文考慮以下問題：每臺機器都有一個加工速度和租用的固定成本，其中固定成本不隨加工時間變化而變化，生產(chǎn)方的成本預(yù)算(資源)是一個固定常數(shù)；目標(biāo)是在給定的成本預(yù)算情形下，租用相應(yīng)的機器并加工工件使得最大完工時間(Makespan)最小。

本文考慮文獻[13]所提問題的兩種更一般的情況。第一種情況假設(shè)工件的長度不完全相同，機器速度越大，其單位成本速度也越大；第二種情況中工件的長度相同但對機器沒有要求。本文分別對上述兩種情形給出了近似算法及其最壞情況界。

1 符號定義

本文引入以下符號。

m：云制造平臺提供的的機器數(shù)；

n:云制造平臺得到的需要加工的工件數(shù)，n≥m；

M={Mi|i=1,2,…,m}：云制造平臺提供的機器集合；

J={Jj|j=1,2,…,n}：云制造得到的需要加工的工件集合；

pj：工件Jj的長度；

si：機器Mi的加工速度，即單位時間加工的工件長度；

Ki:機器Mi的加工成本；

U:機器加工工件需要的總成本；

Li：機器Mi的負(fù)載；

Cmax(A):算法A的目標(biāo)函數(shù)值(makespan)；

Cmax(opt)：最優(yōu)調(diào)度的makespan。

2 工件長度不同的同類機調(diào)度問題

算法A1：

1) 令U=0,h=0,M′=?,i=1.

3)i++，若i≤m,返回第2步；否則進行到下一步。

5) 令a=M′，選擇的機器集合M′={M1,M2,…,Mh-1}∪{Mj1,Mj2,…,Mjk}，其中k+h-1=a且jk>jk-1>…j1>h。

6) 把工件按照其加工時間從大到小進行排序即p1≥p2≥…≥pn。

7) 令j=1;ti=0，Li=?.

9) 若j≤n,則返回第上一步；否則,停止。

證明：(ⅰ) 令Γ表示前h臺機器的集合，即Γ={M1,M2,…,Mh}。設(shè)M*表示最優(yōu)排序中機器的集合，根據(jù)假設(shè)可以得到

化簡可得

Cmax(A1)s[i]≤C[i]s[i]+pn。

由此可得

因此

證明：由引理1可知

化簡可得

3 工件長度相同的同類機調(diào)度問題

算法A2：

2) 令U=0,h=0,B=?,i=1。

4)i=i+1，若i≤m,則返回第3步；否則進行到下一步。

6) 令b=B,選擇的機器B={M1,M2,…,Mh-1}∪{Mj1,Mj2,…,Mjk}，其中k+h-1=b且jk′>jk-1′>…>j1′>h。

7) 令j=1;ti=0，Li=?。

9) 若j≤n,則返回第上一步；否則，停止。

化簡可得

Cmax(A2)s[i]≤C[i]s[i]+p。

由此可得

≤(n+b-1)p。

即

證明：由引理2可知

算法A2選擇的機器數(shù)為b，且b≤m-1。結(jié)合n≥m可得

4 結(jié) 論

[1] 李伯虎,張霖,王時龍,等.云制造:面向服務(wù)的網(wǎng)絡(luò)化制造新模式[J].計算機集成制造系統(tǒng),2010,16(1):1-7.

[2] 李伯虎,張霖,任磊,等.再論云制造[J].計算機集成制造系統(tǒng),2011,17(3):449-457.

[3] 李伯虎,張霖,任磊,等.云制造典型特征、關(guān)鍵技術(shù)與應(yīng)用[J].計算機集成制造系統(tǒng),2012,18(7):1345-1356.

[4] Noga J. Scheduling with machine cost[C]//International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques. Springer-Verlag,1999:168-176.

[5] Imreh C. Online scheduling with general machine cost functions[J]. Electronic Notes in Discrete Mathematics,2006,27(9):49-50.

[6] Jiang Y W, He Y. Preemptive online algorithms for scheduling with machine cost[J]. Acta Informatica,2005,41(6):315-340.

[7] Dosa G, Tan Z Y. New upper and lower bounds for on line scheduling with machine cost[J]. Discrete Optimization,2010,7(3):125-135.

[8] Rustogi K, Strusevich A V. Parallel machine scheduling: Impact of adding extra machines[J]. Operations Research,61(5):1243-1257.

[9] Jiang Y W, He Y. Semi-Online Algorithms for scheduling with machine cost[J]. Journal of Computer Science and Technology,2006,21(6):984-988.

[10] He C, Leung YT, Lee K, et al. Scheduling a single machine with parallel batching to minimize makespan and total rejection cost[J]. Discrete Applied Mathematics,2016,204(C):150-163.

[11] Lee K, Leung YT, Jia Z H, et al. Fast approximation algorithms for bi-criteria scheduling with machine assignment costs[J]. European Journal of Operational Research,2014,238(1):54-64.

[12] Li K, Zhang X, Leung YT, et al. Parallel machine scheduling problems in green manufacturing industry[J]. Journal of Manufacturing Systems,2016,38:98-106.

[13] Li K, Zhang H J, Cheng B Y, et al. Uniform parallel machine scheduling problems with fixed machine cost[J/OL]. Optimization Letters,2016[2017-09-08]. https://doi.org/10.1007/s11590-016-1096-3.

[14] Horowitz E, Sahni S, Sahni, S. Computing partitions with applications to the knapsack problem[J]. Journal of the Acm,1974,21(2):277-292.