基于混合集合規(guī)劃的作業(yè)車間生產(chǎn)排程模型研究

劉 軒，尚 鋆，白 翱

（中國工程物理研究院 機械制造工藝研究所，綿陽 621900）

0 引言

合理、有效的計劃和排程是現(xiàn)代制造系統(tǒng)高效運行的關鍵所在之一。隨著制造過程智能化的需求牽引，近年來對于作業(yè)車間的生產(chǎn)排程問題研究較多，其基本技術路線以智能計算方法的建模和求解為主，典型的算法包括遺傳算法、禁忌搜索算法、粒子群算法、模擬退火算法等[1～4]。然而，工業(yè)生產(chǎn)中的排程問題往往屬于NP-hard問題。具體而言，在實際的工程應用中，除了要考慮多約束、多目標的因素之外，還需要兼顧由制造資源種類多、加工工序數(shù)量大等導致的求解規(guī)模大的因素。此外，不同零件的加工工序數(shù)量、不同工序的加工工時大小都可能有很大的差別，且存在一定的不確定性，這些因素也都大大增加了問題求解的困難性，求解結果距離實際應用往往存在較大的差距。這使得目前的排程在很大程度上仍然依賴于人的經(jīng)驗，其合理性、有效性有待提升。

混合集合規(guī)劃（Mixed Set Programming，MSP）[5]理論是一種在混合域上的、基于集合規(guī)劃的算法體系，在處理工業(yè)上復雜的大規(guī)模組合優(yōu)化問題時效果顯著。近些年來，利用混合集合規(guī)劃算法在鐵路列車開行方案、航班計劃恢復、路徑優(yōu)化等方面的研究較多[6～8]，相關應用及實踐案例證明了該理論在求解多約束優(yōu)化問題時的優(yōu)勢。自然約束語言（Natural Constraint Language，NCL）是由周建陽博士創(chuàng)建的、支持混合集合規(guī)劃算法體系的語言系統(tǒng)[9]，它可以以一種人類更容易理解的方式來描述復雜的、變量間相互關聯(lián)的工程優(yōu)化模型。NCL支持隱式類型的聲明、進行全局的語義分析、基于上下文的推理及求解。NCL將數(shù)值約束、簡化的一階邏輯及集合推理集成在一個語言環(huán)境之下，形成一個在混合域（實數(shù)、整數(shù)、布爾值、索引及集合）上針對約束滿足問題的聯(lián)合求解系統(tǒng)，最終獲得工程優(yōu)化問題的滿意解。

針對多品種小批量生產(chǎn)模式下作業(yè)車間排程的難題，本文嘗試將混合集合規(guī)劃理論引入到作業(yè)車間生產(chǎn)排程問題的求解中。在分析和梳理作業(yè)車間資源、作業(yè)、工序約束的基礎上，設置排程優(yōu)化的主次目標，利用自然約束語言建立多約束優(yōu)化模型，提出對應的求解策略并加以求解。研究結果將為復雜多約束條件下作業(yè)車間的排程優(yōu)化提供一種新的手段和實現(xiàn)途徑，從而輔助相關的計劃調(diào)度人員進行科學和定量的決策。

1 作業(yè)車間生產(chǎn)排程問題的約束與目標

1.1 約束條件

作業(yè)車間生產(chǎn)排程是一個非常復雜的問題，本文將約束分為資源、作業(yè)、工序三類，其中資源指加工設備，作業(yè)指一種零件的一個加工批次。

1）資源層級約束

工作日歷：資源可工作的時間集合。其中要考慮到周末、法定節(jié)假日、設備定期檢修以及工作日的休息時間等資源不可工作時間。

資源占用：同一資源在任一時間只能加工一個零件的一道工序。

2）作業(yè)層級約束

最早開工時間：作業(yè)最早開始加工的時間。最早開工時間受制于任務下發(fā)時間、圖紙及原材料到達時間、加工工序制定完成時間以及工裝等的到位時間。

最晚完工時間：作業(yè)最晚完工的時間。一般以需求方要求的交貨期限為準。

作業(yè)的優(yōu)先級：不同的作業(yè)其優(yōu)先級可能不同，優(yōu)先級越高的作業(yè)加工次序越早。

3）工序層級約束

工序的工藝流程：要滿足工序的基本加工次序。如工序2必須在工序1加工完成后才能開始加工。工序單次加工：一個零件的一道工序只能加工一次。工序的可用資源：可以完成一道工序的加工的所有資源的集合。

工序時間：工序的工時，包括工序的準備工時和實際加工工時。為了提高排程的實用性和準確性，將工序的檢驗工時和轉運工時也增加到工序時間中。

1.2 優(yōu)化目標

