周琪森，林 杰，白 翱

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

0 引言

在需求多變的市場競爭環(huán)境中，制造企業(yè)的生產(chǎn)模式是多品種的、變批量的、面向訂單的生產(chǎn)模式，呈現(xiàn)隨機(jī)性強(qiáng)、干擾因子多、多目標(biāo)和多約束的特點(diǎn)，排程問題往往是NP-hard難題。而實(shí)際生產(chǎn)過程中存在大量的不確定因素，對制造企業(yè)的日常生產(chǎn)活動產(chǎn)生干擾，影響企業(yè)效率。合理、科學(xué)地分配生產(chǎn)時間和資源的排產(chǎn)方法就是制造企業(yè)能夠高效運(yùn)行的關(guān)鍵，也是實(shí)現(xiàn)制造過程智能化的核心。現(xiàn)有的排產(chǎn)方法主要以各類智能算法為核心，其中包括基于約束理論算法[1]、模擬退火算法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)[2]、粒子群算法[3]等、利用智能算法對排程問題進(jìn)行建模和求解。

本課題的研究對象是制造企業(yè)下的工序級作業(yè)車間排程模型，在按單生產(chǎn)模式下，作業(yè)車間的主要生產(chǎn)需求來源于各類訂單，而訂單的批量、到達(dá)時間是隨機(jī)的、無法預(yù)估的，無法通過提前進(jìn)行成品的預(yù)測生產(chǎn)或者是零部件的預(yù)測生產(chǎn)來減輕或平緩生產(chǎn)負(fù)荷不均帶來的生產(chǎn)組織管理壓力。同時，由于產(chǎn)品復(fù)雜，并有高精度要求，帶來了復(fù)雜多變的工藝路線，導(dǎo)致求解規(guī)模龐大，求解問題困難，目前基于現(xiàn)有的求解策略所得排產(chǎn)結(jié)果還不足以運(yùn)用到實(shí)際生產(chǎn)當(dāng)中。

1 混合集合規(guī)劃方法

混合集合規(guī)劃是在由實(shí)數(shù)、整數(shù)、布爾量、集合所構(gòu)成的混合域上，以邏輯和集合推理作為算法結(jié)構(gòu)框架的求解系統(tǒng)，優(yōu)勢在于能夠精確描述實(shí)數(shù)、整數(shù)、布爾量、集合類型上的復(fù)雜約束。同時，基于混合集合規(guī)劃求解優(yōu)化問題的方法，提出的自然約束語言（Natural Constraint Language，NCL）能夠利用數(shù)理邏輯對生產(chǎn)計(jì)劃與排程問題進(jìn)行簡明的自然描述建模，提高求解效率并且有效的規(guī)避組合爆炸[4]。因此，混合集合規(guī)劃可以應(yīng)用于對大規(guī)模的復(fù)雜問題的求解，同時保證了求解問題的速率和精度[5～7]。目前，混合集合規(guī)劃被應(yīng)用于集裝箱碼頭船舶靠泊和裝卸過程干擾恢復(fù)[8]、高速鐵路列車開行方案優(yōu)化[9]、航空公司航班計(jì)劃以及機(jī)位分配等問題[10～12]等大規(guī)模計(jì)劃方案的研究當(dāng)中，已經(jīng)取得顯著成果。

本課題在智能制造的背景下，引入混合集合規(guī)劃方法以及自然約束語言來研究多品種變批量按單生產(chǎn)模式下的工序級作業(yè)車間的生產(chǎn)排程建模及求解，充分考慮優(yōu)先級約束和裝配約束，將車間任務(wù)合理、科學(xué)地分配到各個班組中，解決任務(wù)合理安排，資源合理分配的難題。

2 排產(chǎn)問題分析

2.1 作業(yè)車間生產(chǎn)流程分析

以某制造企業(yè)為例，如圖1所示，該企業(yè)接收訂單后，統(tǒng)計(jì)訂單中的成品需求數(shù)量和需求時間，根據(jù)物料以及各車間加工技能和加工能力向車間傳達(dá)任務(wù)，包括工藝路線信息（含工時）、零部件最早開工時間及最晚交貨時間、工序優(yōu)先級等。

圖1 作業(yè)車間生產(chǎn)流程圖

