李 平 唐秋華 夏緒輝 陳平和

1.武漢科技大學(xué)，武漢，430081 2.湖北理工學(xué)院，黃石，435000 3.武漢神龍汽車公司技術(shù)中心，武漢，430056

0 引言

由于多種產(chǎn)品間存在巨大差異，故在其大規(guī)?；旌仙a(chǎn)過(guò)程中，常出現(xiàn)訂單頻繁異動(dòng)、操作時(shí)間調(diào)整、機(jī)器出現(xiàn)故障等各種不確定事件。為應(yīng)對(duì)上述不確定情形，生產(chǎn)調(diào)度中常用措施有實(shí)時(shí)調(diào)度、預(yù)測(cè)調(diào)度和重調(diào)度等［1－2］。

實(shí)時(shí)調(diào)度是在當(dāng)前任務(wù)完成后，根據(jù)設(shè)備可用情況，在當(dāng)前待完成任務(wù)集中實(shí)時(shí)地選擇下一任務(wù)［3］。預(yù)測(cè)調(diào)度是在生產(chǎn)調(diào)度前預(yù)先估計(jì)可能發(fā)生的意外和擾動(dòng)，在編制調(diào)度方案時(shí)預(yù)先設(shè)置一定的冗余時(shí)間，當(dāng)生產(chǎn)過(guò)程中出現(xiàn)不確定因素時(shí)，通過(guò)調(diào)整冗余時(shí)間而主動(dòng)吸收計(jì)劃內(nèi)的不確定擾動(dòng)，按照預(yù)定調(diào)度方案完成生產(chǎn)任務(wù)［4－5］。比較而言，實(shí)時(shí)調(diào)度強(qiáng)調(diào)了不確定事件發(fā)生后的響應(yīng)速度，這種調(diào)度方法靈活、易于調(diào)整，但難以關(guān)注整體生產(chǎn)效率，不可能實(shí)現(xiàn)全局最優(yōu)。預(yù)測(cè)調(diào)度的主要目標(biāo)是維護(hù)生產(chǎn)過(guò)程的穩(wěn)定性，有利于在某些不確定事件發(fā)生后，保障生產(chǎn)有序進(jìn)行，但冗余時(shí)間大小不好確定，設(shè)置過(guò)小滿足不了應(yīng)付擾動(dòng)的要求，設(shè)置過(guò)大又易造成生產(chǎn)浪費(fèi)和效率低下。

不同于實(shí)時(shí)調(diào)度及預(yù)測(cè)調(diào)度，重調(diào)度是在擾動(dòng)發(fā)生后，以調(diào)整量最小或生產(chǎn)效率最大等為目標(biāo)重新編制調(diào)度方案，對(duì)生產(chǎn)進(jìn)行局部或全局重新調(diào)度［6－7］。由于重調(diào)度是在擾動(dòng)發(fā)生后的系統(tǒng)行為，故又常被稱為反應(yīng)調(diào)度。重調(diào)度既避免了實(shí)時(shí)調(diào)度中不考慮全局最優(yōu)的缺陷，又避免了預(yù)測(cè)調(diào)度中冗余時(shí)間的浪費(fèi)，是一種兼顧全局和效率的折中方案。

目前，關(guān)于重調(diào)度的研究主要集中在單臺(tái)機(jī)器、并行機(jī)器、流水車間（Flow Shop）和作業(yè)車間（Job Shop）的重調(diào)度方法、重調(diào)度對(duì)動(dòng)態(tài)制造系統(tǒng)性能的影響等方面［8－9］。Parviz等［10］研究了在時(shí)間沖突情況下的柔性作業(yè)車間重調(diào)度方法，Sabuncuoglu等［11］探索了機(jī)器可靠性較差條件下的柔性作業(yè)車間重調(diào)度，李鐵克等［12］研究了在機(jī)器故障情況下混合流水車間的重調(diào)度。上述重調(diào)度方法都只能應(yīng)對(duì)單一類型的擾動(dòng)，缺乏應(yīng)對(duì)多種擾動(dòng)類型的能力。

