趙金霞，沈 灝

(1.杭州電子科技大學電子信息學院，浙江杭州310018;2.杭州電子科技大學理學院，浙江 杭州310018)

0 引言

在調(diào)度問題中，Johnson算法成功地解決了 Flow Shop問題中的 n/m/F/Fmax(m=2)問題，而n/m/F/Fmax(m＞2)就是一個NP難題［1］，對此，有CDS以及用斜度指標排列作業(yè)的Palmer等啟發(fā)式算法［2，3］。除了啟發(fā)式算法，許多人也研究了用模擬退火算法和遺傳算法等搜索技術(shù)來求解流水線調(diào)度問題，并取得了一定成果［4，5］。最新的求解方法有改進量子遺傳算法和基于分布估計算法［6，7］。對于n項任務(wù)，兩道工序，每道工序由若干臺平行機組成，目標為makespan最小化的調(diào)度問題，要將n!次排列全部收索完畢才能得到最優(yōu)解，隨著n的增加，復雜度劇增。本文提出的Johnson序結(jié)合自然序的快速算法，既能提高求解效率，又能在盡量滿足先到先服務(wù)規(guī)則的前提下達到客戶要求。

1 問題描述

有一屬于典型的同序流水作業(yè)調(diào)度問題的具體實例:某工廠要盡快趕出140項任務(wù)，其中工序1加工車間和工序2加工車間關(guān)于每項任務(wù)所需要的時間如表1所示，其中只列出6項，其余各項均省略。工序1加工車間共有12臺平行機，工序2加工車間共有3臺平行機，各車間按j1，j2，…，j140的自然順序工作時，計算每個jk的開工時間和完工時間;若工廠希望整批任務(wù)能夠盡早完工，以提高生產(chǎn)效率，又要盡量保證客戶滿意度，應如何安排任務(wù)的先后加工順序，才能使完成所有任務(wù)的總工期最短。

表1 140項任務(wù)兩道工序時間表

2 流水作業(yè)模型的建立及求解

2.1 模型假設(shè)

(1)每個任務(wù)的每道工序只在一臺設(shè)備上完成，不能同時在幾臺不同的設(shè)備上加工，且加工過程中不能中斷。

(2)每道工序完成后即可排到下一道工序隊列里加工，不考慮兩道工序中間的搬運等時間，也不考慮機器的調(diào)整時間。

(3)任務(wù)數(shù)、設(shè)備數(shù)和加工時間已知，加工時間與加工順序無關(guān)。

(4)每臺設(shè)備只能同時加工一項任務(wù)，每項任務(wù)前一道工序完成后才能進行下一道工序。

2.2 自然順序下調(diào)度模型

由于要按照產(chǎn)品編號順序進行加工，本文根據(jù)各項任務(wù)工序1的完成順序得到工序2的加工順序，同時考慮到工序2的平行機可能有空閑問題，編程計算得到各工序開始時間與結(jié)束時間，最終這140項任務(wù)在自然順序下的總完工時間為236。

自然順序下的算法思想如下:

(1)按照自然順序，每一項任務(wù)都是先加工工序1再加工工序2，一臺工序1平行機加工完，就對下一項任務(wù)進行加工;把完成工序1的任務(wù)依次放到一個隊列里，如果工序2的平行機有空閑，就把隊列里存著的任務(wù)拿出來加工;

(2)每臺工序1平行機或工序2平行機上的后一項任務(wù)開工時間=前一項任務(wù)完工時間，即T后－項－項=T前－項－項;

(3)每項任務(wù)的工序1完工時間=此項任務(wù)工序1開工時間+此項任務(wù)所需工序1加工時間，即T工序1完工=T工序1開始+T工序1;

(4)每項任務(wù)的工序2完工時間=此項任務(wù)工序2開工時間+此項任務(wù)所需工序2加工時間，即T工序2完工=T工序2開始+T工序2;

(5)自然順序下每一項任務(wù)的工序2開工時間=此項任務(wù)工序1完工時間+等待時間，即T工序2開始=T工序1完工+T等待，若工序2平行機有空閑，則等待時間為0。

2.3 Johnson序結(jié)合自然序的混合調(diào)度算法

2.3.1 算法設(shè)計

根據(jù)實際問題確定一個常數(shù)T，在自然順序中截取一段總加工時長不超過T但盡量接近T的幾個連續(xù)任務(wù)成為一個小組，組內(nèi)工件應用Johnson序，但是組間工件采用先到先服務(wù)原則的自然序。T可根據(jù)不同廠商的實際情況選取，比如取平行機總數(shù)，或者工序1設(shè)備總數(shù)等。由于Johnson算法得到的是總加工時長最短序，可知混合算法在組內(nèi)加工時長最短，所以總加工時長必然小于或等于純自然序下的總加工時長。

