調(diào)度策略在并行機(jī)調(diào)度仿真的應(yīng)用

王 崐，鄭樹(shù)琴

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

0 引 言

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

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

1 研究方法

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

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

每張訂單的實(shí)際加工時(shí)間：

訂單實(shí)際加工時(shí)間=準(zhǔn)備時(shí)間+

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

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

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

2 結(jié)果分析

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

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

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

表2 Fl e x s i m仿真實(shí)驗(yàn)結(jié)果

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

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

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

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

3 結(jié)束語(yǔ)

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