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

劉 軒，尚 鋆，白 翱

（中國(guó)工程物理研究院 機(jī)械制造工藝研究所，綿陽(yáng) 621900）

0 引言

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

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

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

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

1.1 約束條件

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

1）資源層級(jí)約束

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

資源占用：同一資源在任一時(shí)間只能加工一個(gè)零件的一道工序。

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

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

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

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

3）工序?qū)蛹?jí)約束

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

工序時(shí)間：工序的工時(shí)，包括工序的準(zhǔn)備工時(shí)和實(shí)際加工工時(shí)。為了提高排程的實(shí)用性和準(zhǔn)確性，將工序的檢驗(yàn)工時(shí)和轉(zhuǎn)運(yùn)工時(shí)也增加到工序時(shí)間中。

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

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

1）作業(yè)完工類

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

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

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

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

……

2）資源利用類

最大化瓶頸資源利用率；

最大化資源利用均衡率；

最大化資源總利用率；

最小化資源空閑總時(shí)間；

……

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

2 建模及求解

2.1 建模思路

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

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

圖1 建模思路框圖

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

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

表1 資源表（RESOURCE）

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

表3 工序表（TASK）

2.3 約束模型的建立與詳解

1）資源工作日歷約束

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

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

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

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

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

5）工序工藝流程約束

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

6）工序單次加工約束

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

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

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

2.5 模型求解

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

1）第一步

第二步以順序性準(zhǔn)則先后選取完工時(shí)間最早的工序和起始時(shí)間最早的工序，最后確定每個(gè)工序的開工時(shí)間。求解結(jié)束。

2.6 結(jié)果輸出

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

3 應(yīng)用實(shí)例

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

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

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

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

排程結(jié)果輸出形式如下：

1）Excel表格形式

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

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

圖2 Excel表格形式

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

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

3）資源-工序甘特圖

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

圖4 資源-工序甘特圖

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

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

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

5）資源負(fù)載圖

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

圖6 資源負(fù)載圖

4 結(jié)論

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

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

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

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

[4] 潘全科,朱劍英.一類解決作業(yè)車間調(diào)度問(wèn)題的遺傳退火算法[J].聊城大學(xué)學(xué)報(bào)(自然科學(xué)版),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].北京:北京交通大學(xué),2012.

[7] 朱博.不正常航班飛機(jī)和機(jī)組計(jì)劃恢復(fù)問(wèn)題研究[D].南京:南京航空航天大學(xué),2012.

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

[9] 周建陽(yáng).自然約束語(yǔ)言[M].北京:科學(xué)出版社,2009.