李彥平，王 帥，趙 月

（沈陽(yáng)大學(xué) 科學(xué)技術(shù)研究中心，遼寧 沈陽(yáng) 110044）

流水車間調(diào)度問題在生產(chǎn)系統(tǒng)中被廣泛應(yīng)用.它是一類典型的NP難組合優(yōu)化問題，隨著生產(chǎn)任務(wù)的增加以及作業(yè)任務(wù)抵達(dá)時(shí)間的差異，都將會(huì)提高此類問題的求解難度［1］.由于此類問題存在普遍性及復(fù)雜性，所以研究流水車間調(diào)度問題具有非常重要的的理論意義和實(shí)用價(jià)值［2］.

流水車間調(diào)度問題可以理解為機(jī)器之間存在無限個(gè)緩沖區(qū)，但是在實(shí)際的生產(chǎn)中，由于工藝要求不同及作業(yè)空間設(shè)計(jì)受限制等，導(dǎo)致機(jī)器間存在的緩沖區(qū)往往是有限個(gè)，甚至是不存在的［3］.若機(jī)器間無緩沖區(qū)，當(dāng)任務(wù)n 在第k 個(gè)機(jī)器上完成加工時(shí)，且第k＋1個(gè)機(jī)器存在作業(yè)任務(wù)，此時(shí)任務(wù)n 將會(huì)被阻塞在第k 個(gè)機(jī)器上，直至第k＋1個(gè)機(jī)器可用，這類問題被稱為阻塞流水車間調(diào)度問題.

本文詳細(xì)研究了具有阻塞約束的流水車間調(diào)度問題，該問題的目標(biāo)函數(shù)為求解最小化完工時(shí)間之和.根據(jù)相關(guān)文獻(xiàn)可知，目前廣泛采用啟發(fā)式算法對(duì)此類問題進(jìn)行求解：文獻(xiàn)［4］提出了一種基于折衷策略對(duì)工件進(jìn)行初始排序的啟發(fā)式算法，并與NEH 算法進(jìn)行了比較，實(shí)驗(yàn)證明其提出的算法要優(yōu)于NEH 算法；文獻(xiàn)［5］設(shè)計(jì)了一種構(gòu)造啟發(fā)式算法，從減少下游工件的滯留時(shí)間入手產(chǎn)生工件的初始排序，結(jié)合有向圖中對(duì)關(guān)鍵路徑的分析，采用插入規(guī)則進(jìn)行搜索得到工件序列的近優(yōu)排序.通過與NEH 算法的比較，證明了所提算法的有效性；文獻(xiàn)［6］對(duì)PF、NEH 算法進(jìn)行改進(jìn)和組合，并結(jié)合插入鄰域搜索算法，提出了PFNEHLS、wFP-NEHLS、PW-NEHLS三種組合的啟發(fā)式方法，并利用這些方法解決阻塞流水車間調(diào)度問題，在Taillard的大規(guī)模問題上得到了較優(yōu)的解.

啟發(fā)式算法通用性強(qiáng)，容易實(shí)現(xiàn)，但是利用啟發(fā)式動(dòng)態(tài)規(guī)劃算法求解阻塞流水車間調(diào)度問題的研究相對(duì)較少.本文基于極大代數(shù)思想，針對(duì)阻塞流水車間特點(diǎn)建立了數(shù)學(xué)調(diào)度模型，同時(shí)采用啟發(fā)式動(dòng)態(tài)規(guī)劃算法進(jìn)行求解.文章針對(duì)具體生產(chǎn)加工實(shí)例進(jìn)行求解，通過與表3結(jié)果進(jìn)行比較可知，本文所提出的啟發(fā)式動(dòng)態(tài)規(guī)劃調(diào)度算法具有可行性.

1 阻塞流水車間調(diào)度模型

設(shè)：D＝（R＋∪ε，?，⊕）為極大代數(shù)，?為求和運(yùn)算，⊕為取大運(yùn)算；阻塞流水車間調(diào)度模型可表述為