為此，本文以柔性作業(yè)車間為研究對(duì)象，探索對(duì)多種擾動(dòng)具有自適應(yīng)能力的重調(diào)度框架和算法，以期快速普適地求解重調(diào)度問(wèn)題。

1 具有自適應(yīng)能力的作業(yè)車間重調(diào)度

1.1 車間重調(diào)度問(wèn)題描述

常見(jiàn)作業(yè)車間調(diào)度問(wèn)題可以描述為：給定一組任務(wù)、各任務(wù)的工藝順序、各任務(wù)中每道工序的可選機(jī)器集及其在這些機(jī)器上的加工時(shí)間，求一個(gè)調(diào)度方案，使所有任務(wù)的最大完工時(shí)間最小。

生產(chǎn)過(guò)程中不確定事件的發(fā)生是不可避免的，在作業(yè)車間中常見(jiàn)擾動(dòng)類型有加工時(shí)間變動(dòng)、工序優(yōu)先關(guān)系改變、機(jī)器可用性變更等。由于生產(chǎn)過(guò)程中不確定事件類型繁多，重調(diào)度時(shí)須強(qiáng)調(diào)3個(gè)方面［13－16］：①對(duì)各種不同類型的擾動(dòng)都具有自適應(yīng)的能力；②重調(diào)度的計(jì)算時(shí)間要短，反應(yīng)速度要快；③重調(diào)度后調(diào)度方案的性能損失要小。

圖1所示的作業(yè)車間重調(diào)度示意圖中，包含3臺(tái)機(jī)器、3個(gè)任務(wù)，每個(gè)任務(wù)有2道工序，其中1（1）表示1號(hào)工件的第1道工序。假設(shè)［0，t）時(shí)間段內(nèi)生產(chǎn)正常，t時(shí)刻出現(xiàn)擾動(dòng)。預(yù)計(jì)產(chǎn)生新的調(diào)度方案需耗費(fèi)計(jì)算時(shí)間為Δt，作如下規(guī)定：①只要所在機(jī)器未發(fā)生故障，在［0，t＋Δt］時(shí)刻內(nèi)開(kāi)始的任何工序都不作調(diào)整，避免擾亂現(xiàn)有生產(chǎn)秩序。例如1號(hào)工件的第1道工序1（1），2號(hào)工件的第1及第2道工序即2（1）和2（2），在t時(shí)刻之前它們已經(jīng)開(kāi)始加工，在加工它們的機(jī)器不存在故障前提下，允許它們繼續(xù)完成任務(wù)，不受新調(diào)度方案影響。②從t＋Δt時(shí)刻，其他工序遵照新調(diào)度方案中加工順序和機(jī)器分配的安排。例如1號(hào)工件的第2道工序和3號(hào)工件的第1及第2道工序須遵照重調(diào)度方案執(zhí)行。

圖1 重調(diào)度示意圖

1.2 擾動(dòng)及參數(shù)異動(dòng)分析

根據(jù)上述規(guī)定，啟用重調(diào)度的首要判定內(nèi)容是：在所在機(jī)器未發(fā)生故障的前提下，t＋Δt時(shí)刻有哪些工序尚未開(kāi)始；已經(jīng)開(kāi)始加工，但因所在機(jī)器發(fā)生故障而無(wú)法繼續(xù)運(yùn)行的工序；針對(duì)上述工序集合的變更，重調(diào)度系統(tǒng)中需要更新哪些參數(shù)，以保證該系統(tǒng)對(duì)各種擾動(dòng)類型都具有適應(yīng)能力。

據(jù)此將常見(jiàn)擾動(dòng)類型分成訂單異動(dòng)、操作延時(shí)和機(jī)器故障三大類。在出現(xiàn)緊急插單或訂單取消時(shí)，在受影響工序集中增加或減少新的任務(wù)、補(bǔ)充或取消上述任務(wù)的可用機(jī)器約束；針對(duì)操作延時(shí)的情況下，采用固定時(shí)間間隔檢查的方法，根據(jù)測(cè)定結(jié)果修正操作時(shí)間；針對(duì)機(jī)器出現(xiàn)故障的情況，在各工件工序的可用機(jī)器集合中刪除出現(xiàn)故障的機(jī)器，形成新的可用機(jī)器約束，同時(shí)在操作時(shí)間表中作同步更新，詳細(xì)內(nèi)容如表1所示。

