一類固定工件排序問題算法研究

□汪 瑜 孫 宏 [中國(guó)民航飛行學(xué)院 廣漢 618307]

一類固定工件排序問題算法研究

□汪 瑜 孫 宏 [中國(guó)民航飛行學(xué)院 廣漢 618307]

針對(duì)一類“可用機(jī)器數(shù)有限,存在機(jī)器與工件間匹配約束,以機(jī)器-工件分配成本最小為目標(biāo)”的固定工件排序問題，以固定工件的開始時(shí)刻、結(jié)束時(shí)刻為基準(zhǔn)構(gòu)建網(wǎng)絡(luò)時(shí)序圖，將“機(jī)器-工件”分配過程看成網(wǎng)絡(luò)時(shí)序圖中的網(wǎng)絡(luò)流問題，并設(shè)計(jì)排序問題的模擬退火算法。通過算例發(fā)現(xiàn)：算法平均CPU時(shí)間為32.9秒，總成本最大誤差為0.07%，時(shí)間復(fù)雜度為O(M(m3+ mn))，空間復(fù)雜度為O(m2n)。結(jié)果表明：算法為多項(xiàng)式算法，且可行。

固定工件排序；網(wǎng)絡(luò)時(shí)序圖；模擬退火；多項(xiàng)式算法

引 言

固定工件排序問題是指對(duì)擁有明確加工時(shí)間的若干待加工工件，將其按照一定的加工順序分配給機(jī)器加工，實(shí)現(xiàn)最小化工件的最大完工時(shí)間。而作為一類特殊的固定工件排序問題，即有機(jī)器數(shù)目限制，開始時(shí)刻與結(jié)束時(shí)刻明確，存在“機(jī)器-工件”約束關(guān)系的問題同樣在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和軍事方面有著廣泛的應(yīng)用背景：如在學(xué)校課程表的制定過程中，所有的待授課程（即固定工件）有著明確的開始時(shí)刻與結(jié)束時(shí)刻，而教室（即機(jī)器）數(shù)目是有一定限制的，并存在待授課程的學(xué)生數(shù)目與教室可容納人數(shù)之間的限制問題，要求合理安排待授課程與教室之間的關(guān)系；又如航空公司飛機(jī)調(diào)度問題，在已有的航班計(jì)劃基礎(chǔ)上，航班（即固定工件）的起飛時(shí)刻與結(jié)束時(shí)刻等因素明確，待使用飛機(jī)（即機(jī)器）數(shù)目有限，另外航班上的旅客人數(shù)與飛機(jī)最大容量之間存在著一定的約束，要求合理的將飛機(jī)分配安排到航班上；又如企業(yè)人員調(diào)配問題中，在工作計(jì)劃中合理的選擇做事順序，以及鐵路運(yùn)輸中的調(diào)機(jī)分配問題等均可歸入到此類固定工件的排序問題之中，甚至宇宙飛船復(fù)雜龐大的飛行計(jì)劃編排,都要用到上述的排序理論和算法。顯然此類排序算法對(duì)解決自然界與社會(huì)中存在的問題有著巨大的現(xiàn)實(shí)意義。然而根據(jù)現(xiàn)有的研究成果發(fā)現(xiàn)，這種“有機(jī)器數(shù)目限制，開始時(shí)刻與結(jié)束時(shí)刻明確，存在“機(jī)器-工件”約束關(guān)系，以加工的總成本最小為目標(biāo)”的固定工件排序問題是NP-Complete（NPC）[1]問題且不存在好的多項(xiàng)式算法，為此尋找好的啟發(fā)式算法成為了解決這類問題的關(guān)鍵。