2.2 排產(chǎn)思路解析

作業(yè)車間由若干班組組成，而班組可認(rèn)為是具有通用設(shè)備、通用工具的設(shè)備集，是制造車間的核心制造單元。而班組的負(fù)荷情況可以用班組負(fù)荷率來衡量，班組負(fù)荷率指的是在一個生產(chǎn)時間單元內(nèi)班組計(jì)劃加工負(fù)荷與該班組的加工能力的比值。車間根據(jù)班組內(nèi)部人員及設(shè)備負(fù)荷情況和資源使用情況進(jìn)行計(jì)算機(jī)輔助排程得到工序級作業(yè)任務(wù)計(jì)劃，并傳達(dá)到各個班組處，由班組長將工序任務(wù)安排到具體設(shè)備或人員負(fù)責(zé)。本課題基于某制造企業(yè)的實(shí)際生產(chǎn)需要，在制造車間將工序級生產(chǎn)任務(wù)安排到班組的實(shí)際生產(chǎn)背景下，建立數(shù)學(xué)模型及約束。作業(yè)車間生產(chǎn)周期為一周，排產(chǎn)最小時間單元為半天。

因此，班組長作為一級調(diào)度員，能夠?qū)崟r實(shí)地的掌握生產(chǎn)情況，能夠根據(jù)生產(chǎn)實(shí)時情況作出針對性的調(diào)整。事先平衡各班組間的生產(chǎn)任務(wù)負(fù)荷，能夠有效避免忙的忙，閑的閑這一不合理現(xiàn)象，有效提高車間的生產(chǎn)效率。先將工序任務(wù)安排到班組，再由班組將工序任務(wù)分配到班組內(nèi)部的具體設(shè)備上，從而將大規(guī)模排程問題拆分為若干較小規(guī)模問題，降低排程數(shù)據(jù)規(guī)模，避免了人工排產(chǎn)耗時長且不科學(xué)的窘境。

之所以將排產(chǎn)最小時間單元定為半天，是考慮到由于安全、質(zhì)量等問題的存在，當(dāng)發(fā)生異常事件時可能導(dǎo)致生產(chǎn)變動甚至中斷或停止生產(chǎn)，排產(chǎn)到小時甚至分鐘沒有實(shí)際意義。同時排產(chǎn)到半天已經(jīng)足夠滿足該企業(yè)在日常的生產(chǎn)的調(diào)度管理需求，可以在規(guī)定的時間節(jié)點(diǎn)完成產(chǎn)品交付，也給班組長留有一定的調(diào)度空間。再者，在大規(guī)模的排程問題計(jì)算中，排程精度較寬泛可以降低求解復(fù)雜度，提高計(jì)算效率。

因此，在排產(chǎn)開始前需要將排產(chǎn)數(shù)據(jù)中工序定額加工工時以及班組能力工時換算成為半天的整數(shù)倍，不足半天者可以補(bǔ)至半天，這也是為了給排產(chǎn)結(jié)果留有余地。此倍率參數(shù)k的取值可以影響最終排產(chǎn)結(jié)果，可以由計(jì)調(diào)員根據(jù)車間生產(chǎn)情況進(jìn)行設(shè)置。本課題中暫定參數(shù)取值方法如表1所示。

表1 工時換算規(guī)則

3 排產(chǎn)模型建立與求解

3.1 數(shù)據(jù)邏輯分析

生產(chǎn)排程的基礎(chǔ)數(shù)據(jù)主要是班組、工序以及作業(yè)任務(wù)的相關(guān)屬性，可以直接從實(shí)時生產(chǎn)數(shù)據(jù)庫中讀取。本文讀取了該制造企業(yè)車間的班組-工種表、班組工時能力表、工作日歷表、待排產(chǎn)工序表等四個生產(chǎn)原始數(shù)據(jù)表，將數(shù)據(jù)抽象為以下數(shù)學(xué)變量。

PERIOD：采用順序號作為工作日歷，比如新年第一天記為001，考慮法定節(jié)假日以及雙休日，自動跳過后得到正常上班時間段集合；

OpTypei：第i道工序所用工種；