表1 受影響工序及參數(shù)更新

在執(zhí)行調(diào)度前通過(guò)更新操作時(shí)間、機(jī)器約束，可確保算法適用于不同訂單變動(dòng)、操作延時(shí)及機(jī)器故障等不確定擾動(dòng)發(fā)生的情形。

需要注意的是，機(jī)器約束的確定是操作時(shí)間更改的前提條件，因此，在兩種或兩種以上擾動(dòng)同時(shí)發(fā)生時(shí)，按“先機(jī)器約束后操作時(shí)間”的原則進(jìn)行系統(tǒng)參數(shù)更新。例如在訂單異動(dòng)和操作延時(shí)兩種擾動(dòng)同時(shí)發(fā)生時(shí)，因訂單異動(dòng)有可能涉及機(jī)器約束的改變，所以先按訂單異動(dòng)規(guī)則更新機(jī)器約束和操作時(shí)間，再按操作延時(shí)規(guī)則進(jìn)一步更新操作時(shí)間。

1.3 作業(yè)車間自適應(yīng)重調(diào)度框架

建立在表1基礎(chǔ)上的面向作業(yè)車間的重調(diào)度算法需要具有以下幾種能力：

（1）擾動(dòng)不可避免，但在指定時(shí)段內(nèi)擾動(dòng)可能發(fā)生，也可能不會(huì)發(fā)生，故要求算法在無(wú)擾動(dòng)、有擾動(dòng)兩種情況下都得能到近優(yōu)解，以減少生產(chǎn)損失；

（2）擾動(dòng)類型的多樣化需要算法具有一種自適應(yīng)能力，可處理各種類型的擾動(dòng)影響。結(jié)合表1內(nèi)容，需要算法中存在確定受影響工序、系統(tǒng)參數(shù)更新兩個(gè)模塊，通過(guò)模塊內(nèi)參數(shù)的變動(dòng)適應(yīng)外在環(huán)境的改變。

為此，本文提出圖2所示的作業(yè)車間自適應(yīng)重調(diào)度流程，在遺傳算法基礎(chǔ)上通過(guò)利用參數(shù)、編碼、算子等的重新設(shè)計(jì)，實(shí)現(xiàn)不同擾動(dòng)類型條件下的作業(yè)車間重調(diào)度。該算法總流程如下：

圖2 作業(yè)車間自適應(yīng)重調(diào)度流程

（1）初始化系統(tǒng)參數(shù)，包括工件數(shù)、工序數(shù)、機(jī)器數(shù)、加工時(shí)間等，產(chǎn)生預(yù)調(diào)度方案。

（2）依照預(yù)調(diào)度方案進(jìn)行生產(chǎn)，按照固定間隔時(shí)間檢查結(jié)果及擾動(dòng)類型提醒，決定是否重調(diào)度。①如果發(fā)生擾動(dòng)，確定擾動(dòng)類型，轉(zhuǎn)步驟（3）；②如果沒(méi)有擾動(dòng)發(fā)生，按預(yù)調(diào)度方案繼續(xù)生產(chǎn)。

（3）確定受擾動(dòng)影響的工序集合，更新系統(tǒng)參數(shù)。

（4）利用下述算法生成新的調(diào)度方案，更新預(yù)調(diào)度方案，轉(zhuǎn)步驟（2）。

2 基于雙層編碼的重調(diào)度算法設(shè)計(jì)

從上述內(nèi)容可知，通過(guò)調(diào)整受影響工序集、更新相應(yīng)系統(tǒng)參數(shù)，所調(diào)度對(duì)象便可自動(dòng)調(diào)整，調(diào)度對(duì)象的屬性如操作時(shí)間等也已經(jīng)自動(dòng)變化，所提出算法既適用于靜態(tài)調(diào)度，也適用于動(dòng)態(tài)重調(diào)度。從機(jī)理來(lái)說(shuō)，動(dòng)態(tài)重調(diào)度已可順利實(shí)現(xiàn)，算法核心就是促使解空間信息中既要包含各工序的順序，還應(yīng)包含該工序所分配的機(jī)器信息。

