2種新的單件裝配生產(chǎn)過程組合調(diào)度規(guī)則

李 明， 郭煥銀， 曹吉花

（宿州學(xué)院 機(jī)械與電子工程學(xué)院，安徽 宿州 234000）

在單件生產(chǎn)中，調(diào)度的困難程度遠(yuǎn)大于大批量生產(chǎn)方式。單件生產(chǎn)一般具有以下特點(diǎn)［1－3］：產(chǎn)品設(shè)計和制造周期長，生產(chǎn)計劃和控制有很強(qiáng)的自適應(yīng)性，設(shè)計方案通常根據(jù)客戶的具體需要而定；產(chǎn)品各部件之間的時序約束關(guān)系和成套性要求嚴(yán)格，瓶頸設(shè)備的能力和利用率是生產(chǎn)計劃與控制的關(guān)鍵環(huán)節(jié)。因此，以單件小批為主要生產(chǎn)模式的企業(yè)，車間的組織與控制方式對其生產(chǎn)調(diào)度有著更高的要求［4］，需要采用動態(tài)調(diào)度策略，其決策規(guī)則稱為調(diào)度規(guī)則（dispatching rule）。

以往的研究中提出了很多針對串形工藝路線產(chǎn)品的調(diào)度規(guī)則［5－8］。僅有少量的調(diào)度規(guī)則研究的是關(guān)于多級裝配產(chǎn)品，特別是關(guān)于單件裝配生產(chǎn)。文獻(xiàn)［9］提出了一種工序交付期規(guī)則（operation due date rule，簡稱ODD），該規(guī)則在關(guān)于產(chǎn)品拖期的各項性能指標(biāo)中均表現(xiàn)良好。文獻(xiàn)［10］提出了2種規(guī)則——ECT－FIFO規(guī)則和LF－ECT規(guī)則，擁有最小的LF（latest finishing time）的工序?qū)@得最高的優(yōu)先級；結(jié)果表明LF－ECT規(guī)則表現(xiàn)較好。文獻(xiàn)［11］對各種應(yīng)用在單件生產(chǎn)中的調(diào)度規(guī)則進(jìn)行了深入的性能分析，結(jié)果表明，最晚完成時間（the latest finish time，簡稱LFT）規(guī)則和改進(jìn)的最晚開始時間（latest start date，簡稱LSD）規(guī)則表現(xiàn)最好。文獻(xiàn)［12］研究了復(fù)雜定制產(chǎn)品生產(chǎn)的動態(tài)調(diào)度，每當(dāng)一個新的產(chǎn)品生產(chǎn)任務(wù)進(jìn)入系統(tǒng)后，由啟發(fā)式算法或者是進(jìn)化算法得到一個新的關(guān)于所有工序的調(diào)度；然而，這種方法僅僅在毎道加工或裝配工序所需的時間是確定性的情況下才是可行的。本文中提出的動態(tài)調(diào)度規(guī)則沒有這方面的限制，因為每個調(diào)度決定都是根據(jù)當(dāng)時的整個系統(tǒng)的狀態(tài)得出的。

1 提出的調(diào)度規(guī)則

本文提出的規(guī)則是基于工序的，即調(diào)度的產(chǎn)生是基于各裝配工序的優(yōu)先級。下面從3個因素考慮工序的優(yōu)先級。第1個因素是工序的最晚完成時間（LFT）。如前所述，如果一道工序的實際完成時間晚于它的LFT，那么這道工序所屬的產(chǎn)品將必然會拖期，所以LFT是描述一道工序緊急程度的關(guān)鍵因素。這也是一些研究［10－11］發(fā)現(xiàn)LFT規(guī)則表現(xiàn)很好的原因。第2個因素是這道工序所屬路徑上的剩余工序數(shù)量。如果2道工序擁有相同的或者是很接近的LFT，那么剩余工序數(shù)量較多的那道工序顯然應(yīng)該有較高的優(yōu)先級，因為剩余的工序多意味著有更多潛在的等待時間。第3個因素是這道工序是否在關(guān)鍵路徑上。關(guān)鍵路徑是一個產(chǎn)品的多個路徑中剩余加工時間最長的，所以執(zhí)行處于關(guān)鍵路徑上的工序?qū)ν苿诱麄€產(chǎn)品的完成有直接的作用。值得注意的是，關(guān)鍵路徑并不是靜態(tài)不變的，隨著制造過程的進(jìn)行，關(guān)鍵路徑會發(fā)生變化。

