工序松弛規(guī)則及其在動(dòng)態(tài)Job-Shop調(diào)度問(wèn)題中的應(yīng)用仿真研究

范華麗，熊禾根，錢國(guó)潔，蔣國(guó)璋，李公法

（武漢科技大學(xué) 機(jī)械自動(dòng)化學(xué)院，武漢 430081）

0 引言

車間作業(yè)調(diào)度問(wèn)題自上個(gè)世紀(jì)五十年代被Jonson[1]提出以來(lái)，一直受到各個(gè)學(xué)科和領(lǐng)域的廣泛關(guān)注。車間作業(yè)調(diào)度有多種類型，其中Job-Shop調(diào)度問(wèn)題[2]由于其在實(shí)際生產(chǎn)中存在的廣泛性及問(wèn)題的復(fù)雜性，成為了研究的熱點(diǎn)。求解Job-Shop問(wèn)題的方法有多種類型，其中智能算法和啟發(fā)式算法[3]因其能夠快速有效的得到近優(yōu)解而成為近年來(lái)的研究熱點(diǎn)。然而在實(shí)際企業(yè)的生產(chǎn)車間中，通常有成百上千個(gè)工件等待加工，且車間參數(shù)及工況會(huì)隨時(shí)變化，如機(jī)器故障，緊急訂單的插入等，因此需要實(shí)時(shí)地進(jìn)行重調(diào)度，智能算法和啟發(fā)式算法在針對(duì)此類問(wèn)題時(shí)，通常不能很快的得到近優(yōu)解，而早期的優(yōu)先規(guī)則[4]因其算法的簡(jiǎn)潔性和易于執(zhí)行等特點(diǎn)，在求解此類問(wèn)題時(shí)顯現(xiàn)出優(yōu)勢(shì)。

優(yōu)先規(guī)則有多種，很多文獻(xiàn)[5][6]給出了關(guān)于它們性能的分析研究，也得出了一些具有參考意義的結(jié)論[7]。本文根據(jù)已有的優(yōu)先規(guī)則，提出了一個(gè)新的規(guī)則SOP（slack of operation processing time），在考慮具有擴(kuò)展工藝約束的調(diào)度問(wèn)題模型中分析和比較了該規(guī)則的性能。并從工件總拖期和拖期工件百分比兩個(gè)性能指標(biāo)進(jìn)行分析，探索了擴(kuò)展工藝約束率和交貨期寬裕度系數(shù)對(duì)調(diào)度規(guī)則性能的影響。

1 新規(guī)則的提出

優(yōu)先規(guī)則有多種類型，根據(jù)所包含的信息，一般可分為以下四類：基于加工工時(shí)的規(guī)則、基于交貨期的規(guī)則、組合規(guī)則和既非基于加工工時(shí)也非基于交貨期的規(guī)則。這些規(guī)則中，有不少是在已有基礎(chǔ)上進(jìn)行改進(jìn)得到的。如Baker[8]對(duì)SPT(shortest processing time)和EDD(earliest due date)規(guī)則的性能曲線進(jìn)行分析，發(fā)現(xiàn)當(dāng)交貨期較緊時(shí)SPT性能較好，當(dāng)交貨期較松時(shí)，EDD性能較好，因此進(jìn)行綜合，在松弛較多時(shí)取工件交貨期為優(yōu)先值，在工件沒(méi)有松弛時(shí)取加工工時(shí)作為優(yōu)先值，得到了性能較好的MDD(modified due date)規(guī)則，MDD實(shí)質(zhì)就是SPT和EDD的組合。又如Conway[9]對(duì)工件交貨期di進(jìn)行細(xì)化進(jìn)而提出了工序交貨期dij的概念，Baker和Kennet[10]在此基礎(chǔ)上得到了改進(jìn)的規(guī)則MOD(modified operation due date)，其實(shí)質(zhì)也是把MDD規(guī)則優(yōu)先值中的工件交貨期改成了工序交貨期，通過(guò)仿真試驗(yàn)結(jié)果證明其性能較好。

