王 崐，鄭樹琴

（1.山西省煤炭規(guī)劃設(shè)計院，山西 太原 030045；2.太原理工大學(xué)機械工程學(xué)院，山西 太原 030024）

0 引 言

調(diào)度是在有限生產(chǎn)資源約束中優(yōu)化效益目標函數(shù)的決策過程。多機調(diào)度旨在為一系列工作的加工處理過程建立適當?shù)恼{(diào)度次序，以保所有工作在合適的時間內(nèi)完成；在此過程中需要解決的問題包括：機器的分配、工作處理次序、調(diào)度合理性等。多機調(diào)度問題分為針對并行機和串行機，均被證明為NP-hard問題[1]。并行機調(diào)度可按系統(tǒng)配置分為三種：等同機、同類機、變速機的調(diào)度。實際調(diào)度需要考慮系統(tǒng)隨機性和動態(tài)性的影響[2]，例如：加工時間的不確定性和訂單到達率隨時間的動態(tài)性。大型系統(tǒng)的多目標調(diào)度時常出現(xiàn)，需要深入研究；因此文章建立仿真模型模擬動態(tài)隨機環(huán)境中的等同機調(diào)度，進而研究不同策略在此系統(tǒng)中的作用，以求達到同時最大化吞吐率和最小化延遲工件量的雙重目的。

多目標調(diào)度問題應(yīng)用廣泛，但其理論研究有待完善。Andres等[3]提出了多目標遺傳算法解決流水車間調(diào)度問題，目標函數(shù)包括最小化調(diào)度時長和拖期，模型約束包括基于工序排序的調(diào)整時間和順序的約束。Lee和Asllani[4]針對工序的調(diào)整時間的最小化拖期工件量和調(diào)度時長的單機調(diào)度問題，建立了混合整數(shù)規(guī)劃模型及相關(guān)遺傳算法。Jungwattanaki等[5]采用遺傳算法和模擬退火算法，解決工序的調(diào)整時間的最小化加權(quán)調(diào)度時長和拖期工件量的流水車間調(diào)度問題。Picard和Queyranne[6]將單機調(diào)度問題建模成時間相關(guān)的旅行者問題（Traveling Salesman Problem）并運用分支定界法求解，以達到最小化拖期和加權(quán)拖期的目的。Allahverdi等[7]描述并解釋了基于準備時間的多準則調(diào)度問題的復(fù)雜度。因此，最大化生產(chǎn)率和最小化延遲工件量的多目標并行機調(diào)度問題需要更重視。Kiran陳述了仿真方法對于隨機動態(tài)調(diào)度問題的適用性。隨機動態(tài)調(diào)度環(huán)境中，并非所有工作在同一時間進入生產(chǎn)系統(tǒng)，而且訂單數(shù)量、加工時間、準備時間等變量都有隨機性，因此利用仿真將調(diào)度策略用于不同的工作車間調(diào)度（比如Gupta等[8]，Tavakkolo-Moghad?dam等[9]和Ying[10]）。據(jù)上綜述，多目標隨機動態(tài)等同機調(diào)度問題很有實用價值，將用仿真方法分析隨機動態(tài)環(huán)境中的調(diào)度問題。

1 研究方法

圖1 仿真模型的配置和布局

文中制造系統(tǒng)的并行機調(diào)度模型是用Flexsim仿真軟件，它是一款能幫助可視化流程優(yōu)化生產(chǎn)和最小化運作費用的基于真實對象的仿真軟件，可用來建立并分析隨機系統(tǒng)離散事件仿真模型，可供仿真3D動畫，并有強大數(shù)據(jù)收集和結(jié)果分析功能。仿真模型的布局和參數(shù)，基于某大型制造企業(yè)的組裝車間，具有7條等同功能的生產(chǎn)線，包含多個裝配步驟、加工時間較長，因此準備時間和加工時間中的不確定性和隨機性較大；而且訂單到達速率按時間而不同、產(chǎn)生了動態(tài)性，增加了調(diào)度求解的難度。Flexsim仿真模型的建立，基于組裝車間實際布局的研究分析；模型參數(shù)及輸入數(shù)據(jù)的統(tǒng)計分布，來自于車間實際數(shù)據(jù)的采集和前期分析，以保仿真模型具有很強的理論和實踐價值。模型的配置和布局見圖1，由于車間白班和夜班的訂單到達率及加工速率都不同，因此采用不同的統(tǒng)計分布輸入量。為了盡可能模擬車間實際情況，訂單到達時間采取經(jīng)驗分布。訂單的相關(guān)信息（比如訂單數(shù)量、到達時間、交貨期、遲到時間等）在訂單生成的同時隨機分配給每張訂單；每張訂單可被7條生產(chǎn)線中的任何一條加工、并且預(yù)期加工時間與生產(chǎn)線的選擇無關(guān)，即生產(chǎn)實際中加工時間的隨機性（方差）在調(diào)度策略中被忽略。

每張訂單的實際加工時間：

訂單實際加工時間=準備時間+

（工件標準加工時間+調(diào)整因子）×訂單數(shù)量.（1）

式中：加工時間的隨機性由調(diào)整因子表示，代表了實際加工時間與標準時間的偏差，來自不同生產(chǎn)線的配置（機器設(shè)備配置、工人熟練程度等）；調(diào)整因子的數(shù)值大小來自于一個Johnson Bounded分布的隨機變量，而此統(tǒng)計分布的參數(shù)擬合源于該車間的實際生產(chǎn)數(shù)據(jù)分析。該模型的仿真時間設(shè)置為24 000 min，即20個工作日。模型預(yù)熱時間為2 400 min，即2個工作日。每個模型重復(fù)10次，以對仿真結(jié)果進行統(tǒng)計分析。模型參數(shù)的設(shè)置見表1。實際數(shù)據(jù)統(tǒng)計期間，33個工作日的實際產(chǎn)量為1 261。根據(jù)表1參數(shù)設(shè)置，當重復(fù)10次仿真模型、并且每次運行42 000 min（包含2 400 min的預(yù)熱時間）時，運用先入先出（FIFO）調(diào)度策略（車間現(xiàn)行實際調(diào)度策略）的仿真輸出結(jié)果的產(chǎn)量平均值為1 232，90%置信區(qū)間為[1 178,1 287]，即仿真結(jié)果的置信區(qū)間包含了實際產(chǎn)量（1 261）。此結(jié)果驗證了本文仿真模型的正確性。

表1 Fl e x s i m仿真模型參數(shù)設(shè)置

2 結(jié)果分析

本文依據(jù)仿真模型和參數(shù)設(shè)置，采用不同調(diào)度策略所得仿真結(jié)果見表2，調(diào)度策略包括：先入先出（FIFO）、最小化加工時間優(yōu)先（SPT）、最早訂單完成時間優(yōu)先（EDD）。其中FIFO是車間實際使用的調(diào)度策略，也是很多企業(yè)最常用的調(diào)度策略。表2列出基于單一目標（最大化生產(chǎn)率或最小化拖期工件量）和多目標時最優(yōu)調(diào)度策略的仿真結(jié)果。多目標函數(shù)定義按式（吞吐率）：

α×拖期工件量；其中：0﹤α﹤1. （2）式中：多目標函數(shù)的含義是：最大化調(diào)整吞吐率，即在總生產(chǎn)率中減去拖期工件帶來的罰值，此罰值與拖期工件量成正比，罰值的權(quán)重α介于0和1之間，取決于企業(yè)中拖期工件的管理成本。本次試驗α選定值0.5。

表2考慮單一目標函數(shù)進行對比策略時，SPT策略對于分別最大化生產(chǎn)率和最小化拖期工件量均可達到最優(yōu)。EDD策略相較現(xiàn)行策略FIFO在控制拖期工件量方面有一定優(yōu)勢，但是在結(jié)果中的總產(chǎn)量并不因策略的改變而增加，反而會因為過度考慮優(yōu)化拖期訂單而以犧牲吞吐量為代價。

表2 Fl e x s i m仿真實驗結(jié)果

當按式（2）的多目標函數(shù)時，SPT策略仍有很大優(yōu)越性是不僅試驗期間目標函數(shù)結(jié)果的均值優(yōu)勢于策略FIFO和EDD，而且表中結(jié)果的標準差也明顯降低?？傊?，應(yīng)用SPT策略可顯著提高系統(tǒng)產(chǎn)出的均值，同時降低輸出結(jié)果的不確定性（即標準差），從而提高系統(tǒng)的可靠性。

由于SPT策略對提高系統(tǒng)產(chǎn)量和可靠性的表現(xiàn)顯著，表3將SPT策略對比現(xiàn)行FIFO策略的優(yōu)越性進行了總結(jié)。絕對提高量是運用各評價指標時SPT結(jié)果和FIFO結(jié)果均值的差，相對提高量則定義為式（3）：

式中：代入的數(shù)值為表2中仿真結(jié)果的均值。表3結(jié)果表明，如果企業(yè)采用SPT策略在其等同機車間內(nèi)，生產(chǎn)系統(tǒng)的效率將大幅提高；僅考慮吞吐率為目標時，SPT策略帶來的增幅為14.9%；拖期工件數(shù)量單一目標的減少為49.6%；如果考慮多準則多目標評價時，SPT策略的使用可以帶來61.3%的顯著提高。

表3 S PT策略相較于現(xiàn)行FI FO策略的生產(chǎn)提高量

3 結(jié)束語

本文針對動態(tài)隨機環(huán)境，運用調(diào)度策略建立了并行機調(diào)度問題的仿真模型；該等同并行機調(diào)度問題以最大化吞吐率和最小化延遲工作數(shù)量為多目標函數(shù)。此仿真模型用于一個7臺等同并行機的裝配車間，模型參數(shù)和實驗數(shù)據(jù)來自某大型制造企業(yè)。仿真結(jié)果與實際數(shù)據(jù)結(jié)果的比較證明了仿真模型的正確性。仿真結(jié)果分析進而表明：最小化加工時間優(yōu)先（SPT）的調(diào)度策略相較現(xiàn)行的先入先出（FIFO）策略，在生產(chǎn)輸出量和可靠性上都有顯著提高。因此，大型動態(tài)隨機環(huán)境的生產(chǎn)系統(tǒng)中，適當改變現(xiàn)行調(diào)度策略，加入新的調(diào)度策略或調(diào)度算法，可大幅提高系統(tǒng)的效率和可靠性。

[1] Cheng,T.C.E，Sin,C.C.S.A state-of-the-art review of paral?lel-machine scheduling research[J].European Journal of Op?erational Research，1990（47）：271-292.

[2] Banks,J.Handbook of simulation:principles,methodology,ad?vances,applications,and practice[M].Wiley,New York.1998.

[3] Andres,C.,Tomax,J.V.,Garcia-Sabater,J.P.and Miralles,C.,A multi-objective genetic algorithm to solve the schedul?ing problem in flowshops with sequence dependents setup times[J].Proceedings of the International Conference on In?dustrial Engineering and System Management,Marrakech,Morocco,May 2005（16-19）：630-635.

[4] Lee,S.M.and Aslani,A.A.Job scheduling with dual criteria and sequence-dependent setups[J].Mathematical versus ge?netic programming.Omega，2004（32）:145-153.

[5] Jungwattanaki,J.,Reodecha,M.,Chaovalitwongse,P.and Werner,F.An evaluation of sequencing heuristics for flesible flowshop scheduling problems with unrelated parallel ma?chines and dual criteria[J].Otto-von-Guericke-Universitat Magdeburg,2005,28（5）：1-23.

[6] Picard,J.C.and Queyranne M.The time-dependent traveling salesman problem and its application to the tardiness problem in one machine scheduling[J].Operational research,1978（26）：86-110.

[7] Allahverdi,A.,Gupta,J.N.D.and Aldowaisan,T.,A review of scheduling research involving setup considerations.Omega[M].Int.J.Mgmt Sci.,1999（27）：219-239.

[8] Gupta,A.K.,A.I.Sivakumar.Simulation based multiobjective schedule optimization in semiconductor manufacturing[M].In Proceeding of the 2002 Winter Simulation Conference,ed.E.Yucesan,C.-H.Chen,J.L.Snowdon,and J.M.Charnes,IEEE,Piscataway,New Jersey:2002:1862-1870.

[9] Tavakkoli-Moghaddam,R.and M.Daneshmand-Mehr.A computer simulation model for job shop scheduling problems minimizing makesapn[J].Computers＆amp;Industrial Engineering 2005（48），2002：811-823.

[10] Ying,C.C.,1996,Specification of a job shop scheduling sim?ulation model and some properties of its internal transition function[J].Computers ind.Engng,1996（31）：201-204.