下面還有些表示可能會用到：LFTi——工序i的最晚完成時間；RPSi——工序i所在路徑上的剩余工序數(shù)量；MPT——所有工序的平均加工時間；CPi——一個二進(jìn)制變量，1表示工序i在關(guān)鍵路徑上，0表示工序i不在關(guān)鍵路徑上。

很明顯，擁有較小的LFT，較大的RPS，等于1的CP的工序?qū)碛休^高的優(yōu)先級。

1.1 ELFT規(guī)則

如果一道工序的完成時間晚于它的LFT，那么這道工序所屬的產(chǎn)品必然會拖期。如果完成時間非常接近LFT，意味著這道工序所在路徑上的其他工序的松弛時間就會非常短，所以對每一道工序來說，不僅要評定緊急程度，也要考慮在路徑上的剩余工序的緊急程度。容易得出如下結(jié)論：在關(guān)鍵路徑上并且有較小的LFT和較大的RPS的工序應(yīng)該有較高的緊急程度。工序j的優(yōu)先級ej可被描述如下：

其中，ω為工序j所在路徑上的毎道剩余工序的補(bǔ)償時間；τ為工序j處于關(guān)鍵路徑上的補(bǔ)償時間。因此ej可以理解為工序j期望的最晚完成時 間（expected latest finishing time，簡 稱ELFT）。如果工序j剩余的工序比較多，或者處于關(guān)鍵路徑上，期望它比實際的LFT更早些完成，那么就給它賦予更高的優(yōu)先級。明顯可以看出ej越小，工序j的優(yōu)先級越高。

1.2 LFT／RPS／CP規(guī)則

對于上文所述的3個因素（LFT、RPS、CP）采用不同的組織形式，可得到LFT／RPS／CP規(guī)則。其詳細(xì)步驟描述如下：

（1）如果一臺機(jī)器處于空閑狀態(tài)，而且有候選工序等待在這臺機(jī)器上執(zhí)行（不考慮等待工序），將這些候選工序按照LFT的升序排列。

（2）考慮已經(jīng)在步驟（1）中排好序的工序，對任意工序i滿足i≥1和LFTi＜LFT1＋MPT，這部分工序的集合命名為A。然后以相同的1／3的概率執(zhí)行步驟（3）、（4）或（5）去調(diào)整A 中工序的排列順序。

（3）保持A中工序的排序不變，并轉(zhuǎn)到步驟（6）。

（4）將A中的工序按照RPS的降序重新排列并轉(zhuǎn)到步驟（6）。

（5）按照CP的值將A分為2個子集，第1個子集包含A中CP為1的工序，第2個子集包含A中CP為0的子集。然后分別將2個子集的工序按照LFT的升序重新排列，轉(zhuǎn)到步驟（6）。

（6）選擇A中排在第1位的工序并執(zhí)行。

2 數(shù)值仿真實驗

在Visual Studio 2003環(huán)境下開發(fā)了單件裝配生產(chǎn)過程仿真程序，考慮如下單件裝配生產(chǎn)車間：有20個工作站，每個工作站有1臺機(jī)器。每個產(chǎn)品包含20個裝配工序，分別在這20臺機(jī)器上執(zhí)行。工序執(zhí)行時間服從［10，30］的均勻分布。產(chǎn)品隨機(jī)到達(dá)，到達(dá)間隔時間服從參數(shù)為23個時間單位的負(fù)指數(shù)分布。數(shù)值試驗表明在這個參數(shù)下，在制品水平可達(dá)到穩(wěn)定狀態(tài)并且各機(jī)器的負(fù)載水平較高。新到產(chǎn)品的交付期由關(guān)鍵路徑長度（li）、寬容系數(shù)（c）和產(chǎn)品到達(dá)時間（ai）決定，即產(chǎn)品i的交付期di＝ai＋cli。試驗中取c＝2。試驗中將生產(chǎn)500個產(chǎn)品，除去鋪線的50個和收線的50個，統(tǒng)計中間400個產(chǎn)品的拖期產(chǎn)品數(shù)和總拖期時間，作為評判調(diào)度規(guī)則效率的標(biāo)準(zhǔn)。