BatchIDi：第i道工序計(jì)劃所屬零件批次，對應(yīng)調(diào)度問題中的作業(yè)（JOB）的概念；ManHouri：第i道工序計(jì)劃所用工時，單位為半天；OpPriorityi：第i道工序的優(yōu)先級參數(shù)（數(shù)值越大級別越高）；

idSucci：第i道工序的后繼工序（NULL表示該工序?yàn)樽鳂I(yè)中最后一道工序）；

TeamOpTypej：第j個班組所對應(yīng)的班組可加工工種集合；

TeamAbilityi：第j個班組內(nèi)部設(shè)備半天內(nèi)的累計(jì)在制工時即為加工能力，單位為半天；

DeptCodei：第i道工序計(jì)劃所分配班組；

StartPeriodi：第i道工序計(jì)劃開工時段；

EndPeriodi：第i道工序計(jì)劃完工時段。

3.2 構(gòu)建排產(chǎn)約束

基于上述生產(chǎn)數(shù)據(jù)，在考慮班組能力負(fù)荷的情況下，本文的主要工作是通過NCL語言將生產(chǎn)排程中的各類約束準(zhǔn)確全面地描述清楚，確定每道工序的開始時間（投產(chǎn)時間）、完工時間以及加工班組。

3.2.1 資源日歷約束

WorkTimeTaski是工序i的有效加工時間，定義為工序i的起止時間段TimeTaski與工作日歷PERIOD交集。

3.2.2 工藝路線約束

工藝員編制的工藝路線必須嚴(yán)格遵守，原則上由車間計(jì)調(diào)，工人不能隨意更改工藝約束。同時一道工序完工后需要其后繼工序在下一個半天開工，為中間的準(zhǔn)備生產(chǎn)活動留有一定的準(zhǔn)備時間。

3.2.3 班組技術(shù)約束

班組內(nèi)設(shè)備能加工何種工種即為班組可加工工種集合， 對應(yīng)工序j。

3.2.4 班組能力約束

TeamAbilityi定義為第j個班組內(nèi)部設(shè)備半天內(nèi)的累計(jì)在制工時即為班組能力，單位是最小排產(chǎn)時間單元即半天。

3.2.5 優(yōu)先級約束

當(dāng)工序i的優(yōu)先級小于工序j時，有兩種情況，若工序i，j所分配班組相同，即占用priority資源沖突時，需要保證工序i的開工時間大于工序j的完工時間，即工序i在工序j之后進(jìn)行加工。

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

本次排產(chǎn)選取最小時間跨度為主要優(yōu)化目標(biāo)，同時考慮班組間一個生產(chǎn)周期內(nèi)（本文定一周為一個生產(chǎn)周期）的負(fù)荷均衡，使得車間接受到的作業(yè)任務(wù)盡量安排在一周內(nèi)完成，保證班組負(fù)荷率不會太低，同時又可以平衡一周內(nèi)的加工負(fù)荷，避免生產(chǎn)任務(wù)集中所造成生產(chǎn)任務(wù)無法按部就班地進(jìn)行。

最小化最晚完工時間表示如下：

各班組半天內(nèi)加工負(fù)荷均衡如下：

3.4 求解策略

本次求解基于POEM平臺邏輯優(yōu)化引擎求解，求解過程基于上述約束條件對解空間進(jìn)行切削，從而求得一系列可行解。同時根據(jù)優(yōu)化目標(biāo)設(shè)計(jì)相應(yīng)的求解規(guī)則，改善約束模型，進(jìn)一步提高求解效率。求解排產(chǎn)問題有如下步驟。

1）查詢確定工序加工班組

2）查詢確定工序開工時間

4 實(shí)例驗(yàn)證

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

此車間共有六個班組，班組可執(zhí)行加工工種總計(jì)25種，選取排產(chǎn)任務(wù)為計(jì)劃加工時間在2016年12月到2017年4月總計(jì)1000道待加工工序，共分為386個不同的作業(yè)任務(wù)集。

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

實(shí)例驗(yàn)證求得可行解耗時228秒，作業(yè)任務(wù)安排自2016年12月1日上午起，3月16日下午完工，排產(chǎn)結(jié)果可以滿足車間內(nèi)班組調(diào)度需求。排產(chǎn)結(jié)果表格輸出形式如表2所示。

表2 排產(chǎn)結(jié)果表格形式示例

續(xù)（表2）