設(shè)符號jk為任務(wù)k，k=1，2，…，n;P1k為第k個任務(wù)的第一道工序加工時間;P2k為第k個任務(wù)的第二道工序加工時間;Mi為第i臺機器，i=1，2，…，m。

(1)工件集分成兩個不交子集J1和J2，其中J1={jk|P1k＜P2k}，J2={jk|P1k＞P2k}，滿足P1k=P2k的工件可以分在兩個子集中的任何一個。

(2)先將J1中的工件按P1k的非降序排序，再將J2中工件按P2k的非增序排序。

設(shè)機器M1上的第一個工件的開工時間為t=0，工件的加工順序為j1，j2，…，jn，則第k個工件jk在機器Mi上的完工時間可以用以下遞推公式計算［1］:

2.3.2 Johnson算法結(jié)合自然序求解

(1)用MATLAB編程將140項任務(wù)分成兩個子集合:工序1加工時間小于或等于工序2加工時間的任務(wù)集合J1={j1k}，工序1加工時間大于工序2加工時間的任務(wù)集合J2={j2k}，并將J1整理成關(guān)于工序1 加工時間的非降序，k 依次為:43，57，4，...，102，32，27，共 36 項;J2整理成關(guān)于工序 2 加工時間的非增序，k 依次為:41，111，133，...，68，105，116，共 104 項。

(2)先加工J1中的任務(wù)，后加工J2中的任務(wù)，即得總工期最短的加工順序Jk。

(3)把Jk帶入到自然順序的程序中去，得到每項任務(wù)由12臺工序1平行機和3臺工序2平行機加工時的各自開始時間與結(jié)束時間，最終這140項任務(wù)在Johnson算法結(jié)合自然序求解下的總完工時間為229，比單純的自然順序下的總完工時間短。

2.4 實例驗證

在實際生產(chǎn)中，任務(wù)集的給出具有很大的隨機性，而且考慮到顧客的滿意度問題，廠家要盡量保證顧客按先到先服務(wù)的自然順序完成任務(wù)，所以用計算機隨機模擬出3種任務(wù)集(假設(shè)有10項任務(wù)，4臺工序1平行機，1臺工序2平行機)，即工序1時間非遞增工序2時間非遞減序列、工序1時間非遞減工序2時間非遞增序列、工序1時間和工序2時間均服從泊松分布的3種序列，分別如表2－4所示，以此舉例驗證Johnson序結(jié)合自然序混合型算法在許多實際問題中具有一定的應用價值。

表2 工序1時間非遞增工序2時間非遞減任務(wù)集 (h)

表3 工序1時間非遞減工序2時間非遞增任務(wù)集 (h)

表4 工序1時間和工序2時間均服從泊松分布任務(wù)集 (h)

表3的情況下，自然順序和混合型算法下的完工時間相同，因為J1恰好是關(guān)于工序1時間的非降序，J2恰好是關(guān)于工序2時間的非增序，和此情況下的自然順序一樣，故結(jié)果相同。

由于顧客流一般服從泊松分布，所以模擬得工序1時間和工序2時間均服從泊松分布的任務(wù)集。

從以上3個例子可以看出Johnson序結(jié)合自然序的混合型算法優(yōu)于純自然序。

3 結(jié)束語

Johnson算法的特點是求得總加工時長最短序，但實際生產(chǎn)中，這樣可能會造成先到任務(wù)延期太長而不能被客戶接受的情況，而混合算法既體現(xiàn)了Johnson算法總加工時長最短的優(yōu)點，又可以避免此種情況的發(fā)生，可見Johnson序結(jié)合自然序的混合型算法具有很強的實踐可行性。

［1］ 陳光亭，裘哲勇.數(shù)學建模［M］.北京:高等教育出版社，2010:60－61.

［2］ Dudek R A，Panwalker S S，Smith M L.The lessons of Flowshop scheduling research［J］.Operations Research，1992，40(1):42－46.

［3］ Palmer D S.Sequencing jobs through a multi-stage process in the minimum total time-A quick method of obtaining a near optimum［J］.Operations Research Quart-erly，1965，16(1):101 － 107.

［4］ 田彭，楊自厚.同順序排序問題的模擬退火求解［J］.信息與控制，1994，23(3):133－139.

［5］ 熊紅云，何鉞.模糊Flow－shop問題及其遺傳優(yōu)化［J］.信息與控制，1999，28(1):8－13.

［6］ 王興林，李茂軍.基于改進量子遺傳算法的Flow－Shop調(diào)度求解［J］.計算技術(shù)與自動化，2010，29(3):82－85.

［7］ 葉寶林，高慧敏，王筱萍，等.基于分布估計算法的二階段置換流水車間調(diào)度算法［J］.計算機應用研究，2011，28(10):3 702－3 706.