作業(yè)車間生產(chǎn)排程問題往往存在多個優(yōu)化目標，本文將優(yōu)化目標分為作業(yè)完工和資源利用兩類。

1）作業(yè)完工類

最小化作業(yè)延遲時間總量；

最小化作業(yè)總完工時間；

最小化作業(yè)延遲總數(shù)量；

最大化作業(yè)按期完工率；

……

2）資源利用類

最大化瓶頸資源利用率；

最大化資源利用均衡率；

最大化資源總利用率；

最小化資源空閑總時間；

……

這些優(yōu)化目標都是在生產(chǎn)排程中希望達到的效果，但事實上需要把優(yōu)化目標分出主次，甚至有時候不同目標之間是相互沖突的，這時就需要犧牲掉一些次要目標，來保證主要目標的實現(xiàn)。NCL支持多目標優(yōu)化，并以優(yōu)化目標在程序中的自然順序為優(yōu)化順序，也就是說，第一條優(yōu)化目標為主優(yōu)化目標，是要優(yōu)先滿足的，剩下的優(yōu)化目標的優(yōu)先性逐條降低。

2 建模及求解

2.1 建模思路

建模的基本思路如下：1）首先根據(jù)排程的基本要素建立相應的數(shù)據(jù)庫，作為生產(chǎn)排程的基礎數(shù)據(jù)；2）然后以數(shù)據(jù)庫中的變量作為基礎變量逐條建立約束條件模型；3）之后根據(jù)生產(chǎn)需要選取所需的優(yōu)化目標；4）最后根據(jù)所選的優(yōu)化目標設計相應的求解策略，從而實現(xiàn)優(yōu)化求解。

建模思路框圖如圖1所示。

圖1 建模思路框圖

2.2 數(shù)據(jù)結構設計

建立生產(chǎn)排程的數(shù)據(jù)庫，它包含三個基礎表：資源（RESOURCE）、作業(yè)（JOB）、工序（TASK）。詳細的數(shù)據(jù)結構分別如表1、表2、表3所示。

表1 資源表（RESOURCE）

表2 作業(yè)表（JOB）

表3 工序表（TASK）

2.3 約束模型的建立與詳解

1）資源工作日歷約束

對于不同的工序i和j，它們的加工時間不重疊，或者資源占用不同。

作業(yè)i的任何一個工序的開工時間都不能早于作業(yè)i的最早開工時間。

4）作業(yè)優(yōu)先級約束

在實際的生產(chǎn)排程問題中，作業(yè)優(yōu)先級是一個不容忽視的約束條件。作業(yè)的優(yōu)先級越高，越要優(yōu)先進行排程。在本文中將作業(yè)優(yōu)先級分為三級：非常緊急、緊急、一般，分別對應數(shù)值2、1、0，數(shù)值越大優(yōu)先級越高。

工序的優(yōu)先級應與其對應的作業(yè)優(yōu)先級保持一致，于是首先將作業(yè)優(yōu)先級賦給其所有工序。之后，當工序i的優(yōu)先級高于工序j的優(yōu)先級，并且它們的資源占用發(fā)生沖突時，優(yōu)先安排工序i。

5）工序工藝流程約束

如果工序i的后繼工序不為空，則工序i的完工時間不晚于工序i后繼工序的開工時間。

6）工序單次加工約束

對于不同的資源i和j，一道工序如果安排在了資源i上，就不能再安排在資源j上。該道工序只能被加工一次。

2.4 優(yōu)化目標的選取

這是次優(yōu)化目標，在滿足主優(yōu)化目標的前提下滿足此優(yōu)化目標。

2.5 模型求解

運用混合集合規(guī)劃算法對問題進行求解，其求解思想基于約束切割與深度優(yōu)先搜索，根據(jù)選取的優(yōu)化目標設計相應的求解策略有利于實現(xiàn)高效優(yōu)化求解。本文中將求解過程分為兩步，第一步將所有工序安排在相應資源上，第二步再確定每個工序的開工時間。

1）第一步

第二步以順序性準則先后選取完工時間最早的工序和起始時間最早的工序，最后確定每個工序的開工時間。求解結束。

2.6 結果輸出

最終排程結果可以以Excel表格形式和作業(yè)計劃與延期統(tǒng)計表輸出，也可以以可視化形式輸出。圖形可視化可以輸出資源-工序甘特圖、作業(yè)-工序甘特圖、資源負載圖。

3 應用實例

下面以某機加車間的實際生產(chǎn)數(shù)據(jù)進行應用實例驗證。