最早提出此類固定工件排序問題啟發(fā)式算法的U.I.GUPTA設(shè)計(jì)了一種求解該類問題的貪婪算法并解決了電路線路安排問題[2]，隨后M.Fischetti在U.I.GUPTA的基礎(chǔ)上，進(jìn)一步研究了公共汽車司機(jī)的排班問題[3～5]，K.Jansen的航空公司飛機(jī)維護(hù)人員排班問題以及V.Gabrel的地球觀測(cè)衛(wèi)星軌道選擇問題等均使用了貪婪算法[6～7]，Qiwei Huang等人設(shè)計(jì)了一種考慮不同類型機(jī)器加工工件成本不同的算法，該算法認(rèn)為加工時(shí)間與加工成本呈線性關(guān)系，并指出在僅有2種機(jī)器類型時(shí)設(shè)計(jì)的近似算法為多項(xiàng)式算法，超出2種類型時(shí)仍為NPC問題[8]。對(duì)于此類特殊的固定工件排序問題，國(guó)內(nèi)的洪文等人通過將數(shù)學(xué)模型與數(shù)據(jù)分離的形式進(jìn)行了研究，并用LINGO軟件給出了一種實(shí)用算法[9]，孫宏等人按照固定工件加工開始、結(jié)束時(shí)刻構(gòu)造了工件時(shí)序網(wǎng)絡(luò)模型，并將固定工件排序問題轉(zhuǎn)化為網(wǎng)絡(luò)流模型[10]。

然而，“有機(jī)器數(shù)目限制，開始時(shí)刻與結(jié)束時(shí)刻明確，存在“機(jī)器-工件”約束關(guān)系，以加工的總成本最小為目標(biāo)”的固定工件排序問題現(xiàn)有的研究成果并沒有考慮到機(jī)器資源限制，且給出有效的多項(xiàng)式算法，因此并不能很好地應(yīng)用到現(xiàn)實(shí)問題中。本文首先通過構(gòu)造以固定工件時(shí)刻為基礎(chǔ)的網(wǎng)絡(luò)時(shí)序圖，并以此得出基準(zhǔn)的機(jī)器資源限制，隨后以時(shí)序網(wǎng)絡(luò)模型的路徑分配成本最小為目標(biāo)函數(shù)設(shè)計(jì)基于模擬退火的啟發(fā)式算法并給出復(fù)雜度公式，最后通過算例對(duì)算法進(jìn)行分析。

一、算法設(shè)計(jì)

（一）算法原理

在此類固定工件排序問題中，每個(gè)工件將被分配到不同的機(jī)器上進(jìn)行加工作業(yè)，目標(biāo)是求出所有工件的加工方案使得完成全部加工的總成本最小。對(duì)于每一個(gè)工件來(lái)說，它要在不同的機(jī)器上進(jìn)行加工，且不同的機(jī)器加工同樣工件的成本不同。雖然我們無(wú)論如何都可以求出工件的加工方案，但是如果安排不當(dāng)就會(huì)出現(xiàn)工件在加工成本較高的機(jī)器上加工導(dǎo)致成本上升，這樣就會(huì)使得完成全部工件加工的總成本較大。由于工件加工時(shí)間具有先后順序，因此這使得工件排序問題變得更加復(fù)雜。首先通過建立描述固定工件時(shí)序關(guān)系的工件網(wǎng)絡(luò)時(shí)序模型來(lái)確定工件之間加工的先后順序，然后再將機(jī)器分配到由網(wǎng)絡(luò)時(shí)序圖所構(gòu)造的有向路徑上，即將固定工件排序問題轉(zhuǎn)化為尋找工件網(wǎng)絡(luò)模型的最優(yōu)有向路分解問題，并以時(shí)序網(wǎng)絡(luò)模型的路徑分配成本最小為目標(biāo)函數(shù)，構(gòu)造了一種基于模擬退火的啟發(fā)式算法。具體來(lái)說：

第一步：構(gòu)造工件的網(wǎng)絡(luò)時(shí)序圖。根據(jù)所有“待加工工件”加工的開始時(shí)刻、結(jié)束時(shí)刻，以“連續(xù)的結(jié)束時(shí)刻與緊隨其后的連續(xù)開始時(shí)刻看成一個(gè)節(jié)點(diǎn)(階段)”的原則，將所有的“時(shí)刻”歸入不同的節(jié)點(diǎn)(階段)中，并以每一個(gè)待加工工件的開始時(shí)刻和結(jié)束時(shí)刻所在的節(jié)點(diǎn)以有向弧連接，將節(jié)點(diǎn)總數(shù)記為t。檢查除起點(diǎn)與終點(diǎn)以外的任一節(jié)點(diǎn)vi(i=2，3…t-1)，記其出度與入度之差為k。若k〈0，則連接vj到vj+1(j=1，2…i-1)共k條虛??；若t〉0，則連接vj到vj+1共k條虛弧。以此保證節(jié)點(diǎn)vi(i=2，3…t-1)出、入度相等；