同時(shí)，由于重調(diào)度過(guò)程中反應(yīng)時(shí)間Δt非常重要，如果Δt過(guò)大，則對(duì)整個(gè)加工過(guò)程影響很大，例如會(huì)推遲完工時(shí)間并增加閑置時(shí)間等，因此，計(jì)算新的調(diào)度方案應(yīng)采取速度較快的算法。包括遺傳算法在內(nèi)的啟發(fā)式算法能夠在較短時(shí)間內(nèi)求得調(diào)度問(wèn)題的近似最優(yōu)解，故本文考慮在重調(diào)度中使用遺傳算法進(jìn)行計(jì)算。

算法求解過(guò)程包括編碼、生成初始解、對(duì)種群進(jìn)行遺傳操作、在迭代過(guò)程中不斷改善種群結(jié)構(gòu)和解的性能，最終得到最優(yōu)解。具體實(shí)施方法敘述如下。

為了簡(jiǎn)化問(wèn)題的描述，對(duì)本文中出現(xiàn)的符號(hào)作如下約定：i＝1，2，…，I，為工件序號(hào)，I為工件總數(shù)；j＝1，2，…，Ji，為工藝序號(hào)，Ji為第i個(gè)工件的工序數(shù)為總工序個(gè)數(shù)；m＝1，2，…，M，為機(jī)器編號(hào)，M為機(jī)器總數(shù)；Kij為第i個(gè)工件的第j道工序的可用機(jī)器總數(shù)為第i個(gè)工件的第j道工序的可用機(jī)器集合；1，2，…，Kij為機(jī)器可用集合中的序號(hào)為機(jī)器的實(shí)際編號(hào)為第i個(gè)工件的第j道工序在可選機(jī)器集Φij中的機(jī)器上的加工時(shí)間集合為第i個(gè)工件的第j道工序的結(jié)束時(shí)間；Mt（s）m為第m臺(tái)機(jī)器上進(jìn)行的第s項(xiàng)操作的結(jié)束時(shí)間。

2.1 雙層遺傳編碼和初始化

為同時(shí)描述工件的加工順序與分配機(jī)器兩種信息，采用圖3所示的雙層編碼結(jié)構(gòu)：第一層為基于工件工序的編碼，稱為工序碼；第二層為基于可用機(jī)器選擇的編碼，稱為機(jī)器碼，總編碼長(zhǎng)度為2N。在給定的可用機(jī)器集和對(duì)應(yīng)加工時(shí)間表的基礎(chǔ)上，每一個(gè)雙層編碼對(duì)應(yīng)一個(gè)調(diào)度方案，描述各工件每道工序所選擇的機(jī)器，以及各機(jī)器上進(jìn)行工件加工的先后順序。設(shè)其中一個(gè)染色體為

其中，工序碼xn（xn∈ ｛1，2，…，I｝）對(duì)應(yīng)于被加工的工件號(hào)，某工件號(hào)xn在工序碼中第i次出現(xiàn)表示該工件的第i道工序，而某一工件號(hào)在工序碼中出現(xiàn)的累計(jì)次數(shù)即為該工件的工序數(shù)。機(jī)器碼yn（yn∈ ｛1，2，…，Kij｝）是各工序可用機(jī)器集內(nèi)各元素的重新編號(hào)（圖3），旨在減少計(jì)算過(guò)程對(duì)系統(tǒng)運(yùn)行空間的需求，加快運(yùn)行速度。注意，每一個(gè)xn對(duì)應(yīng)一個(gè)集合｛y1，…yn…，yN｝，根據(jù)集合｛x1，…xn…，xN｝與｛y1，…yn…，yN｝的對(duì)應(yīng)關(guān)系，即可確定每個(gè)工件各道工序的執(zhí)行機(jī)器。

圖3 雙層染色體編碼示意圖

