劉 軒，尚 鋆，白 翱

（1.中國工程物理研究院 機械制造工藝研究所，綿陽 621900；2.中國核電工程有限公司，北京 100840）

設(shè)備故障驅(qū)動的作業(yè)車間生產(chǎn)任務(wù)重調(diào)度方法研究

劉 軒1,2，尚 鋆1，白 翱1

（1.中國工程物理研究院 機械制造工藝研究所，綿陽 621900；2.中國核電工程有限公司，北京 100840）

現(xiàn)代作業(yè)車間中，因設(shè)備故障導(dǎo)致原生產(chǎn)計劃無法執(zhí)行的情況時有發(fā)生，影響了車間生產(chǎn)任務(wù)的正常執(zhí)行。針對此問題，首先分析了設(shè)備故障情況下的動態(tài)約束條件，并進行了業(yè)務(wù)建模和數(shù)據(jù)建模，其次采用混合集合規(guī)劃理論及其支持工具，結(jié)合滾動窗口重調(diào)度模式，建立了作業(yè)車間重調(diào)度模型，包括其主要約束、優(yōu)化目標(biāo)、求解算法等。最后，通過某機械加工車間的生產(chǎn)實例進行了應(yīng)用驗證，求解結(jié)果表明了本方法的可行性和有效性。

作業(yè)車間；設(shè)備故障；重調(diào)度；混合集合規(guī)劃；自然約束語言；智能制造

0 引言

作業(yè)車間中經(jīng)常出現(xiàn)各種動態(tài)的擾動或異常事件，這些擾動或異常事件會對原生產(chǎn)計劃的正常執(zhí)行產(chǎn)生不利影響，嚴(yán)重時甚至造成生產(chǎn)任務(wù)不能按期完工和交付，給企業(yè)帶來訂單超期交付而被懲罰的損失。因此，當(dāng)擾動或異常事件發(fā)生時，根據(jù)當(dāng)前車間任務(wù)的實時執(zhí)行狀態(tài)和擾動影響程度，對原有的生產(chǎn)計劃進行重新調(diào)度，以生成新的生產(chǎn)計劃是保證車間生產(chǎn)任務(wù)正常執(zhí)行的關(guān)鍵所在。設(shè)備故障是現(xiàn)代作業(yè)車間中最常見的擾動之一，由設(shè)備故障引起的停機問題將導(dǎo)致原來安排到該設(shè)備上生產(chǎn)的工序無法順利執(zhí)行，因此，研究設(shè)備故障條件下的調(diào)度對于提高整個制造系統(tǒng)的穩(wěn)定性具有重要意義。

目前，國內(nèi)外學(xué)者對于設(shè)備故障重調(diào)度問題已經(jīng)有了一些研究[1～3]，其中采用的求解方法多以遺傳算法、粒子群算法等智能優(yōu)化算法為主。混合集合規(guī)劃（Mixed Set Programming，MSP）[4]理論結(jié)合了運籌學(xué)、啟發(fā)式規(guī)則以及智能推理等諸多方法的優(yōu)勢，且已獨立發(fā)展了對應(yīng)的支持語言系統(tǒng)——自然約束語言（Natural Constraint Language，NCL）[5]，可更加有效、方便地求解工程中復(fù)雜的組合優(yōu)化問題。目前MSP已在車間生產(chǎn)調(diào)度領(lǐng)域有了一些研究與應(yīng)用[6～8]，初步展現(xiàn)其在大規(guī)模工程優(yōu)化問題方面的諸多優(yōu)勢。

針對作業(yè)車間設(shè)備故障引起的重調(diào)度問題，本文將采用混合集合規(guī)劃的理論進行建模和求解，通過增加動態(tài)約束條件和引入動態(tài)任務(wù)集的方法，在基本靜態(tài)調(diào)度模型基礎(chǔ)上設(shè)計了一種設(shè)備故障重調(diào)度方法，以便發(fā)生設(shè)備故障時能夠快速生成新的生產(chǎn)計劃，指導(dǎo)不同工序生產(chǎn)任務(wù)的落實和執(zhí)行，從而保證車間生產(chǎn)過程的平穩(wěn)、高效。