第二步：有向路徑的分解方案。根據(jù)第一步生成的網(wǎng)絡(luò)時(shí)序圖，可以得出圖的最大割，記為z，生成z條均以第一個(gè)節(jié)點(diǎn)開始、最后一個(gè)節(jié)點(diǎn)為終點(diǎn)，包含不同“弧”的有向路徑；

第三步：構(gòu)造評(píng)估函數(shù)。根據(jù)第二步中的有向路徑分解方法，將可供選擇的“機(jī)器”數(shù)，記為n，分配給z條有向路徑。顯然不同的“機(jī)器”加工不同的“有向路徑”的成本是不同的，尋找最優(yōu)的“機(jī)器-有向路徑”分配方案。并將每一個(gè)“機(jī)器”數(shù)量累計(jì)，得出所需的“機(jī)器”與其對(duì)應(yīng)的數(shù)量；

第四步：利用模擬退火設(shè)計(jì)啟發(fā)式算法。將有向路徑的分解方案看成“狀態(tài)”，將最優(yōu)的“機(jī)器-有向路徑”分配成本看成評(píng)估函數(shù)。通過隨機(jī)生成不同的“狀態(tài)”以及得到不同的評(píng)估函數(shù)值，不斷的轉(zhuǎn)移“狀態(tài)”(退火)，在達(dá)到算法的終止準(zhǔn)則時(shí)，停止“狀態(tài)”的轉(zhuǎn)移并得出最佳方案。

對(duì)于算法的詳細(xì)過程，可參考文獻(xiàn)11，12。

（二）參數(shù)選取

上述基于模擬退火算法的參數(shù)主要包括了初始溫度t0，算法終止溫度tf，溫度最大下降次數(shù)Mmax以及最優(yōu)解保持次數(shù)Ccount。為了保證算法穩(wěn)定的收斂，對(duì)參數(shù)進(jìn)行仿真分析。按照起始溫度應(yīng)能保證平穩(wěn)分布中每一狀態(tài)的概率相等的原則，算法選取的終止溫度為tf=10，初始溫度t0=Kδ，K是一個(gè)充分大的數(shù)，δ={max{cij}-min{cij}}z，其中max{cij}所形成的“候選機(jī)型-有向路徑”最大成本函數(shù)值；min{cij}表示所形成的“候選機(jī)型-有向路徑”最小成本函數(shù)值；z表示有向路徑數(shù)[11]。圖1、圖2是在操作系統(tǒng)Windows Vista， MATLAB7.0環(huán)境下，內(nèi)存1G，CPU主頻1.83GHz，硬盤空間80G下分別對(duì)溫度最大下降次數(shù)Mmax與最優(yōu)解保持次數(shù)Ccount的仿真實(shí)驗(yàn)，從圖1中可以看出，對(duì)于“5架機(jī)器，33個(gè)固定工件”問題溫度最大下降次數(shù)Mmax在達(dá)到60000次后對(duì)于最優(yōu)解的影響已經(jīng)趨于穩(wěn)定，而對(duì)于“10架機(jī)器，68個(gè)固定工件”問題溫度最大下降次數(shù)Mmax在達(dá)到90000次后對(duì)于最優(yōu)解的影響已經(jīng)趨于穩(wěn)定。即對(duì)于規(guī)模在“60個(gè)固定工件，10架機(jī)器”以下的問題，選取溫度最大下降次數(shù)Mmax=90000次足可達(dá)到穩(wěn)定。類似地，另外從圖2中可以看出，對(duì)于規(guī)模在“60個(gè)固定工件，10架機(jī)器”以下的問題，最優(yōu)解保持次數(shù)Ccount選取900次即可保證算法達(dá)到穩(wěn)定。

圖1 最大迭代次數(shù)對(duì)解的影響

（三）算例

