不確定條件下的作業車間多目標調度模型及其遺傳優化

黃明，劉鵬飛，梁旭

(大連交通大學 軟件學院，遼寧 大連 116028)

0 引言

作業車間調度問題中的不確定性條件主要表現在制造過程中時常發生的擾動(如急件加工，機器損壞等)、生產信息獲得的不完整性、資源的優化配置等［1］.目前，雖然對于不確定性條件下的作業車間調度問題取得了一定的研究成果，但多數研究重點側重于采用某種具體算法求解不確定條件的某一種或幾種特定條件［2-3］，未形成系統的理論體系，對不確定條件下的作業調度模型研究較少，文獻［4］提出了一種不確定性條件下的生產調度模型，該模型采用決策系數策略，在用智能算法求解模型時通常使用隨機取權的方法.文獻［5］研究了以生產成本及設備利用率指標為調度目標的車間調度問題，建立了一個面向各種生產資源約束的多目標優化調度模型，但其模型仍然為單層的線性模型，將各函數利用權值相加，結果受權值參數干擾很大.

針對以上問題，本文提出一種新的不確定條件下的作業車間多目標調度模型，該模型為雙層調度模型，分別以作業時間最短和成本最低為調度目標，采用Pareto最優解［6］得到調度序列.其中的成本調度目標，不僅考慮到了車間調度問題中常見的生產資源約束、成本約束問題，還兼顧了企業中的機器使用率問題，具有很高的實用性.此外，本文采用遺傳算法對新模型求解，針對新的調度模型提出了一種改進的多目標遺傳算法，該算法先利用遺傳算法針對需要進行調度的作業進行調度運算，生成作業時間最短、機器空閑時間最小的解，再在這組解中評估生產成本，得到一組Pareto最優解，可以在兼顧機器使用率的同時使生產成本最小化.本文采用某機車廠的一組實際生產數據對改進的算法進行了驗證，結果證明了新調度模型及其改進算法的有效性.

1 不確定條件下的作業車間多目標調度模型

1.1 不確定條件分析

在企業的生產過程中，會遇到各種各樣的不確定因素［4］，如訂單取消，勞動力因素，每道工序中產品的作業時間、中間存儲單元的存儲量等;生產中機器故障，急件加工等情況也是不確定條件;此外，企業的資源優化配置也屬于不確定因素，需要對各種生產資源進行優化配置，以使企業的生產成本更低，贏得最大的經濟效益.本文將以作業車間為生產背景，分析生產過程中影響調度作業的各種因素，從一般車間擾動情況和生產成本最小兩方面對作業車間調度進行建模，因此，此問題實質上是一個多目標的決策問題.

1.2 不確定條件下的作業車間多目標調度模型

傳統的作業車間多目標調度模型［4-5］僅是簡單的將生產成本、生產周期等目標加權后相加，其權值帶有一定的隨機性，最后簡單對未加工的任務進行重新計算，其調度結果不僅在實質上是一個單目標的調度結果，缺乏客觀性，且調度結果對參數改變很靈敏.因此，針對傳統模型存在的缺點，本文提出了一種新的不確定條件下的作業車間多目標調度模型，該模型是一個雙層調度模型，在兼顧調度時間最短的基礎上，同時尋求發生車間擾動(例如機器損壞、加工時間延遲、緊急訂單等)之后的生產成本、管理費用、庫存費用的最小化，以達到利益的最大化和資源消耗的最小化.

新模型對參與調度的生產任務從加工時間、生產效率、雙資源(機器和人)的利用率、在庫管理成本四個方面分別進行了評估，并提出了集約工程的概念，即為了節省生產成本而使同種零件(定義為工藝相同且工藝順序相同的零件)批量制作的方法.

新的作業車間多目標調度模型描述如下:

模型的調度對象為發生車間擾動(例如機器損壞、加工時間延遲、緊急訂單等)之后，規定已著手的任務繼續做完，則剩下的未加工任務均為進行生產調度的對象.

為描述調度約束，給出如下符號定義:對于車間要生產的工件i，其訂單生產數量用xi表示，ai為當前調度實際生產數量;oij表示工件i的第j道工序;Ti為第i個工件生產完工時間;tij為第i道工序在第j臺機器上的作業時間，rtij為第i個工件使用第j臺機器前需要的機器準備時間;ctij為第i個工件在第j道工序完畢后搬運至下一工序所用機器的時間，則第i個工件的第j道工序作業時間為(rtij+tij+cij);sdayi為第i個工件在生產完畢入庫或存放在臨時存儲中心后至下次出庫(包括出庫直接售賣情況和出庫后進行裝配情況)所產生的庫存停滯天數;mlj為第j臺機器未進行加工使用的空閑時間.

為描述企業的各項成本，給出如下符號定義:調整設備單價hm指人操作機器的人工成本;企業日常的倉庫管理工作中，管理一天倉庫所發生的費用為am;部門單價dmj為根據部門設備種類不同而分別設定的部門勞動單價，在求解模型中可以根據某工件i在該道工序占用的機器j的類別來確定需要使用何種部門單價.