受到上述文獻(xiàn)的啟發(fā)，在工件松弛SLACK的基礎(chǔ)上，提出了工序松弛的概念。工件松弛是指工件交貨期減去當(dāng)前時(shí)間和該工件所有剩余加工工時(shí)。工序松弛可以定義為工序交貨期減去當(dāng)前時(shí)間和工序加工工時(shí)，因此工序松弛越小，這道工序就越緊急，也應(yīng)具有最高的優(yōu)先級(jí)從而最先被加工。我們依此提出SOP規(guī)則，它的優(yōu)先值為：

2 問(wèn)題的模型

動(dòng)態(tài)Job-Shop調(diào)度問(wèn)題可以描述為有一系列工件J陸續(xù)到達(dá)具有M臺(tái)機(jī)器的車間，每個(gè)工件有一個(gè)到達(dá)時(shí)間ri和交貨期di，每個(gè)工件都有一定數(shù)量的工序ni，它們按照不同的工藝順序約束在不同機(jī)器上加工，工序i的第j道工序的加工工時(shí)為pij。要求確定各機(jī)器上所有工件的加工開(kāi)始時(shí)間和加工完成時(shí)間，使得某個(gè)性能指標(biāo)達(dá)到最優(yōu)。通常這里的工藝約束指的是一個(gè)工件內(nèi)部所定義的工藝路線順序約束，文獻(xiàn)[11]指出，在許多加工裝配型離散制造企業(yè)中，還存在另外兩類工藝約束，即工藝路線中的延時(shí)約束和工件間的工藝約束，我們把這類約束定義為擴(kuò)展工藝約束。本文的仿真模型即考慮具有擴(kuò)展工藝約束的動(dòng)態(tài)Job-Shop調(diào)度問(wèn)題，調(diào)度目標(biāo)為最小化工件總拖期T和拖期工件百分比%T。

3 調(diào)度規(guī)則試驗(yàn)處理與分析

工件陸續(xù)到達(dá)的Job-Shop調(diào)度問(wèn)題是一種典型的動(dòng)態(tài)車間作業(yè)調(diào)度問(wèn)題。針對(duì)此類問(wèn)題進(jìn)行仿真調(diào)度試驗(yàn)，在具有擴(kuò)展工藝約束的動(dòng)態(tài)車間作業(yè)調(diào)度問(wèn)題中，比較和分析不同調(diào)度規(guī)則的性能，并研究不同車間模型參數(shù)對(duì)調(diào)度規(guī)則性能的影響。

3.1 仿真試驗(yàn)的設(shè)計(jì)與生成

仿真試驗(yàn)案例中有10臺(tái)機(jī)器，工件總數(shù)為3000個(gè)，以指數(shù)分布形式分批到達(dá)車間，批量大小服從離散均勻分布每個(gè)工件的工序數(shù)量從離散均勻分布DU[3,6]中產(chǎn)生。工件的工藝路線隨機(jī)生成，每道工序的加工機(jī)器以相同概率按無(wú)放回抽樣方式從10臺(tái)機(jī)器中產(chǎn)生。每道工序的加工工時(shí)從離散均勻分布DU[5,15]中產(chǎn)生，因此每道工序的平均加工時(shí)間個(gè)單位時(shí)間。同時(shí)工件間具有擴(kuò)展工藝約束的工序是隨機(jī)生成且沒(méi)有沖突的。

通常，車間利用率Ug是反映工件投放時(shí)間的一個(gè)因素。對(duì)于本文中的考慮擴(kuò)展約束的動(dòng)態(tài)車間作業(yè)調(diào)度問(wèn)題，車間利用率可作如下定義：

式中，m是車間中機(jī)器的數(shù)量，指平均每個(gè)工件的工序數(shù)量，指平均每個(gè)工件的加工工時(shí)，是指工件批量到達(dá)的平均時(shí)間間隔。因此每給定一個(gè)車間利用率，就可以得到相應(yīng)的工件批量到達(dá)的時(shí)間間隔。不失一般性，假設(shè)第一批工件的到達(dá)時(shí)間為0，則根據(jù)時(shí)間間隔tv可計(jì)算出每批工件的到達(dá)時(shí)間，即投放時(shí)間ri。