為了驗(yàn)證算法，本文采用航空公司機(jī)隊(duì)規(guī)劃問題進(jìn)行分析。基于航班機(jī)型分配的航空公司機(jī)隊(duì)規(guī)劃是典型的此類特殊固定工件加工問題：“工件”即為航班節(jié)(一個(gè)航班節(jié)由多個(gè)航班組成)[12]，“機(jī)器”即為飛機(jī)機(jī)型。工件的開始時(shí)刻、結(jié)束時(shí)刻明確，分別為航班的起飛時(shí)刻以及到達(dá)時(shí)刻，目標(biāo)為機(jī)隊(duì)規(guī)劃的總分配成本最小。

圖2 最優(yōu)解保持次數(shù)對(duì)解的影響

通過上述分析，選取t0=9000，tf=10，Mmax=90000，Ccount=900，對(duì)“7種機(jī)型，58個(gè)航班節(jié)”進(jìn)行計(jì)算，結(jié)果如圖3所示，橫坐標(biāo)是“航班節(jié)”的時(shí)刻表，圖中的任一“行”為航班節(jié)的飛行順序以及所使用機(jī)型。算例中需要的飛機(jī)總數(shù)為30架：其中機(jī)型2：1架；機(jī)型3：3架；機(jī)型4：26架；總成本為1484萬(wàn)元。

圖3 航空公司機(jī)隊(duì)規(guī)劃方案

為了對(duì)機(jī)隊(duì)規(guī)劃算法的運(yùn)算效率進(jìn)行評(píng)估以及驗(yàn)證計(jì)算結(jié)果的穩(wěn)定情況，經(jīng)過10次的仿真，結(jié)果如表1所示，計(jì)算出平均的CPU時(shí)間為32.9秒，總成本最大誤差為0.07%。

二、算法復(fù)雜度

算法時(shí)間復(fù)雜度主要由有向路徑的隨機(jī)生成與最優(yōu)的“有向路徑-機(jī)器”分配決定。對(duì)于隨機(jī)生成的z條有向路徑，其最好的情況下是所有的工件均可以在時(shí)間上相連，即m+1=t，其中m為工件數(shù)目，t為網(wǎng)絡(luò)時(shí)序圖中節(jié)點(diǎn)數(shù)目；而最壞的情況是所有的工件均不可以相連，即節(jié)點(diǎn)v1的出度=m =z。因此在網(wǎng)絡(luò)時(shí)序圖上的節(jié)點(diǎn)vi(i=1，2…t)上隨機(jī)地選擇發(fā)出弧，其最大的出度為工件數(shù)m。而網(wǎng)絡(luò)時(shí)序圖節(jié)點(diǎn)總數(shù)t的最大值為m+1，因此生成一條隨機(jī)路徑的復(fù)雜度可以表示為O(m2)，即生成z條有向路徑的時(shí)間復(fù)雜度為O(m3)；而對(duì)于“有向路徑-機(jī)器”分配方案，其時(shí)間復(fù)雜度顯然與可供選擇的“機(jī)器”數(shù)以及有向路徑數(shù)有關(guān)。若可供選擇的“機(jī)器”數(shù)為n，那么其算法時(shí)間復(fù)雜度應(yīng)為O(mn)。因此若在模擬退火算法迭代的過程中最大的迭代次數(shù)為M，那么整個(gè)算法的時(shí)間復(fù)雜度應(yīng)該為O(M(m3+ mn))。對(duì)于算法的空間復(fù)雜度而言，完全取決于所構(gòu)造的網(wǎng)絡(luò)時(shí)序圖中的“有向路徑”數(shù)以及可供選擇的“機(jī)器”數(shù)，因此空間復(fù)雜度為O(m2n)。

表1 算法CPU時(shí)間與成本函數(shù)值仿真

三、結(jié) 語(yǔ)

針對(duì)“機(jī)器資源有限，加工時(shí)間確定、機(jī)器與工件有約束關(guān)系以及以最少加工成本為目標(biāo)”的一類固定工件排序問題，本文根據(jù)工件的加工時(shí)刻構(gòu)造網(wǎng)絡(luò)時(shí)序圖，將固定工件排序轉(zhuǎn)化為網(wǎng)絡(luò)時(shí)序圖中的網(wǎng)絡(luò)流問題，并利用模擬退火進(jìn)行算法設(shè)計(jì)。通過算例發(fā)現(xiàn)，算法平均計(jì)算時(shí)間為32.9秒，總成本最大誤差為0.07%，算法的時(shí)間復(fù)雜度為O(M(m3+mn))，空間復(fù)雜度為O(m2n)。以此解決了現(xiàn)實(shí)中該類問題不存在有效多項(xiàng)式算法的缺陷。