假設在機器損壞，來緊急訂單后，對于工件i的第m道工序，已完成生產的數量為yi，緊急訂單拆分工件后，需要新加工的工件i數量為zi，則新模型的數學描述為:

在式(1)中，模型M是由2個因素組成的向量，Timefitness為時間向量，Cost為成本向量，各個因素的詳細描述如下:

(1)時間評估因素Timefitness

車間調度的目標之一是調度時間的最小化，不確定條件下的作業車間調度模型同樣要求得到的調度作業序列是一個作業時間最短的序列.而在企業的生產車間中，往往是n個加工順序不同的工件以不同的時間在m臺機器上完成加工，工序之間往往存在前后約束，所以調度時間的目標應該是最小化最大完工時間［7］，所以，模型運用式(3)得到每一個調度作業序列所包含工件的最大完成時間，即Cmax，式(4)定義了調度模型的調度任務，即調度序列不包括已完成的工序或工件，且不包括已著手的工序(該部分工序應該繼續加工至該工序結束后再安排它工序);運用式(2)描述了模型對于時間評估因素的要求，即得到的N個調度方案中要求取調度時間最小化的調度作業序列.

運用式(2)和式(3)評估調度時間，可以按照調度時間最小化合理調度安排各作業，同理，各個作業間如果進行了合理調度，則各機器空余時間自然會現對變少，滿足作業車間對加工時間最小化的目標.

(2)生產效率因素pd

不確定條件下的調度問題包括當車間發生擾動(例如機器損壞、加工時間延遲、緊急訂單等)之后的車間調度，所以在建模中必須考慮到各工序間的生產成本問題，對此，本文提出一種集約生產的概念，即為了節省生產成本而使同種物品(定義為工藝相同且工藝順序相同的零件)批量制作，可以節省大量的機器準備時間和物品搬運時間，從而提高了生產效率.式(5)、(6)定義了模型對于各成本的調度要求，即成本和要求最小化.式(8)則說明了工件i的實際生產數量ai，即如果某工件在調度時刻，存在m道已完成工序或m道已著手工序，則集約生產的數量僅取原任務數量，新訂單的工件i作為新任務參加調度;如果某工件已生產結束了yi數量，且無已完成工序或已著手工序，則集約生產的數量取xi－yi+zi;式(7)詳細描述了新模型對于生產效率的要求.

(3)雙資源利用率因素mm

通常情況下，在車間發生擾動之前，車間的資源已進行了組合分配，那么，在擾動發生之后，必須重新分配車間資源，所以，不確定條件下的調度問題必須考慮的另一個影響因素是雙資源制約因素.本文提出了控制人和機器的等待時間最小以使人的勞動成本和機器的使用成本達到最高的策略，其具體控制策略通過式(9)實現為所有機器未進行加工的時間和，乘以hm(即人操作機器的人工成本)可以得到對機器進行調整時或機器空閑，手工閑置時的雙資源利用成本.

(4)在庫成本因素sc

工件在車間加工完畢后，一般將送至倉庫或臨時存儲中心進行保管.為了降低車間的存儲成本，管理要求工件在倉庫或臨時儲存中心的停滯時間盡量縮短，即在滿足交貨期的前提下使庫存物品或臨時存儲中心的工件存放數量達到最少.針對此問題，本文提出式(10)來計算在庫成本(包括使用倉庫或臨時存儲中心的成本)，描述了工件i的在庫成本為工件i的在庫停滯天數乘以管理倉庫的單價費用，且停滯天數越少，在庫成本越小，式(6)描述的成本費用會越低，達到追求成本最小化的調度目標.

2 求解新模型的多目標遺傳調度算法

遺傳算法(Genetic Algorithms，GA)是由美國密執根(Minchigan)大學的Holland教授于1975年首先提出的一種借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法，因其算法本身簡單，具有本質并行性等優點［8］，廣泛應用于各種優化領域.至今，遺傳算法在調度領域中己經得到了比較廣泛的應用，國內外學者發表了大量應用遺傳算法解決調度問題的文章［9］，遺傳算法對于調度問題的適用性已得到肯定.因此，本文采用了遺傳算法對上述提出的新模型進行求解.

新模型采用向量來描述不確定條件下的作業車間調度目標，所以調度結果采用Pareto最優解是一個可行的方法.此外，車間調度的目的是根據各種制約條件，生成可行的調度以指導生產，如果提供一組解，那么調度人員需要請專家指導在Pareto最優解進行最終選擇，算法缺乏實用性.因此，本文采用一種改進的多目標遺傳調度算法來求解新模型，其算法基本框架為:得到需要進行調度的生產任務，根據模型規則計算各工件的生產數量，確定調度任務，優化生成調度時間最小的解，然后在這組解中評估各個成本因素，得到Pareto最優解，取成本函數最小的染色體進行最優保留策略［10］，循環迭代后，輸出總體成本最優的解.該策略同時兼顧了調度時間最小化和各項生產成本的最小化.

改進的多目標遺傳算法步驟如下:

Step 1:得到需要進行本次車間調度的生產任務，規則為:

調度的任務=原有任務+緊急訂單任務－已著手的任務－已完成任務

Step 2:進行集約生產統計，將同種工藝且同樣工藝順序的工件集中進行生產.

Step 3:初始化染色體.

Step 4:運行遺傳算法，進行交叉，變異，以本文的式(2)為目標函數進行優化.

Step 5:采用本文提到的式(3)計算種群中每個染色體的綜合成本函數值，按照函數值最小的原則更新本次循環的Pareto非劣解.

Step 6:運用本次循環成本最小的染色體進行最優保留策略.

Step 7:重復step 4-step6，直至滿足結束條件.

Step 8:將車間的已著手任務作為每個染色體最前面的基因.

Step 9:輸出綜合成本最優結果.

利用改進的多目標遺傳調度算法求解調度模型，可以提供一個同時兼顧調度時間最小、機器利用率最高和綜合成本最小的調度方案，具有很高的實用性.

3 仿真實驗

本文將采用改進的多目標遺傳算法對新模型進行試算，同時鑒于各個調度模型關注的調度目標不同，而本文同時關注了調度時間、生產效率、雙資源利用率、庫存成本四個方面，所以為了說明新模型可以提供兼顧調度時間最少和成本最小化的調度方案，本文將采用文獻［4-5］中的隨機加權法來測試對以上四個調度目標的改進.

仿真實驗中，遺傳算法的種群規模為6，最優解集規模為3，運用最優保留策略［10］，染色體采用基于自然數的編碼方法［11］，單點交叉［6］，交換變異［6］，共運行30代，系統環境，測試數據、系統參數設置及預設車間情況如下:

(1)系統環境

操作系統:Microsoft Windows XP Professional版本2002

內存:512MB

CPU:2.80Hz

編程語言:C語言

(2)測試數據

采用了某機車廠的部分生產數據.關鍵數據如表1:

表1 測試所用生產數據

(3)算法參數

為了計算方便，設式(7)所有機器類別的dmj=1.0;設式(9)中 hm=0.4;式(10)中 am=0.6;設原訂單的生產數量，工件1為10，工件2為5;設重調度時刻，工件2的第一道工序已著手，緊急訂單需要2個新的工件2，5個工件1.

試算的結果如表2(迭代次數為系統隨機選取):

表2 改進的遺傳多目標算法仿真結果

表3為采用隨機加權法的遺傳算法運算結果，可以看出，由于各成本因素權值不定，導致染色體的進化不穩定，易陷入局部最優解;且適應度并不能直觀反映出染色體的調度時間和成本優劣情況.而表2可以看出，本文采用改進的多目標遺傳調度算法求解雙層調度模型，能夠有效地同時對調度時間和成本進行優化，保持基本一致的種群進化方向，得到的調度時間目標較隨機加權的遺傳算法更為優秀，可以更為有效地解決調度中常見的生產資源約束、成本約束問題.

表3 采用隨機加權法的遺傳算法仿真結果

4 結論

本文提出的不確定條件下的作業車間多目標調度模型相對于傳統作業車間多目標調度模型，從調度時間目標和成本目標上分別進行優化，不僅考慮到了生產調度中常見的車間擾動問題、成本問題，還兼顧了企業中的機器使用率問題，具有很高的實用性;相應的改進算法引入了“集約生產”的思想，減少了機器準備時間，降低了生產成本，得到的Pareto最優解，可以在兼顧機器使用率的同時使生產成本最小化.

［1］劉明周，單暉.不確定條件下車間動態重調度優化方法［J］.機械工程學報，2010.45(10):137-141.

［2］陳知美，顧幸生.基于蟻群算法的不確定條件下的Job Shop調度［J］.山東大學學報(工學版)，2005，35(4):74-79.

［3］丁雷，丁愛民，寧汝新.工時不確定條件下的車間作業調度技術［J］.計算機集成制造系統，2010，16(1):98-103.

［4］顧幸生.不確定性條件下的生產調度［J］.華東理工大學學報，2000，26(5):441-444.

［5］鞠全勇，朱劍英.多目標批量生產柔性作業車間優化調度［J］.機械工程學報，2007，43(8):148-151.

［6］王小平，曹立明.遺傳算法:理論、應用及軟件實現［M］.西安:西安交通大學出版社，2002:52-55，73.

［7］何彥.面向綠色制造的機械加工系統任務優化調度方法研究［R］.重慶:重慶大學，2007:79-80.

［8］PENG Wu-liang，WANG Cheng-en.Critical chain method project scheduling based model and its GA solution［J］.Journal of Systems Engineering，2010，25(1):125-133.

［9］周輝仁，鄭丕諤，安小會，等.基于遺傳算法求解Job Shop調度優化的新方法［J］.系統仿真學報，2009，21(11):143-146.

［10］何琳，王科俊，李國斌，等.最優保留遺傳算法及其收斂性分析［J］.控制與決策，2000，15(1):63-66.

［11］楊曉梅，曾建潮.采用多個體交叉的遺傳算法求解作業車間問題［J］.計算機集成制造系統，2004，10(9):1114-1118.