1 設(shè)備故障重調(diào)度動態(tài)約束分析

在設(shè)備故障重調(diào)度問題中，存在一些除靜態(tài)調(diào)度常見約束以外的重調(diào)度特有的動態(tài)約束條件。

圖1是設(shè)備故障重調(diào)度的示意圖，為設(shè)備-工序甘特圖。圖中共列出了三臺設(shè)備——設(shè)備1、設(shè)備2、設(shè)備3，三個作業(yè)——作業(yè)A、作業(yè)B、作業(yè)C，其中作業(yè)A有三道工序，作業(yè)B有三道工序，作業(yè)C有兩道工序。圖中箭頭所指位置為設(shè)備2發(fā)生故障時刻，此時刻就作為重調(diào)度的節(jié)點時刻。

首先參照圖1定義三種任務(wù)的狀態(tài)：

1）重調(diào)度任務(wù)

在重調(diào)度節(jié)點時刻未完工且需要進行重調(diào)度的任務(wù)。受到設(shè)備2故障影響需要重調(diào)度的任務(wù)有作業(yè)B的工序1未完工部分（如圖1中右陰影所示）及其所有后續(xù)工序（作業(yè)B的工序2、3）、作業(yè)A的工序2及其后繼工序（作業(yè)A的工序3）、作業(yè)C的工序2。

圖1 設(shè)備故障重調(diào)度示意圖

2）正加工任務(wù)

在重調(diào)度節(jié)點時刻未受到設(shè)備故障影響的已經(jīng)開始加工但仍未完工的任務(wù)。這一類任務(wù)不需要進行重調(diào)度，但是會對當(dāng)次重調(diào)度產(chǎn)生影響。如圖1中作業(yè)A的工序1（左陰影部分為未完工部分）。

3）已調(diào)度任務(wù)

在重調(diào)度節(jié)點時刻未受到設(shè)備故障影響且未完工的任務(wù)。這一類任務(wù)也不需要進行重調(diào)度，但是會對當(dāng)次重調(diào)度產(chǎn)生影響。如圖1中作業(yè)C的工序1。

定義完任務(wù)的狀態(tài)，就開始對重調(diào)度的動態(tài)約束條件進行分析，總結(jié)出以下五種動態(tài)約束條件：

1）正加工任務(wù)次序約束

圖1中作業(yè)A的工序1為“正加工任務(wù)”，需要重調(diào)度的作業(yè)A的工序2是其后繼工序，所以其開工時間必須在該“正加工任務(wù)”完工之后。本文中將這種約束稱為“正加工任務(wù)次序約束”。

2）正加工資源占用約束

圖1中作業(yè)A的工序1為“正加工任務(wù)”，該工序占用了重調(diào)度后設(shè)備1上的一部分可用時間（即圖1中左陰影部分），因此設(shè)備1上的這部分時間就不能再安排其他任務(wù)（如作業(yè)B的工序2）。本文中將這種約束稱為“正加工資源占用約束”。

3）已調(diào)度任務(wù)次序約束

圖1中作業(yè)C的工序1為“已調(diào)度任務(wù)”，需要重調(diào)度的作業(yè)C的工序2是其后繼工序，所以其開工時間必須在該“已調(diào)度任務(wù)”完工之后。本文中將這種約束稱為“已調(diào)度任務(wù)次序約束”。

4）已調(diào)度資源占用約束

圖1中作業(yè)C的工序1為“已調(diào)度任務(wù)”，該工序占用了重調(diào)度后設(shè)備3上的部分可用時間，因此設(shè)備3上的這部分時間就不能再安排其他任務(wù)（如作業(yè)B的工序3）。本文中將這種約束稱為“已調(diào)度資源占用約束”。

5）資源可用約束

每一次重調(diào)度時，較之上一次調(diào)度都過去了一段時間，這時就需要將已經(jīng)過去的這段時間從資源的可用時間中刪除掉。更新之后的資源可用信息構(gòu)成準(zhǔn)確的“資源可用約束”。