在圖3所示案例中，某作業(yè)車間有3臺(tái)機(jī)器，需加工2個(gè)工件，且各工件均含有2道工序。各工件每道工序的可用機(jī)器表及加工時(shí)間如圖3所示。

假設(shè)某個(gè)染色體編碼為（1，2，1，2，1，2，2，1），其中前四位（1，2，1，2）為工位碼，直接確定了2個(gè)工件共4道工序的執(zhí)行順序：工件1工序1、工件2工序1、工件1工序2、工件2工序2。編碼后四位（1，2，2，1）為機(jī)器碼，聯(lián)立可用機(jī)器集共同確定執(zhí)行各工序的機(jī)器為：工件1的第1、2道工序分別由機(jī)器1和3加工，工件2的第1、2道工序分別由機(jī)器3和2加工。該染色體編碼對(duì)應(yīng)的加工過(guò)程甘特圖見(jiàn)如圖4。

圖4 遺傳編碼與加工過(guò)程的對(duì)應(yīng)

2.2 解碼方法和適應(yīng)度函數(shù)設(shè)計(jì)

假設(shè)根據(jù)調(diào)度方案的排序，第i個(gè)工件第j道工序恰好被安排為第m臺(tái)機(jī)器上的第s個(gè)任務(wù)，則有如下公式：

即在上述的假設(shè)中，第i個(gè)工件的第j道工序的完成時(shí)間等于第i個(gè)工件第j－1道工序的完成時(shí)間加上第m臺(tái)機(jī)器上第s－1個(gè)任務(wù)的完成時(shí)間的最大值，或第i個(gè)工件第j道工序在所分配機(jī)器上的加工時(shí)間。 為了表達(dá)形式的方便，記分別表示第i個(gè)工件與第m臺(tái)機(jī)器的可開(kāi)始時(shí)間。

2.3 選擇和交叉操作設(shè)計(jì)

選擇操作采用輪盤賭的方法依概率選擇適應(yīng)度較強(qiáng)的染色體參與遺傳操作。概率的計(jì)算由適度函數(shù)值決定，表達(dá)式如下：

交叉操作首先從種群中隨機(jī)選出兩個(gè)染色體，對(duì)染色體的第一層隨機(jī)選擇交叉點(diǎn)進(jìn)行交叉。交叉操作分為兩步：參與交叉的兩個(gè)染色體的第一層在交叉點(diǎn)前后互換基因；對(duì)交叉后的染色體進(jìn)行局部調(diào)整，調(diào)整的原則為使其所表達(dá)的工件數(shù)及工序數(shù)與問(wèn)題條件相符。如圖5中的染色體中第一層基因位置里1、2、3各出現(xiàn)了3次，表示對(duì)應(yīng)的問(wèn)題是有3個(gè)工件，每個(gè)工件有3道工序的Job Shop問(wèn)題。但交叉后，出現(xiàn)了有的工件工序變多，有的工件工序變少的問(wèn)題，這時(shí)調(diào)整的方法是從工序較多的工件號(hào)中隨機(jī)抽取一個(gè)使之變成工序變少的工件號(hào)，并從該工件可選機(jī)器中選擇一個(gè)。圖5演示了一個(gè)具體的交叉操作過(guò)程。圖6為調(diào)整步驟示意。

圖5 工序碼交叉

2.4 變異算子設(shè)計(jì)

變異操作分為工序碼變異和機(jī)器碼變異兩步。工序碼變異首先隨機(jī)選擇兩個(gè)變異位置，然后將第一層工序碼和第二層機(jī)器碼的對(duì)應(yīng)位置上的基因進(jìn)行互換。圖7演示了一個(gè)具體的工序碼變異操作過(guò)程。

圖6 工序碼調(diào)整

圖7 工序碼的變異設(shè)計(jì)

機(jī)器碼變異是在第二層機(jī)器碼中隨機(jī)選擇一個(gè)變異位置，將該位置對(duì)應(yīng)的可選機(jī)器序號(hào)集中隨機(jī)選擇一個(gè)序號(hào)，替換原序號(hào)值，如圖8所示。