式中：JN＝｛1，2，…，N｝為任務(wù)集，N為任務(wù)個(gè)數(shù)；In＝｛1，2，3，…，n｝為排序集，n≤N，n為被排序的任務(wù)個(gè)數(shù)；K＝｛1，2，…，m｝為機(jī)器集，m為機(jī)器數(shù)；t：JN×K ?D為任務(wù)加工時(shí)間函數(shù)；t（j，k）表示任務(wù)j∈J 在機(jī)器k 上所需的加工時(shí)間；r：JN?D為任務(wù)到達(dá)時(shí)間函數(shù)；r（j）表示任務(wù)j∈J的到達(dá)時(shí)間或者稱為準(zhǔn)備就緒最早時(shí)間；x：JN×K ?D為任務(wù)開始加工時(shí)間函數(shù)；x（j，k）表示任務(wù)j∈J 在機(jī)器k 上的最早開工時(shí)間；c：JN×K ?D為任務(wù)完成加工時(shí)間函數(shù)；c（j，k）：任務(wù)j∈J 在機(jī)器k 上的最早完工時(shí)間，s：In?JN為任務(wù)排序函數(shù)，s（i）≠s（i′），i≠i′；s（i）表示第i個(gè)被加工的任務(wù).

模型（1）表述出了不同任務(wù)在不同機(jī)器上的開始加工時(shí)間，模型（2）是在此基礎(chǔ)上加入各自的加工時(shí)間所求得其相應(yīng)的完工時(shí)間.模型中的m＋1表示任務(wù)完工后的停留區(qū)域，x（s（i），m＋1）表示第i個(gè)被加工任務(wù)完成的時(shí)間.這里，任務(wù)排序函數(shù)s 給出了一種任務(wù)的排序方式，s（i）∈J表示第i個(gè)被加工的任務(wù)，（s（1），s（2），s（3），…，s（n））表示按序加工的任務(wù)列.

可以證明，模型（1）存在如下不等式關(guān)系

為此若補(bǔ)充定義s（0）?0，x（0，k）?ε，x（j，0）?ε，則模型（1）可簡(jiǎn)化為如下形式：

通過遞推可知：

模型（4）與（5）分別表示出第i個(gè)被加工任務(wù)在機(jī)器m 上的開始加工時(shí)間和完工時(shí)間，模型中涉及到第i個(gè)被加工任務(wù)的各時(shí)間參數(shù)與其前一個(gè)被加工任務(wù)在各個(gè)機(jī)器上的開始加工時(shí)間，換句話說，第i個(gè)被加工任務(wù)在第m 臺(tái)機(jī)器上的完工時(shí)間，只與其前一個(gè)任務(wù)調(diào)度有關(guān).

2 阻塞流水車間啟發(fā)式動(dòng)態(tài)規(guī)劃調(diào)度算法

如果考慮完工時(shí)間之和最小，阻塞流水車間最優(yōu)調(diào)度可以描述為

這里簡(jiǎn)稱其為Qn（s）問題.

為便于問題的求解，引入任務(wù)集J（i）＝JN／｛s（1），s（2），…，s（i）｝，i∈In.顯然有

其中，J（0）＝JN.

定義1 稱｛s＊（1），s＊（2），…，s＊（n）｝為Qn（s）問題的一個(gè)次優(yōu)解，如果其滿足：

式中，J（n）＝JN／｛s＊（1），s＊（2），…，s＊（n-1）｝.

定義2 稱｛s＊（1），s＊（2），…，s＊（n）｝為Qn（s）問題的一個(gè)滿意解，如果?i∈In，滿足

式中，J（i）＝JN／｛s＊（1），s＊（2），…，s＊（i-1）｝.

基于以上定義，可以給出如下阻塞流水車間啟發(fā)式動(dòng)態(tài)規(guī)劃調(diào)度算法：

其中，J（0）＝JN，｛s＊（0）｝＝?.

3 計(jì)算實(shí)例分析