考慮到具有擴(kuò)展工藝約束的工件的數(shù)量或許會(huì)是影響調(diào)度規(guī)則性能的一個(gè)因素，我們引進(jìn)Ec作為工件擴(kuò)展工藝約束率。本文的仿真試驗(yàn)中，我們選取了四個(gè)不同程度的工件擴(kuò)展工藝約束率，即0%、3%、5%、8%。

此外，工件交貨期的設(shè)置采用的是TWK(Total Work Content)規(guī)則，即式中，c是交貨期寬裕度系數(shù)，它表示了交貨期設(shè)置的松緊程度。由于拖期工件百分比%T是衡量交貨期松緊程度的一個(gè)合理指標(biāo)，因此可通過(guò)不同的%T來(lái)控制交貨期的松緊程度。對(duì)于不同程度的Ug和Ec，我們根據(jù)四種不同程度的%T設(shè)置相應(yīng)的四個(gè)不同松緊程度的c值，即對(duì)應(yīng)松交貨期，對(duì)應(yīng)中等程度的交貨期，對(duì)應(yīng)緊交貨期。例如，當(dāng)時(shí)，通過(guò)仿真試驗(yàn)得到不同程度下的交貨期寬裕度系數(shù)取值分別為c=10,14,20,28。

仿真試驗(yàn)測(cè)試了四種Ec和四種不同c值，因此共有16個(gè)不同變量的仿真試驗(yàn)，對(duì)于不同仿真參數(shù)的試驗(yàn)運(yùn)行10次取其平均值?？紤]到車間穩(wěn)定狀態(tài)和所采集數(shù)據(jù)的有效性及合理性，截除前后各500個(gè)工件，采集10次仿真在各調(diào)度規(guī)則下的工件總拖期和拖期工件百分比。

3.2 調(diào)度規(guī)則的選擇

仿真試驗(yàn)所選用的調(diào)度規(guī)則包括：SPT、EDD、MDD、ODD、RR、WINQ[12](total work-content of jobs in the queen of the next operation of a job)和SOP。這幾種規(guī)則都是性能較好且運(yùn)用較廣泛的規(guī)則。

3.3 試驗(yàn)結(jié)果的分析與評(píng)價(jià)

3.3.1 基于工件總拖期的分析

為了更加直觀的分析Ec和c對(duì)調(diào)度規(guī)則性能的影響，我們對(duì)試驗(yàn)數(shù)據(jù)進(jìn)行兩方面的分析，即固定一個(gè)c值，看不同Ec對(duì)調(diào)度規(guī)則性能的影響，以及固定一個(gè)Ec，看不同c值下各個(gè)調(diào)度規(guī)則的性能。為了使結(jié)果更具有代表性和說(shuō)明性，我們?cè)诳紤]這兩個(gè)方面時(shí)，均選取中等程度的交貨期寬裕度和適度的擴(kuò)展工藝約束率。

表1列出了在中等程度的交貨期寬裕度即[10%,20%]時(shí)，不同Ec下各調(diào)度規(guī)則的工件總拖期的相對(duì)增長(zhǎng)程度RPI(the relative percentage increase)。用SR表示調(diào)度規(guī)則的集合，T(X)表示規(guī)則的工件總拖期，規(guī)則X的工件總拖期的相對(duì)增長(zhǎng)程度RPI(T)可定義為：

表1 四種擴(kuò)展工藝約束下各調(diào)度規(guī)則的工件總拖期的相對(duì)增長(zhǎng)程度

表1中各調(diào)度規(guī)則按照RPI值遞增排列。從表中可以看出當(dāng)交貨期程度適度時(shí)，SOP在無(wú)擴(kuò)展工藝約束下表現(xiàn)最優(yōu)，當(dāng)考慮擴(kuò)展工藝約束時(shí)，它的性能也較好。同時(shí)RR規(guī)則在不同擴(kuò)展工藝約束程度下性能也較好，而WINQ在擴(kuò)展工藝約束程度較高時(shí)表現(xiàn)一般，在無(wú)擴(kuò)展工藝約束時(shí)性能較好。此外，SPT規(guī)則在以工件總拖期為調(diào)度目標(biāo)下的性能較差。

