設備故障驅動的作業(yè)車間生產任務重調度方法研究

劉 軒，尚 鋆，白 翱

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

設備故障驅動的作業(yè)車間生產任務重調度方法研究

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

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

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

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

0 引言

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

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

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

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

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

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

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

1）重調度任務

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

圖1 設備故障重調度示意圖

2）正加工任務

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

3）已調度任務

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

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

1）正加工任務次序約束

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

2）正加工資源占用約束

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

3）已調度任務次序約束

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

4）已調度資源占用約束

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

5）資源可用約束

每一次重調度時，較之上一次調度都過去了一段時間，這時就需要將已經過去的這段時間從資源的可用時間中刪除掉。更新之后的資源可用信息構成準確的“資源可用約束”。

2 業(yè)務建模

2.1 約束條件

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

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

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

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

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

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

2.2 動態(tài)任務集

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

1）待調度任務集：存儲當次參與調度的任務；

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

3）正加工任務集：存儲重調度時刻的正加工任務。

2.3 優(yōu)化目標

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

3 數(shù)據建模

3.1 數(shù)據結構設計

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

表1 資源類表

表2 作業(yè)類表

表3 工序類表

表4 計劃類表

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

表5 資源類表數(shù)據結構

表6 作業(yè)類表數(shù)據結構

表7 工序類表數(shù)據結構

表8 計劃類表數(shù)據結構

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

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

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

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

4 NCL建模與求解

4.1 約束條件建模

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

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

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

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

4.3 求解算法設計

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

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

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

設備故障重調度的流程圖如圖2所示。

圖2 設備故障重調度

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

Step1：依據計劃結果表（PLAN表）中的信息，從“任務總集”中選出要重調度的任務，復制到“待調度任務集”中，然后將這些選出的需要重調度的任務對應的工序從PLAN表中刪除，但不刪除這些任務在“任務總集”中的信息。

此時PLAN表中存儲了準確的“已調度任務次序約束”信息。

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

Step3：在約束的條件下進行調度，并輸出計劃結果到PLAN表中。

6 實例驗證

以某機加車間2015年1月份的生產任務作為實例進行驗證。

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

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

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

B08設備故障重調度計劃的結果具體指標如表11所示。

表11 設備故障重調度計劃結果

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

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

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

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

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

劉軒（1990 -），男，河北唐山人，碩士研究生，研究方向為生產計劃與調度理論及應用。