另外必須說明的是，這類特殊的固定工件排序問題，能夠廣泛應(yīng)用于航空企業(yè)中的機(jī)型分配，基于航班機(jī)型分配的機(jī)隊(duì)規(guī)劃問題，另外也適用于企業(yè)人員的調(diào)度、火車調(diào)機(jī)分配、學(xué)校課程表制定等問題，因此具有良好的應(yīng)用前景。

[1] 朱一清. 可計(jì)算性和計(jì)算復(fù)雜性[M]. 北京: 國(guó)防工業(yè)出版社, 2006.

[2] GUPTA U I, LEE D T, LEUNG J Y T. An optimal solution for the channel-assignment problem [J]. IEEETransactions Computers, 1979, 28(11):807-810.

[3] FISCHETTI M, MARTELLO S, TOTH P. The fixed job scheduling problem with spread-time constraints [J].Operational Research, 1987, 35(6): 849-858.

[4] FISCHETTI M, MARTELLO S, TOTH P. The fixed job scheduling problem with working-time constraints [J].Operational Research, 1989, 37(3): 395-858.

[5] FISCHETTI M, MARTELLO S, TOTH P.Approximation algorithms for fixed job schedule problem [J].Operational Research ,1992 ,40(Supp.No.1):96-108

[6] JANSEN K. An approximation algorithm for the license and shift class design problem [J]. European Journal Operational Research, 1994, 73(1):127-131.

[7] GABREL V. Scheduling jobs within time windows on identical parallel machines new model and algorithms [J].European Journal Operational Research, 1995, 83(2): 320-329.

[8] HUANG Qi-wei, LOYD E. Cost Constrained Fixed Job Scheduling [C]. Lecture notes in computer science2841, 2003:111-124.

[9] 洪文, 胡雁玲. 工作排序問題及其數(shù)學(xué)模型[J]. 合肥聯(lián)合大學(xué)學(xué)報(bào), 2002, 12(1): 95-99.

[10] 孫宏, 楊偉, 黎青松, 文軍. 固定工件排序問題的網(wǎng)絡(luò)流模型研究[J]. 西華大學(xué)學(xué)報(bào), 2006, 25(1): 20-22.

[11] 孫宏, 文軍. 航空公司生產(chǎn)組織與計(jì)劃[M]. 成都:西南交通大學(xué)出版社, 2008: 69-74.

[12] 孫宏. 航空公司飛機(jī)排班問題：模型及算法研究[D].成都: 西南交通大學(xué), 2003.

Research on the Algorithm of One Class of Fixed Job Scheduling Problem

WANG Yu SUN Hong
(Civil Aviation Flight University of China Guanghan 618307 China)

For one class of fixed job scheduling problem, in which the available processors were limited, the processor matching-job had to be considered and minimized processor matching-job assigning cost were taken as objective. Firstly, based on the starting and completing time of the fixed job, this algorithm constructed a network time sequence figure. Secondly, the processor matching-job assigning were transformed into a netwok flow problem. Thirdly, the simulated annealing was used to design the scheduling problem algorithm. The solid example shows that the average CPU time is 32.9 seconds, the maximum error of total cost is 0.07%, the time complexity is O(M(m3+ mn)), and the space complexity is O(m2n). The results indicate that this algorithm is polynomial and feasible.

fixed job scheduling; network time sequence model; direction route; polynomial algorithm

F273

A

1008-8105(2010)03-0019-04

編輯 范華麗

2009 ? 09 ? 24

國(guó)家自然科學(xué)基金資助項(xiàng)目( No.60776820),中國(guó)民航飛行學(xué)院自然科學(xué)基金(J2008-76),中國(guó)民航飛行學(xué)院自然科學(xué)基金(J2009-29)

汪 瑜(1983 ? )男，工學(xué)碩士，中國(guó)民航飛行學(xué)院教師；孫 宏（1966 ?）男，工學(xué)博士，中國(guó)民航飛行學(xué)院教授.