2 業(yè)務(wù)建模

2.1 約束條件

首先根據(jù)作業(yè)車間生產(chǎn)調(diào)度問題的三要素（資源、作業(yè)、工序）梳理基本的靜態(tài)調(diào)度約束條件如下：

1）資源類約束：包括工作日歷約束和資源占用約束。

2）作業(yè)類約束：包括最早開工時間約束、最晚完工時間約束、作業(yè)優(yōu)先級約束、作業(yè)裝配等級約束。

3）工序類約束：包括加工次序約束、單次加工約束、可用資源約束、工時約束。

在動態(tài)調(diào)度問題中，還要考慮上文中的五種動態(tài)約束條件：正加工任務(wù)次序約束、正加工資源占用約束、已調(diào)度任務(wù)次序約束、已調(diào)度資源占用約束、資源可用約束。

動態(tài)約束條件是隨著時間和生產(chǎn)系統(tǒng)狀態(tài)的不斷變化而相應(yīng)發(fā)生改變的，這是其不同于靜態(tài)調(diào)度約束條件的根本所在。

2.2 動態(tài)任務(wù)集

根據(jù)生產(chǎn)任務(wù)的幾種不同狀態(tài)，分別定義不同的動態(tài)任務(wù)集如下：

1）待調(diào)度任務(wù)集：存儲當(dāng)次參與調(diào)度的任務(wù)；

2）任務(wù)總集：存儲所有未開工的任務(wù)；

3）正加工任務(wù)集：存儲重調(diào)度時刻的正加工任務(wù)。

2.3 優(yōu)化目標(biāo)

在面向訂單的生產(chǎn)環(huán)境中，按照承諾給客戶的時間節(jié)點交付產(chǎn)品是車間生產(chǎn)最重要的目標(biāo)，因此本文選擇最小化作業(yè)延遲時間總量作為生產(chǎn)計劃重調(diào)度的優(yōu)化目標(biāo)。

3 數(shù)據(jù)建模

3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計

需要建立資源、作業(yè)、工序、計劃四類表，每一類包括的數(shù)據(jù)表分別如表1、表2、表3和表4所示。

表1 資源類表

表2 作業(yè)類表

表3 工序類表

表4 計劃類表

每一類表的具體數(shù)據(jù)結(jié)構(gòu)分別如表5、表6、表7、表8所示。

表5 資源類表數(shù)據(jù)結(jié)構(gòu)

表6 作業(yè)類表數(shù)據(jù)結(jié)構(gòu)

表7 工序類表數(shù)據(jù)結(jié)構(gòu)

表8 計劃類表數(shù)據(jù)結(jié)構(gòu)

3.2 建立動態(tài)約束集和動態(tài)任務(wù)集

每個動態(tài)任務(wù)集分別由一個作業(yè)類表和一個工序類表組成：JOB表和TASK表組成“待調(diào)度任務(wù)集”，JOBALL表和TASKALL表組成“任務(wù)總集”，JOBFIXED表和TASKFIXED表組成“正加工任務(wù)集”。如表9所示。

表9 動態(tài)任務(wù)集的組成

不同的表存儲著不同的約束信息，動態(tài)約束集由資源類表或計劃類表組成：PLANFIXED表儲存“正加工任務(wù)次序約束”信息，RESOURCEFIXED表儲存“正加工資源占用約束”信息，PLAN表儲存 “已調(diào)度任務(wù)次序約束”信息，RESOURCEPLAN表儲存“已調(diào)度資源占用約束”信息，RESOURCE表儲存“資源可用約束”信息。如表10所示。

4 NCL建模與求解

4.1 約束條件建模

下面依次對業(yè)務(wù)建模中梳理的靜態(tài)和動態(tài)約束條件進行數(shù)理邏輯的建模。

表10 動態(tài)約束集的組成

4.2 優(yōu)化目標(biāo)建模

本文中選取最小化作業(yè)延遲時間總量作為優(yōu)化目標(biāo)。

4.3 求解算法設(shè)計