圖8 機(jī)器碼的變異設(shè)計(jì)

2.5 種群的精英保留策略

在本算法中采取精英保留策略，即用當(dāng)前代中適應(yīng)度值最好的個(gè)體替換適應(yīng)度值最差的個(gè)體，在進(jìn)行遺傳步驟的時(shí)候最好個(gè)體不僅以更大的概率參與遺傳操作，并且直接進(jìn)入下一代種群。

3 算例分析

給定具有6個(gè)工件、每個(gè)工件有6道工序、可用機(jī)器數(shù)為10的某作業(yè)車間調(diào)度問(wèn)題。已知各工件每道工序的可選機(jī)器集合（如表2中中括號(hào)所示），及其在對(duì)應(yīng)機(jī)器上的加工時(shí)間（對(duì)應(yīng)于表3中中括號(hào)內(nèi)容）。

表2 各工序可選機(jī)器表

表3 各工序加工時(shí)間表

采用MATLAB編碼編制完成上述遺傳算法。根據(jù)本問(wèn)題的規(guī)模和計(jì)算復(fù)雜度，通過(guò)多次實(shí)驗(yàn)對(duì)比，在綜合考慮計(jì)算效率和求解時(shí)間的前提下，設(shè)置遺傳代數(shù)為50、選擇率為0.8、交叉率為0.8、工序碼變異率和機(jī)器碼變異率均為0.1，運(yùn)行該算法得到遺傳算法迭代圖和預(yù)調(diào)度方案分別如圖9、圖10所示。

圖9 遺傳算法迭代圖

圖10 預(yù)調(diào)度方案甘特圖

從圖9中可以看出，算法的收斂性較好，從第30代開(kāi)始種群的最優(yōu)解就穩(wěn)定在47s。在最優(yōu)預(yù)調(diào)度方案的甘特圖中，表示工序的矩形中的數(shù)字i0j表示該矩形對(duì)應(yīng)于第i個(gè)工件的第j道工序。從圖中可見(jiàn)所求最大完工時(shí)間的較優(yōu)值為47s，在10臺(tái)機(jī)器中設(shè)備運(yùn)用率最高的為機(jī)器5，最后完工的工件是6號(hào)，由于201和303占用了機(jī)器4號(hào)和7號(hào)，完工時(shí)間不可能更為提前。算法的運(yùn)行時(shí)間為3s，低于預(yù)先估計(jì)的1min，顯示該算法效率較高。

當(dāng)不確定發(fā)生時(shí)，以機(jī)器故障為例考慮如下情形的擾動(dòng)：假設(shè)在生產(chǎn)進(jìn)行到第14min時(shí)編號(hào)為9的機(jī)器突然發(fā)生意外，以至于在后續(xù)的生產(chǎn)過(guò)程中無(wú)法繼續(xù)工作，求新的調(diào)度方案，新調(diào)度方案的計(jì)算時(shí)間預(yù)設(shè)為1min。根據(jù)本文中前述的原則可以確定受影響的任務(wù)工序集合與更新后的參數(shù)。發(fā)生擾動(dòng)后，需要在新的初始條件下重新計(jì)算后續(xù)工件工序的調(diào)度方案。根據(jù)本例中9號(hào)機(jī)器發(fā)生故障的情況，更新工序可選機(jī)器表和工序加工時(shí)間表的原則為：未完成工序中涉及第9臺(tái)機(jī)器的加工時(shí)間改為無(wú)窮大。發(fā)生擾動(dòng)后的工件可選機(jī)器和在各機(jī)器上的加工時(shí)間如表4和表5所示。其中，“※”表示在重調(diào)度中不需要考慮的工件工序的機(jī)器可用情況及加工時(shí)間；“inf”表示加工時(shí)間為無(wú)窮大。

表4 9號(hào)機(jī)發(fā)生故障后的可選機(jī)器更新表

表5 9號(hào)機(jī)發(fā)生故障后工序加工時(shí)間更新表

