不確定條件下的作業(yè)車間多目標(biāo)調(diào)度模型及其遺傳優(yōu)化

黃明，劉鵬飛，梁旭

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

0 引言

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

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

1 不確定條件下的作業(yè)車間多目標(biāo)調(diào)度模型

1.1 不確定條件分析

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

1.2 不確定條件下的作業(yè)車間多目標(biāo)調(diào)度模型

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

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

新的作業(yè)車間多目標(biāo)調(diào)度模型描述如下:

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

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

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

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

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

(1)時間評估因素Timefitness

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

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

(2)生產(chǎn)效率因素pd

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

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

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

(4)在庫成本因素sc

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

2 求解新模型的多目標(biāo)遺傳調(diào)度算法

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

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

改進的多目標(biāo)遺傳算法步驟如下:

Step 1:得到需要進行本次車間調(diào)度的生產(chǎn)任務(wù)，規(guī)則為:

調(diào)度的任務(wù)=原有任務(wù)+緊急訂單任務(wù)－已著手的任務(wù)－已完成任務(wù)

Step 2:進行集約生產(chǎn)統(tǒng)計，將同種工藝且同樣工藝順序的工件集中進行生產(chǎn).

Step 3:初始化染色體.

Step 4:運行遺傳算法，進行交叉，變異，以本文的式(2)為目標(biāo)函數(shù)進行優(yōu)化.

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

Step 6:運用本次循環(huán)成本最小的染色體進行最優(yōu)保留策略.

Step 7:重復(fù)step 4-step6，直至滿足結(jié)束條件.

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

Step 9:輸出綜合成本最優(yōu)結(jié)果.

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

3 仿真實驗

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

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

(1)系統(tǒng)環(huán)境

操作系統(tǒng):Microsoft Windows XP Professional版本2002

內(nèi)存:512MB

CPU:2.80Hz

編程語言:C語言

(2)測試數(shù)據(jù)

采用了某機車廠的部分生產(chǎn)數(shù)據(jù).關(guān)鍵數(shù)據(jù)如表1:

表1 測試所用生產(chǎn)數(shù)據(jù)

(3)算法參數(shù)

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

試算的結(jié)果如表2(迭代次數(shù)為系統(tǒng)隨機選取):

表2 改進的遺傳多目標(biāo)算法仿真結(jié)果

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

表3 采用隨機加權(quán)法的遺傳算法仿真結(jié)果

4 結(jié)論

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

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

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

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

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

［5］鞠全勇，朱劍英.多目標(biāo)批量生產(chǎn)柔性作業(yè)車間優(yōu)化調(diào)度［J］.機械工程學(xué)報，2007，43(8):148-151.

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

［7］何彥.面向綠色制造的機械加工系統(tǒng)任務(wù)優(yōu)化調(diào)度方法研究［R］.重慶:重慶大學(xué)，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調(diào)度優(yōu)化的新方法［J］.系統(tǒng)仿真學(xué)報，2009，21(11):143-146.

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

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