由表2中排產(chǎn)結(jié)果表中分析統(tǒng)計(jì)各班組在2016年12月01日2016年12月07日共10個工作周期中的工作負(fù)荷情況表如表3所示。將班組負(fù)荷情況畫成直方圖，如圖2所示。

圖2 各班組負(fù)荷直方圖

表3 各班組半天內(nèi)負(fù)荷率統(tǒng)計(jì)結(jié)果

相比于該車間在2016年6月到9月的生產(chǎn)數(shù)據(jù)統(tǒng)計(jì)分析結(jié)果，前三個月內(nèi)班組的平均負(fù)荷率在40%左右。可以看到本次排產(chǎn)中各班組每半天內(nèi)的平均負(fù)荷率均在50%左右，既滿足了該制造企業(yè)中較大的生產(chǎn)負(fù)荷，同時又給實(shí)際生產(chǎn)過程可能產(chǎn)生的突發(fā)狀況留下了一定的人為干預(yù)空間。同時，將工序任務(wù)安排到班組之后，對于每個班組而言，排產(chǎn)到設(shè)備的生產(chǎn)排程問題規(guī)模已經(jīng)縮小到了十幾臺設(shè)備，一百道工序左右，使得班組內(nèi)排產(chǎn)到設(shè)備上的時間消耗和求解難度大大減少。

5 結(jié)束語

本文利用自然約束語言對作業(yè)車間工序級排產(chǎn)計(jì)劃問題進(jìn)行了數(shù)學(xué)建模，基于車間內(nèi)班組并行加工的生產(chǎn)環(huán)境下，對排產(chǎn)問題進(jìn)行求解，將工序任務(wù)安排到各班組中，減小了排產(chǎn)問題的規(guī)模。同時，在求解策略中考慮車間內(nèi)各班組間的負(fù)荷平衡，使得排產(chǎn)結(jié)果能夠?qū)⒐ば蛉蝿?wù)盡量均衡安排到班組中。實(shí)際應(yīng)用證明了方法的可行性和有效性，有助于提升制造車間生產(chǎn)過程的運(yùn)行效率，提升制造過程管控的科學(xué)化、智能化水平。

[1]何鶯.基于約束理論的多生產(chǎn)線計(jì)劃排程系統(tǒng)的研究和應(yīng)用[D].上海交通大學(xué),2009.

[2]范華麗,熊禾根,等.動態(tài)車間作業(yè)調(diào)度問題中調(diào)度規(guī)則算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究.2016.

[3]周丹晨.基于粒計(jì)算和序列比對的典型工藝路線發(fā)現(xiàn)方法[J].計(jì)算機(jī)集成制造系統(tǒng), 2015, 21(3):694-701.

[4]Zhou J. The NCL Natural Constraint Language[J].2013.

[5]劉軒,尚鋆,白翱.基于混合集合規(guī)劃的作業(yè)車間生產(chǎn)排程模型研究[J].制造業(yè)自動化,2015,37(23):39-43.

[6]劉軒,尚鋆,白翱.設(shè)備故障驅(qū)動的作業(yè)車間生產(chǎn)任務(wù)重調(diào)度方法研究[J].制造業(yè)自動化,2016,38(12):26-30+60.

[7]Rahmati S H A, Zandieh M, Yazdani M. Developing two multiobjective evolutionary algorithms for the multi-objective flexible job shop scheduling problem[J].The International Journal of Advanced Manufacturing Technology, 2013, 64(5):915-932.

[8]韓子龍.基于自然約束語言的多目標(biāo)泊位—岸橋計(jì)劃干擾恢復(fù)研究[D].大連海事大學(xué),2015.

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

[10]楊年.國內(nèi)空鐵聯(lián)合運(yùn)輸網(wǎng)絡(luò)規(guī)劃方法研究[D].南京航空航天大學(xué),2012.

[11]朱博,朱金福.飛機(jī)計(jì)劃恢復(fù)的混合集合規(guī)劃方法研究[J].小型微型計(jì)算機(jī)系統(tǒng),2012,33(11):2556-2560.

[12]王巖華,朱金福,朱博,唐昀.基于混合集合規(guī)劃的機(jī)位分配約束規(guī)劃模型[J].航空計(jì)算技術(shù), 2014,44(06):18-21.