在此基礎(chǔ)上，計(jì)算出后續(xù)工件工序的最佳調(diào)度方案，新調(diào)度方案中的完工時(shí)間為55s，此案例中新調(diào)度方案的實(shí)際計(jì)算時(shí)間為3s，低于預(yù)先估計(jì)的反應(yīng)時(shí)間，計(jì)算得到的新調(diào)度方案如圖11所示。

圖11 9號(hào)機(jī)故障發(fā)生后的重調(diào)度方案

在本例中，通過(guò)適應(yīng)性的雙層編碼遺傳算法解決了機(jī)器故障情形下的重調(diào)度問(wèn)題，得到了Job Shop問(wèn)題在擾動(dòng)情況下的最優(yōu)解，對(duì)于其他類型的擾動(dòng)，可以使用同樣方法進(jìn)行重調(diào)度方案

本文在對(duì)400個(gè)不同規(guī)模的Job Shop重調(diào)度問(wèn)題進(jìn)行仿真運(yùn)算的基礎(chǔ)上試驗(yàn)和分析所應(yīng)用的適應(yīng)性算法的效率，仿真問(wèn)題中的工件個(gè)數(shù)和工序數(shù)在6至25之間自由組合，每道工序可選擇的機(jī)器數(shù)設(shè)為2，即問(wèn)題的規(guī)模介于72至1250之間。運(yùn)算的結(jié)果如圖12及圖13所示，從圖12中可以看出所有問(wèn)題的重調(diào)度運(yùn)算時(shí)間均小于80s，其中絕大部分的時(shí)間小于60s。圖13為運(yùn)算時(shí)間的等值分布圖，從圖中可以看出不同規(guī)模問(wèn)題的運(yùn)算時(shí)間分布，時(shí)間大于60s的問(wèn)題占問(wèn)題總數(shù)的2%以下。因此，本文中所設(shè)置的1min反應(yīng)時(shí)間對(duì)于大部分Job Shop問(wèn)題的重調(diào)度來(lái)說(shuō)可行。的求解。

Job Shop問(wèn)題的規(guī)?？捎蓛蓚€(gè)因素確定：總工序的個(gè)數(shù)和每道工序可選擇的機(jī)器數(shù)。在不失一般性的情況下，可按照如下公式來(lái)定義Job Shop問(wèn)題的規(guī)模：

圖12 運(yùn)算時(shí)間分布圖

圖13 運(yùn)算時(shí)間等高線圖（s）

4 結(jié)論

重調(diào)度通過(guò)重新編制調(diào)度方案來(lái)應(yīng)對(duì)不確定擾動(dòng)，具有同時(shí)保障全局較優(yōu)和生產(chǎn)穩(wěn)定的能力。本文以柔性作業(yè)車間為研究對(duì)象，提出了具有自適應(yīng)能力的重調(diào)度框架及算法。

仿真實(shí)驗(yàn)證明，以各工件每道工序的可用機(jī)器集及相應(yīng)加工時(shí)間為系統(tǒng)參數(shù)，可有效表征柔性作業(yè)車間調(diào)度中常見(jiàn)擾動(dòng)類型；動(dòng)態(tài)調(diào)整上述系統(tǒng)參數(shù)，即可適應(yīng)生產(chǎn)過(guò)程中訂單異動(dòng)、操作延時(shí)和機(jī)器故障等3種類型擾動(dòng)；基于雙層編碼的遺傳算法具有簡(jiǎn)單和高效的特點(diǎn)，可在有限的反應(yīng)時(shí)間內(nèi)求到問(wèn)題的近優(yōu)解；結(jié)合自適應(yīng)重調(diào)度和雙層編碼遺傳算法，對(duì)不同規(guī)模問(wèn)題都能得到滿意的結(jié)果。

后續(xù)工作將針對(duì)柔性作業(yè)和混合流水車間，進(jìn)一步研究基于其他高效算法的適應(yīng)性重調(diào)度方法。

［1］陳國(guó)權(quán).企業(yè)實(shí)施敏捷制造的過(guò)程框架［J］.清華大學(xué)學(xué)報(bào)，1999，14（2）：56－59.Chen Guoquan.Framework of Agile Manufacturing in Enterprise［J］.Journal of Tsinghua University，1999，14（2）：56－59.