2.1 ELFT規(guī)則中參數(shù)的影響

在ELFT規(guī)則中有ω和τ2個參數(shù)。

當(dāng)ω＝0，τ＝0時，ELFT規(guī)則也就是LFT規(guī)則，拖期產(chǎn)品數(shù)為88個，總拖期時間為2161個時間單位。調(diào)整這2個參數(shù)的值，在不同參數(shù)的ELFT規(guī)則下對同一組產(chǎn)品進(jìn)行生產(chǎn)過程仿真，得到如圖1所示的試驗結(jié)果。

圖1 不同參數(shù)下的拖期產(chǎn)品數(shù)與總拖期時間

從圖1中可以看出，在ω∈［0，3］和τ∈［0，27］時，ELFT規(guī)則要優(yōu)于LFT規(guī)則。其中在區(qū)間ω∈［0，3］，τ∈［12，24］表現(xiàn)最為優(yōu)越。但是，當(dāng)ω＞4時，此規(guī)則的效率就開始降低，甚至比LFT規(guī)則還要差。根據(jù)仿真實驗，τ的值可選為工序的平均時間，而ω的值可選為工序的平均時間／工序數(shù)。

2.2 提出規(guī)則與其他規(guī)則的比較

下面將本文提出的動態(tài)調(diào)度規(guī)則的效率，與其他裝配生產(chǎn)動態(tài)調(diào)度研究中表現(xiàn)較好的規(guī)則進(jìn)行比較。由于文獻(xiàn)［10］提出的ODD（operation due date）規(guī)則實際上只是LSD（the latest starting date）規(guī)則的一種，而文獻(xiàn)［12］中提出的refined－LSD是一個“try－every－rule”方法，即要嘗試規(guī)則的參數(shù)取值，經(jīng)比較再選取最好的那個，這個方法現(xiàn)實意義不大而且結(jié)果和LSD規(guī)則相比也幾乎相同，所以選取文獻(xiàn)［10－12］的其他幾個規(guī)則來比較，包括LFT（the latest finishing time）規(guī)則、EDD（the earliest due date）規(guī)則、LSD 規(guī)則、ECT（the earliest completing time）規(guī)則。其中EDD和ECT都是基于產(chǎn)品的調(diào)度規(guī)則，即產(chǎn)品每道工序的優(yōu)先級都是根據(jù)產(chǎn)品的某個性質(zhì)來決定的，比如根據(jù)產(chǎn)品的交付期；其他幾個，包括本文提出的2個都是基于工序的調(diào)度規(guī)則。取10組產(chǎn)品分別用這幾種規(guī)則進(jìn)行調(diào)度，比較拖期產(chǎn)品數(shù)和總拖期時間，試驗結(jié)果見表1和表2所列。表中L／R／C規(guī)則表示LFT／RPS／CP規(guī)則。

表1 各規(guī)則下拖期產(chǎn)品數(shù)比較

表2 各種規(guī)則下總拖期時間比較

從表1和表2可以看出，在單件裝配生產(chǎn)的動態(tài)調(diào)度過程中，在減少拖期產(chǎn)品數(shù)和減少總拖期時間方面，基于工序的調(diào)度規(guī)則要明顯地優(yōu)于基于產(chǎn)品的調(diào)度規(guī)則（ECT、EDD）。

此外，所提出的2種規(guī)則與另外2種基于工序的動態(tài)調(diào)度規(guī)則（LSD、LFT）相比，能更加有效地減少產(chǎn)品的拖期情況。2種LFT＋RPS＋CP規(guī)則調(diào)度下拖期產(chǎn)品數(shù)分別比LFT規(guī)則少6.3%和3.0%，分別比 LSD 規(guī)則少10.3%和7.1%；在減少總拖期時間方面也表現(xiàn)較好：LFT／RPS／CP規(guī)則和ELFT規(guī)則總拖期時間比使用LFT規(guī)則時分別少了9.2%和4.3%，比使用LSD規(guī)則時分別少了12.9%和8.2%。由此可見所提出的這2種動態(tài)調(diào)度規(guī)則能更有效地減少單件裝配生產(chǎn)過程中的拖期產(chǎn)品數(shù)和總拖期時間。