選擇完優(yōu)化目標(biāo)，就開始進行相應(yīng)的求解算法的設(shè)計。本文選取最常用的最小化松弛度準(zhǔn)則和順序搜尋準(zhǔn)則作為查詢準(zhǔn)則，枚舉方式選擇下界優(yōu)先邊界枚舉。將算法求解過程分為兩個階段，即先將工序安排到資源上，再確定每個工序的開工時間。

經(jīng)過求解算法的兩個階段，即可得到每道工序在相應(yīng)資源上的開工時間和完工時間。

5 設(shè)備故障重調(diào)度的實現(xiàn)

設(shè)備故障重調(diào)度的流程圖如圖2所示。

圖2 設(shè)備故障重調(diào)度

在更新“正加工任務(wù)次序約束”、“正加工資源占用約束”和“資源可用約束”信息之后，設(shè)備故障重調(diào)度的具體實現(xiàn)步驟如下：

Step1：依據(jù)計劃結(jié)果表（PLAN表）中的信息，從“任務(wù)總集”中選出要重調(diào)度的任務(wù)，復(fù)制到“待調(diào)度任務(wù)集”中，然后將這些選出的需要重調(diào)度的任務(wù)對應(yīng)的工序從PLAN表中刪除，但不刪除這些任務(wù)在“任務(wù)總集”中的信息。

此時PLAN表中存儲了準(zhǔn)確的“已調(diào)度任務(wù)次序約束”信息。

Step2：根據(jù)PLAN表更新已調(diào)度資源占用表（RESOURCEPLAN表）的信息，從而更新了“已調(diào)度資源占用約束”。

Step3：在約束的條件下進行調(diào)度，并輸出計劃結(jié)果到PLAN表中。

6 實例驗證

以某機加車間2015年1月份的生產(chǎn)任務(wù)作為實例進行驗證。

運行環(huán)境：處理器為AMD Opteron? Processor 6168 1.90GHz（雙核處理器），安裝內(nèi)存（RAM）為32GB，Windows操作系統(tǒng)版本為Windows Server 2008 R2 Enterprise，POEM優(yōu)化計算平臺版本為Academic Version 3.0。

假設(shè)2015年1月22日（周四）9:00設(shè)備B08發(fā)生故障，預(yù)計到2015年1月27日17:30可排除故障。

以故障發(fā)生時刻為重調(diào)度節(jié)點（2015年1月22日9:00），故障期間涉及到的需要重調(diào)度的作業(yè)有4個，共21道工序。并且資源故障發(fā)生時剛好有工序在該設(shè)備上進行加工，為作業(yè)93238_457148_859472的第二道工序id=2400185，需要用剩余工時（177分鐘）修正原有工時（600分鐘）。

B08設(shè)備故障重調(diào)度計劃的結(jié)果具體指標(biāo)如表11所示。

表11 設(shè)備故障重調(diào)度計劃結(jié)果

從表中結(jié)果可以看出，所有受到設(shè)備故障影響進行重調(diào)度的任務(wù)都能夠按時完工，作業(yè)按期完工率為100%，證明了設(shè)備故障重調(diào)度方法良好的重調(diào)度效果；運算時間為2.6秒，完全滿足生產(chǎn)實際的要求。

圖3和圖4分別截取了設(shè)備B08發(fā)生故障進行重調(diào)度之后一周范圍內(nèi)的故障前和故障后的調(diào)度計劃的資源-

【】【】工序甘特圖。通過與圖3進行對比，可以從圖4中看出，受到B08設(shè)備故障影響進行重調(diào)度的任務(wù)（著色）都被很好地重新安排到了原計劃（未著色）的空閑時段，重調(diào)度效果良好。

Production task rescheduling method for job shop based on equipment failure

LIU Xuan1,2, SHANG Jun1, BAI Ao1

TH166

A

1009-0134(2016)12-0026-06

2016-08-13

中國工程物理研究院機械制造工藝研究所“十二五”預(yù)研課題（K814-13-Y）；中國工程物理研究院科技專項（9120601）

劉軒（1990 -），男，河北唐山人，碩士研究生，研究方向為生產(chǎn)計劃與調(diào)度理論及應(yīng)用。