考慮班組負荷均衡的智能制造車間工序級作業任務排程模型研究

周琪森，林 杰，白 翱

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

0 引言

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

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

1 混合集合規劃方法

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

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

2 排產問題分析

2.1 作業車間生產流程分析

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

圖1 作業車間生產流程圖

2.2 排產思路解析

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

因此，班組長作為一級調度員，能夠實時實地的掌握生產情況，能夠根據生產實時情況作出針對性的調整。事先平衡各班組間的生產任務負荷，能夠有效避免忙的忙，閑的閑這一不合理現象，有效提高車間的生產效率。先將工序任務安排到班組，再由班組將工序任務分配到班組內部的具體設備上，從而將大規模排程問題拆分為若干較小規模問題，降低排程數據規模，避免了人工排產耗時長且不科學的窘境。

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

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

表1 工時換算規則

3 排產模型建立與求解

3.1 數據邏輯分析

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

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

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

BatchIDi：第i道工序計劃所屬零件批次，對應調度問題中的作業（JOB）的概念；ManHouri：第i道工序計劃所用工時，單位為半天；OpPriorityi：第i道工序的優先級參數（數值越大級別越高）；

idSucci：第i道工序的后繼工序（NULL表示該工序為作業中最后一道工序）；

TeamOpTypej：第j個班組所對應的班組可加工工種集合；

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

DeptCodei：第i道工序計劃所分配班組；

StartPeriodi：第i道工序計劃開工時段；

EndPeriodi：第i道工序計劃完工時段。

3.2 構建排產約束

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

3.2.1 資源日歷約束

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

3.2.2 工藝路線約束

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

3.2.3 班組技術約束

班組內設備能加工何種工種即為班組可加工工種集合， 對應工序j。

3.2.4 班組能力約束

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

3.2.5 優先級約束

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

3.3 優化目標

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

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

各班組半天內加工負荷均衡如下：

3.4 求解策略

本次求解基于POEM平臺邏輯優化引擎求解，求解過程基于上述約束條件對解空間進行切削，從而求得一系列可行解。同時根據優化目標設計相應的求解規則，改善約束模型，進一步提高求解效率。求解排產問題有如下步驟。

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

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

4 實例驗證

本文以某制造企業下的某機加車間實際生產數據進行應用實例驗證。

此車間共有六個班組，班組可執行加工工種總計25種，選取排產任務為計劃加工時間在2016年12月到2017年4月總計1000道待加工工序，共分為386個不同的作業任務集。

程序運行環境：計算機運行Windows操作系統版本是Windows Server 2008 R2 Enterprise，安裝處理器為雙核，型號是AMD Opteron TM Processor 6168 1.90GHz，內存為32GB，POEM優化計算平臺版本是Academic Vision 3.0。

實例驗證求得可行解耗時228秒，作業任務安排自2016年12月1日上午起，3月16日下午完工，排產結果可以滿足車間內班組調度需求。排產結果表格輸出形式如表2所示。

表2 排產結果表格形式示例

續（表2）

由表2中排產結果表中分析統計各班組在2016年12月01日2016年12月07日共10個工作周期中的工作負荷情況表如表3所示。將班組負荷情況畫成直方圖，如圖2所示。

圖2 各班組負荷直方圖

表3 各班組半天內負荷率統計結果

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

5 結束語

本文利用自然約束語言對作業車間工序級排產計劃問題進行了數學建模，基于車間內班組并行加工的生產環境下，對排產問題進行求解，將工序任務安排到各班組中，減小了排產問題的規模。同時，在求解策略中考慮車間內各班組間的負荷平衡，使得排產結果能夠將工序任務盡量均衡安排到班組中。實際應用證明了方法的可行性和有效性，有助于提升制造車間生產過程的運行效率，提升制造過程管控的科學化、智能化水平。

[1]何鶯.基于約束理論的多生產線計劃排程系統的研究和應用[D].上海交通大學,2009.

[2]范華麗,熊禾根,等.動態車間作業調度問題中調度規則算法研究綜述[J].計算機應用研究.2016.

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

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

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

[6]劉軒,尚鋆,白翱.設備故障驅動的作業車間生產任務重調度方法研究[J].制造業自動化,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]韓子龍.基于自然約束語言的多目標泊位—岸橋計劃干擾恢復研究[D].大連海事大學,2015.

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

[10]楊年.國內空鐵聯合運輸網絡規劃方法研究[D].南京航空航天大學,2012.

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

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