該車間共有六大類資源，本文中抽象為A-F類。各類資源數(shù)分別為：A類16個（A01-A16），B類15個（B01-B15），C類8個（C01-C08），D類9個（D01-D09），E類21個（E01-E21），F(xiàn)類14個（F01-F14），總資源數(shù)共83個。選取的排程任務為開工時間在2015年1月內(nèi)、完工時間在1月至3月內(nèi)的157個作業(yè)，共596道工序。

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

求得可行解的時間為12分鐘36秒。作業(yè)延遲時間總量為28682分鐘，資源空閑時間總量為678974分鐘。作業(yè)總完工時間為2015年03月09日12:58。排程結果能夠滿足實際生產(chǎn)的要求。

排程結果輸出形式如下：

1）Excel表格形式

表格中詳細列出了排程計劃中每一道工序的開工時間和完工時間，以及加工資源、所屬作業(yè)等信息，是排程結果的最基本表現(xiàn)形式。如圖2所示。

2）作業(yè)計劃與延期統(tǒng)計表

圖2 Excel表格形式

該表統(tǒng)計了每個作業(yè)的原計劃起止時間、計劃完工時間和延期（天）信息。從表中可以看出，延期超過一天的作業(yè)一共有三個，它們的作業(yè)編號分別為93066_455789_858667、93400_458449_861018、93456_458760_860968，延期量分別為12天、3天和3天?？梢酝ㄟ^協(xié)商調(diào)整交貨日期或者將原作業(yè)進行批次劃分來保證按期完工。如圖3所示。

圖3 作業(yè)計劃與延期統(tǒng)計表

3）資源-工序甘特圖

資源-工序甘特圖按照資源排序，直觀地顯示了每一道工序的加工資源以及起止加工時間。圖中還可顯示工序的詳細信息：所屬作業(yè)、工序號、資源類別、資源實體、可替換資源、整道工序加工時間、加工時間跨度、作業(yè)應交付日期、件數(shù)、下道工序。通過該圖還可以直觀地看出每一個資源在各個時間段的加工任務，空閑時間較多的資源也一目了然。如圖4所示。

圖4 資源-工序甘特圖

4）作業(yè)-工序甘特圖

作業(yè)-工序甘特圖按照作業(yè)排序，直觀地顯示了作業(yè)中每一道工序的起止加工時間。如圖5所示。

圖5 作業(yè)-工序甘特圖

5）資源負載圖

資源負載圖顯示了計劃期內(nèi)每一個資源設備的利用率，從而可以直觀地了解車間資源利用的整體情況。從圖中可以看出，共有12個資源的利用率超過了50%，其中更有5個資源的利用率達到了100%。如圖6所示。

圖6 資源負載圖

4 結論

對作業(yè)車間的實際生產(chǎn)排程問題進行了建模與求解，除常規(guī)的生產(chǎn)排程約束條件外，又充分考慮了作業(yè)的優(yōu)先級約束，使得求得的結果更加符合實際生產(chǎn)的要求。同時求解策略中對于瓶頸資源利用和資源利用均衡性的考慮，使得排程結果更加優(yōu)化。表格及可視化的結果輸出，對于實際生產(chǎn)起到了一定的指導作用，方便管理者尤其是計劃調(diào)度人員進行合理的計劃安排和任務下發(fā)，有利于提高制造過程的效率并提升設備利用率。

[1] 張國輝,高亮,李培根,張超勇.改進遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].機械工程學報,2009,45(7):145-151.

[2] 張超勇,高亮,李新宇,邵新宇.基于進化禁忌算法的Job-Shop調(diào)度問題研究[J].華中科技大學學報(自然科學版),2009,37(8):80-84+95.

[3] 彭傳勇,高亮,邵新宇,周馳.求解作業(yè)車間調(diào)度問題的廣義粒子群優(yōu)化算法[J].計算機集成制造系統(tǒng),2006,12(6):911-917+923.

[4] 潘全科,朱劍英.一類解決作業(yè)車間調(diào)度問題的遺傳退火算法[J].聊城大學學報(自然科學版),2005,18(1):20-22+29.

[5] Jianyang Zhou.A Note on Mixed Set Programming[A].Proceedings of the Seventh International Symposium on Operations Research and its Applications. Lijiang, Asia-Pacific Operations Research Center, Academy of Mathematics and Systems Science, Chinese Academy of Sciences[C].2008:10.

[6] 熊星.基于混合集合規(guī)劃的高速鐵路列車開行方案優(yōu)化研究[D].北京:北京交通大學,2012.

[7] 朱博.不正常航班飛機和機組計劃恢復問題研究[D].南京:南京航空航天大學,2012.

[8] 白曉勇,周建陽.基于混合集合規(guī)劃的車輛路徑優(yōu)化[J].物流技術,2009,28(7):171-173.

[9] 周建陽.自然約束語言[M].北京:科學出版社,2009.