為檢驗(yàn)算法的有效性，這里給出一個(gè)有4個(gè)任務(wù)4臺(tái)機(jī)器的阻塞流水車間調(diào)度問題的例子，表1為各任務(wù)在每臺(tái)機(jī)器上的加工時(shí)間參數(shù)表.表2為啟發(fā)式動(dòng)態(tài)規(guī)劃調(diào)度算法形成的一組調(diào)度計(jì)算表，分步驟地將問題中的4個(gè)任務(wù)進(jìn)行對(duì)比計(jì)算，得出任務(wù)的優(yōu)化排序與完工時(shí)間之和，表3將表2得出的結(jié)果與其他排序得出的結(jié)果進(jìn)行對(duì)比，利用啟發(fā)式動(dòng)態(tài)規(guī)劃調(diào)度算法求出的排序所得的任務(wù)完工時(shí)間之和為這個(gè)值小于表中另外兩組排序所得的結(jié)果，可見算法十分有效.優(yōu)化排序后對(duì)應(yīng)的甘特圖如圖1所示.由甘特圖分析可知，任務(wù)在各臺(tái)機(jī)器上的加工時(shí)間連續(xù)，各臺(tái)機(jī)器的空閑時(shí)間較短，整條流水線的生產(chǎn)作業(yè)比較順暢，表明阻塞流水車間啟發(fā)式動(dòng)態(tài)規(guī)劃調(diào)度算法能夠求出較好的近優(yōu)解，算法所得出的結(jié)果是比較合理的.

表1 任務(wù)的加工時(shí)間參數(shù)表Table 1 The processing time parameter table of task

表2 啟發(fā)式動(dòng)態(tài)規(guī)劃調(diào)度表Table 2 The schedule of heuristic dynamic programming

表3 不同排序的對(duì)比結(jié)果Table 3 The results of different sort

圖1 阻塞流水車間調(diào)度甘特圖Fig.1 Thescheduling Gantt chart of blocking flow shop

4 結(jié) 論

本文以阻塞流水車間調(diào)度問題為研究背景，以極大代數(shù)（dioid）思想為出發(fā)點(diǎn)，從另一角度給出了阻塞流水車間的排序函數(shù)與調(diào)度模型，并用啟發(fā)式動(dòng)態(tài)規(guī)劃算法解決了此類問題.實(shí)驗(yàn)結(jié)果表明，文章采用啟發(fā)式動(dòng)態(tài)規(guī)劃算法得到的排序結(jié)果優(yōu)于表3中其他排序的結(jié)果.因此，本文所研究的啟發(fā)式動(dòng)態(tài)規(guī)劃算法具有較好的可行性.

［1］謝謝，李彥平.帶有單服務(wù)器的并行機(jī)調(diào)度問題［J］.沈陽(yáng)大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，24（4）：66-69.（Xie Xie，LI Yanping.Scheduling Parallel Machines with a Single Server［J］.Journal of Shenyang University：Natural Science，2012，24（4）：66-69.）

［2］Celia A G，Hans K.Parallel Machine Scheduling with Job Assignment Restrictions［J］.Naval Research Logistics，2007，54（3）：250-257.

［3］陳露，奚立峰，蔡建國(guó)，等.一種求解帶有阻塞限制的混合流水車間的禁忌搜索算法［J］.上海交通大學(xué)學(xué)報(bào)，2006，40（5）：856-859.（Chen Lu，Xi Lifeng，Cai Jianguo，et al.A Tabu Search Algorithm for Hybrid Flow Shop Problem with Blocking Constraint［J］.Journal of Shanghai Jiaotong University，2006，40（5）：856-859.）

［4］洪宗友，龐哈利.基于折衷策略的Blocking流水車間調(diào)度構(gòu)造啟發(fā)式算法［J］.系統(tǒng)工程理論與實(shí)踐，2008，28（10）：114-118.（Hong Zhongyou，Pang Hali.Study on a Constructive Heuristic Algorithm based on Compromise Policy for Blocking Flow-shop Scheduling［J］.Systems Engineering-Theory ＆Practice，2008，28（10）：114-118.）

［5］洪宗友，閆萍，龐哈利.Blocking流水車間調(diào)度問題的MBT算法研究［J］.遼寧師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，30（2）：148-151.（Hong Zhongyou，Yan Ping，Pang Hali.Study on Minimum Blocked Time Algorithm for Blocking Flow-shop Scheduling［J］.Journal of Liaoning Normal University：Natural Science Edition，2007，30（2）：148-151.）

［6］Pan Q K，Wang L.Effective Heuristics for the Blocking Flow Shop Scheduling Problem with Makespan Minimization ［J］.Omega-International Journal of Management Science，2012，40（2）：218-229.