圖1中列出了交貨期程度適度的情況下，各調(diào)度規(guī)則在四種不同擴(kuò)展工藝約束程度下的工件總拖期，從圖中可以看出，工件的擴(kuò)展工藝約束程度影響著工件總拖期，影響趨勢(shì)表現(xiàn)為隨著Ec的增大工件總拖期也隨著增大。同時(shí)，除SPT受擴(kuò)展工藝約束程度的影響較大外，其他規(guī)則均以合理的程度增長(zhǎng)且相應(yīng)的工件總拖期基本持平。

圖1 不同擴(kuò)展工藝約束下各調(diào)度規(guī)則的工件總拖期

選擇中等程度的擴(kuò)展工藝約束如Ec=3%時(shí)，此時(shí)4個(gè)不同c值下的各調(diào)度規(guī)則的RPI(T)如表2所示。從表中可以看出，在不同程度交貨期下，SOP均是最好的規(guī)則，RR規(guī)則次之。且不同c值下，SPT規(guī)則的性都能較差。

圖2反映出c值影響著T，影響趨勢(shì)表現(xiàn)為隨著c的增大T隨之減小。對(duì)于各種調(diào)度規(guī)則，T均隨著c值的增加而減小，即c值越大，T也越小。此時(shí)，SPT規(guī)則受交貨期松緊程度的影響也較大，其它規(guī)則的工件總拖期在不同c值下變化趨勢(shì)相似。

綜上所述，在考慮具有擴(kuò)展工藝約束和交貨期寬裕度的動(dòng)態(tài)車間作業(yè)調(diào)度問(wèn)題中，當(dāng)以工件總拖期為調(diào)度目標(biāo)時(shí)，SOP規(guī)則表現(xiàn)較好。且可知，擴(kuò)展工藝約束程度和交貨期寬裕程度同時(shí)影響調(diào)度規(guī)則的性能，即擴(kuò)展工藝約束程度越大工件總拖期越大；而當(dāng)交貨期寬裕程度增大時(shí)，工件總拖期減小。

表2 四種交貨期寬裕度系數(shù)值下各調(diào)度規(guī)則的工件總拖期的相對(duì)增長(zhǎng)程度

圖2 不同交貨期寬裕度系數(shù)下各調(diào)度規(guī)則的工件總拖期

3.3.2 基于拖期工件百分比的分析

與對(duì)工件總拖期的處理相同，我們?nèi)詫?duì)試驗(yàn)數(shù)據(jù)進(jìn)行兩方面的分析，即分別從擴(kuò)展工藝約束程度和交貨期寬裕程度進(jìn)行分析。

表3 四種擴(kuò)展工藝約束程度下不同調(diào)度規(guī)則的拖期工件百分比

從表3中可以看出，在中等程度的交貨期寬裕度下，各種調(diào)度規(guī)則的T%都保持在10%～30%之間。在每種參數(shù)配置下，按照拖期工件百分比遞增排列，即可得當(dāng)以拖期工件百分比T%為調(diào)度目標(biāo)時(shí)，性能較優(yōu)的規(guī)則。此時(shí)，SOP性能仍較好。

圖3列出了中等程度的交貨期寬裕度時(shí)四種不同Ec下，各調(diào)度規(guī)則下的拖期工件百分比T%隨擴(kuò)展工藝約束的變化。

圖3 不同擴(kuò)展工藝約束程度下各調(diào)度規(guī)則的拖期工件百分比

此時(shí)，不同擴(kuò)展工藝約束程度對(duì)調(diào)度規(guī)則性能的影響不像以工件總拖期為調(diào)度目標(biāo)時(shí)那樣明顯，可見(jiàn)在以拖期工件百分比為調(diào)度目標(biāo)時(shí)，擴(kuò)展工藝約束程度對(duì)調(diào)度規(guī)則的性能影響微小。但仍可看到SOP、RR和MDD的性能與其他規(guī)則相比性能較好。同時(shí)，從圖4中可看到在以T%為調(diào)度目標(biāo)時(shí)，交貨期寬裕程度對(duì)各調(diào)度規(guī)則性能的影響很明顯，且此時(shí)SOP的性能仍是最好的。

圖4 各調(diào)度規(guī)則在不同交貨期寬裕度系數(shù)下的T%

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