3 結(jié)束語

本文研究了在單件裝配生產(chǎn)環(huán)境中的動態(tài)調(diào)度問題，每個產(chǎn)品都有自己獨(dú)特的樹形工藝路線、工序時間、交付期，而且隨機(jī)到達(dá)且符合負(fù)指數(shù)分布。本文提出了2種可用于上述情況的動態(tài)調(diào)度規(guī)則：ELFT規(guī)則和LFT／RPS／CP規(guī)則。為了檢驗這些新規(guī)則的性能表現(xiàn)，開發(fā)了單件裝配生產(chǎn)仿真軟件并做了大量的數(shù)值仿真試驗。試驗結(jié)果表明：ELFT規(guī)則的參數(shù)取值對規(guī)則效率的影響很大，可以根據(jù)仿真試驗的結(jié)果經(jīng)驗性地將τ的值選為工序的平均時間，而ω的值可選為工序的平均時間／工序數(shù)；基于工序的調(diào)度規(guī)則表現(xiàn)遠(yuǎn)遠(yuǎn)優(yōu)于基于產(chǎn)品的調(diào)度規(guī)則；所提出的2種規(guī)則與LSD規(guī)則和LFT規(guī)則相比，能更加有效地減少產(chǎn)品的拖期情況。

［1］Tu Y L.Real－time scheduling and control of one－of－a－kind production［J］.Production Planning ＆ Control，1997，8（7）：701－710.

［2］Kuhlmann T H.A revolving planning and control system［C］／／Proceedings of New Approaches Towards One－of－akind Production，Bremen，Germany，1991：95－112.

［3］Hirsch B E，Kuhlmann T H.Harmonization of decentralized，autonomous production areas［C］／／Proceedings of IFAS CIM in Process and Manufacturing Industries，Espoo，F(xiàn)inland，1992：69－74.

［4］牛興華.一種獨(dú)立制造島作業(yè)計劃的編制方法［J］.天津理工學(xué)院學(xué)報，1999，15（2）：18－23.

［5］Chiang T C，F(xiàn)u L C.Using dispatching rules for job shop scheduling with due date－based objectives［C］／／Proceedings of the 2006IEEE International Conference on Robotics and Automation，Orlando，F(xiàn)lorida，2006：1426－1431.

［6］Dominic P D D，Kaliyamoorthy S，Kumar M S.Efficient dispatching rules for dynamic job shop scheduling［J］.International Journal of Advanced Manufacturing Technology，2004，24（1／2）：70－75.

［7］Chiang T C，F(xiàn)u L C.Solving the FMS scheduling problem by critical ratio－based heuristics and the genetic algorithm［C］／／Proceeding of the 2004IEEE Conference on Robotics and Automation，Vol 3，New Orleans，LA，USA，April 26－May 1，2004：3131－3136.

［8］王?，帲Y增強(qiáng)，葛茂根.基于規(guī)則組合的Job Shop多目標(biāo)柔性調(diào)度方法 ［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2010，33（1）：14－18.

［9］Reeja M K，Rajendran C.Dispatching rules for scheduling in assembly jobshops，part 1［J］.International Journal of Production Research，2000，38（9）：2051－2066.

［10］Mohanasundaram K M，Natarajan K，Viswanathkumar G，et al.Scheduling rules for dynamic shops that manufacture multi－level jobs ［J］.Computers and Industrial Engineering，2002，44（1）：119－131.

［11］Choi B K，You N K.Dispatching rules for dynamic scheduling of one－of－a－kind production［J］.International Journal of Computer Integrated Manufacturing，2006，19（4）：383－392.

［12］Hicks C，Song D P，Earl C F.Product due date assignment for complex assemblies［J］.International Journal of Production Economics，2002，76（3）：243－256.