［2］吳秀麗，李蘇劍，杜彥華.柔性作業(yè)車間多品種小批量調(diào)度算法研究［J］.中國(guó)機(jī)械工程，21（4）：424－429.Wu Xiuli，Li Shujian，Du Yanhua.Research on Batch Scheduling Problem in a Flexible Job Shop［J］.China Mechanical Engineering，21（4）：424－429.

［3］Sugimura N，Tanimizu Y，Iwamura K.A Study on Real－time Scheduling for Holonic Manufacturing System ［J］.Journal of Manufacturing Systems，2004，33（5）：467－475.

［4］Li Z，Ierapetritou M.Process Scheduling under Uncertainty：Review and Challenges［J］.Computers and Chemical Engineering，2008，32（4／5）：715－727.

［5］Leon V J，wu S D，Storer R H.Robustness Measures and Robust Scheduling for Job－shop［J］.IEEE Transactions，1994，26（5）：32－43.

［6］張沙清，陳新度，陳慶新，等.基于改進(jìn)多目標(biāo)微粒群算法的模具多項(xiàng)目反應(yīng)調(diào)度［J］.中國(guó)機(jī)械工程，2011，22（10）：1173－1179.Zhang Shaqing，Chen Xindu，Chen Qingxin，et al.Reactive Scheduling for Multiple Mould and Die Projects Based on Improved Multi－objective Particle Swarm Optimization［J］.China Mechanical Engineering，2011，22（10）：1173－1179.

［7］Abumaizar R J，Svestka J A.Rescheduling Job Shops under Random Disruptions［J］.International Journal of Production Research，1997，35（7）：2065－2082.

［8］Wu S D，Storer R H，Chang P C.One－machine Rescheduling Heuristics with Efficiency and Stability as Criteria［J］.Computers and Operations Research，1993，20（1）：1－14.

［9］李莉，喬非，吳啟迪.半導(dǎo)體制造重調(diào)度研究［J］.中國(guó)機(jī)械工程，2006，17（6）：612－616.Li Li，Qiao Fei，Wu Qidi.Research on Rescheduling for Semiconductor Wafer Fabs［J］.China Mechanical Engineering，2006，17（6）：612－616.

［10］Parviz F，F(xiàn)ariborz J，Jamal A.Flexible Job Shop Scheduling with Overlapping in Operations［J］.Applied Mathematical Modeling，2009，33（7）：3076－3087.

［11］Sabuncuoglu I，Karabuk S.Rescheduling Frequency in an FMS with Uncertain Processing Times and Unreliable Machines［J］.Journal of Manufacturing Systems，1999，18（4）：268－283.

［12］李鐵克，肖擁軍，王柏琳.基于局部性修復(fù)的HFS機(jī)器 故 障 重 調(diào) 度 ［J］.管 理 工 程 學(xué) 報(bào)，2010，4（3）：45－49.Li Tieke，Xiao Yongjun，Wang Bailin.HFS Rescheduling under Machine Failures Based on Local Repair［J］.Journal of Industrial Engineering／Engineering Management，2010，4（3）：45－49.

［13］任海英，鄒艷蕊.基于多Agent的柔性作業(yè)車間預(yù)先／重調(diào)度系統(tǒng)［J］.武漢理工大學(xué)學(xué)報(bào)（信息與管理工程版），2012，34（1）：69－74.Ren Haiying，Zou Yanrui.A Flexible Job Shop Pre／re－scheduling System Based on Agent［J］.Journal of WUT（Information ＆ Management Engineering），2012，34（1）：69－74.

［14］Wh H H，Li R K.A New Rescheduling Method for Computer Based Scheduling Systems［J］.International Journal of Production Research，1995，33（8）：2097－2110.

［15］Leon V J，Wu S D，Storer R H.Games Theoretic Control Approach for Job Shops in the Presence of Disruptions［J］.International Journal of Production Research，1994，32（6）：1451－1476.

［16］Abumaizar R J，Svestka J A.Rescheduling Job Shops under Disruptions［J］.International Journal of Production Research，1997，35（7）：2065－2082.