本文提出了一種新的優(yōu)先規(guī)則SOP，以考慮具有擴(kuò)展工藝約束的動(dòng)態(tài)Job-Shop調(diào)度問(wèn)題為模型，測(cè)試了該規(guī)則的性能，并分別在以工件總拖期和拖期工件百分比為調(diào)度目標(biāo)下，分析了擴(kuò)展工藝約束程度和交貨期寬裕程度對(duì)調(diào)度規(guī)則性能的影響。結(jié)果表明，所提出的優(yōu)先規(guī)則SOP在以工件總拖期和拖期工件百分比為調(diào)度目標(biāo)下性能都較好，具有較好的魯棒性。當(dāng)以工件總拖期為調(diào)度目標(biāo)時(shí)，擴(kuò)展工藝約束程度和交貨期寬裕程度同時(shí)影響調(diào)度規(guī)則的性能，即擴(kuò)展工藝約束程度越大工件總拖期越大；而當(dāng)交貨期寬裕程度增大時(shí)，工件總拖期減小。當(dāng)以拖期工件百分比為調(diào)度目標(biāo)時(shí)，交貨期寬裕程度在以拖期工件百分比為調(diào)度目標(biāo)時(shí)對(duì)各調(diào)度規(guī)則性能的影響很明顯，而擴(kuò)展工藝約束程度對(duì)調(diào)度規(guī)則的性能影響較小。

此外，關(guān)于各種調(diào)度規(guī)則性能測(cè)試的仿真試驗(yàn)在已有的文獻(xiàn)中并不少見(jiàn)，但在實(shí)際生產(chǎn)中，要從中選擇一個(gè)合適的規(guī)則并不容易，因?yàn)檎{(diào)度規(guī)則的數(shù)量龐大，而通常這些文獻(xiàn)都使用了不同的調(diào)度目標(biāo)來(lái)評(píng)價(jià)調(diào)度規(guī)則的性能，有不同的運(yùn)行條件并且有時(shí)會(huì)給出相互矛盾的結(jié)果，因此有必要建立專家系統(tǒng)以選擇和生成合適的調(diào)度規(guī)則以滿足實(shí)際生產(chǎn)中的調(diào)度目標(biāo)。

[1]Jonson S M.Optional two and three-stage production scheduling with set-up times included[J].Naval Research Logistics Quarterly,1954,1:64-68.

[2]Blazewicz J,Domschke W,Pesch E.The job shop scheduling problem: conventional and new techniques[J].European Journal of Operational Research,1996,93(1):1-33.

[3]刑文訓(xùn),謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京:清華大學(xué)出版社,2001.

[4]Haupt R.A survey of priority rule-based scheduling[J].OR Spektrum.1989,11:3-16.

[5]Vinod V,Sridharan R.Scheduling a dynamic job shop production system with sequence-dependent setups: An experimental study[J].Robotics and Computer-Integrated Manufacturing,2008,24(3):435-449.

[6]Binchao Chen, Timothy I.Matis.A flexible dispatching rule for minimizing tardiness in job shop scheduling[J].International Journal of Production Economics,2013,141(1):360-365.

[7]Eva Vallada, Rubén Ruiz, Gerardo Minella.Minimising total tardiness in the m-machine flowshop problem:A review and evaluation of heuristics and metaheuristics[J].Computers and Operations Research.2008,35(4):1350-1373.

[8]Baker K R, Bertrand J W M.A dynamic priority rule for scheduling against due-dates[J].Journal of Operations Management,1982,3(1):37-42.

[9]Conway R W, Maxwell WL, Miller LW.Theory of scheduling [J].Addison-Wesley, 1967, Reading, MA.

[10]Baker K R,Kennet J J.Job shop scheduling with modified due dates[J].Operations Management.1983,4:11-22.

[11]熊禾根,李建軍,孔建益,楊金堂,等.考慮工序相關(guān)性的動(dòng)態(tài)Jobshop調(diào)度問(wèn)題啟發(fā)式算法[J].機(jī)械工程學(xué)報(bào),2006,42(8):50-55.

[12]Rajendran C, Holthaus O.A comparative study of dispatching rules in dynamic flowshops and job shops [J].European Journal of Operational Research,1999,116(1):156-170.