基于約束規(guī)劃的印刷企業(yè)計劃排產(chǎn)模型建立與仿真

姜麗蘋

（中國科學(xué)院沈陽自動化研究所，沈陽 110016）

加工與制造

基于約束規(guī)劃的印刷企業(yè)計劃排產(chǎn)模型建立與仿真

姜麗蘋

（中國科學(xué)院沈陽自動化研究所，沈陽 110016）

為解決約束較多的印刷車間的排產(chǎn)優(yōu)化問題，設(shè)計了基于約束規(guī)劃的多目標(biāo)計劃排產(chǎn)模型。模型基于約束規(guī)劃思想，通過以虛擬活件處理裝訂工序，虛擬設(shè)備處理委外工序的方法簡化排產(chǎn)模型，基于加權(quán)系數(shù)法將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)規(guī)劃問題。利用ILog Cplex軟件對不同企業(yè)規(guī)模數(shù)據(jù)進行仿真驗證，試驗證明在產(chǎn)能充足條件下，模型可獲得優(yōu)化解，滿足交貨期，縮短生產(chǎn)周期，減少完工庫存成本。

排產(chǎn)模型；虛擬活件；虛擬設(shè)備；裝訂工序；委外工序

0 引言

印刷企業(yè)屬于一種特殊的離散型加工行業(yè)。企業(yè)按單生產(chǎn)、產(chǎn)品因單而異、訂單批量小、交貨期短，并且加工設(shè)備昂貴。企業(yè)采用柔性生產(chǎn)方式滿足市場需求[5]。柔性生產(chǎn)只有在良好計劃指導(dǎo)下才能發(fā)揮優(yōu)勢，提高設(shè)備利用率，滿足交貨期。

計劃調(diào)度問題作為一種典型的組合優(yōu)化問題，其求解方法主要有最優(yōu)化方法和近似方法兩大類[1]。柔性作業(yè)車間實際生產(chǎn)過程中約束較多，很難用數(shù)學(xué)規(guī)劃、分支定界等最優(yōu)化方法建立有效求解模型。啟發(fā)式規(guī)則、人工智能等近似方法往往受問題本身特征限制，在求解過程中需要考慮較多參數(shù)，不能保證解的優(yōu)化度[1,2]。

近年來，約束規(guī)劃方法[3-8]在基于組合優(yōu)化的排產(chǎn)調(diào)度問題上受到越來越多的關(guān)注。約束規(guī)劃集成了人工智能和運籌學(xué)的優(yōu)勢，將問題的側(cè)重點由問題的求解轉(zhuǎn)化為問題的建模。實際證明約束規(guī)劃能夠求解大多數(shù)規(guī)模較大、約束較多的生產(chǎn)企業(yè)計劃排產(chǎn)問題，獲得問題的優(yōu)化解。

本文基于約束規(guī)劃思想解決印刷企業(yè)的計劃排產(chǎn)問題，提出計劃排產(chǎn)模型處理企業(yè)的委外工序、裝訂工序、可用時間離散化等縱多生產(chǎn)約束。模型以滿足用戶交付日期、縮短生產(chǎn)周期與減少完工庫存成本為目標(biāo)?；贗Log Cplex對提出計劃排產(chǎn)模型性能進行仿真驗證。

1 印刷企業(yè)生產(chǎn)過程

印刷企業(yè)生產(chǎn)過程如圖1所示，板房制版后，印刷車間基于印版對活件（內(nèi)文、封面等在制品）進行平印或輪轉(zhuǎn)印刷，而后依據(jù)各自工藝要求有選擇的進行覆膜、UV、凹凸工序，然后折頁、裝訂（膠釘或騎釘），最后包裝完成。

印刷產(chǎn)品的工藝結(jié)構(gòu)如圖2所示，多個活件并行批量生產(chǎn)，在裝訂工序合成后進行包裝完成生產(chǎn)。

印刷設(shè)備昂貴，個別工序需委外完成。企業(yè)每道生產(chǎn)工序存在多臺支持不同規(guī)格活件加工的設(shè)備。設(shè)備在更換加工產(chǎn)品前，需設(shè)定參數(shù)，并且首件試制合格后才可批量加工。

印刷企業(yè)的制版計劃相對簡單，可由印刷計劃倒推完成。本文主要研究由印刷到包裝生產(chǎn)過程計劃建模，模型需滿足用戶交貨期和各種生產(chǎn)約束，縮短平均生產(chǎn)周期，減少完工庫存。

圖1 印刷生產(chǎn)過程

圖2 印刷產(chǎn)品結(jié)構(gòu)

2 計劃排產(chǎn)模型建立

2.1 問題分析與描述

印刷企業(yè)生產(chǎn)過程可形式化描述如下：

1）企業(yè)存在N道工序，每道工序存在Mn個支持不同規(guī)格活件加工的設(shè)備。

2）組成產(chǎn)品的活件依據(jù)工藝路徑各自生產(chǎn)，在裝訂工序合并后進行包裝?；罴庸ぶ写嬖谖夤ば颉?/p>

3）可從ERP獲取產(chǎn)品計劃釋放時間和計劃交付時間，產(chǎn)品活件加工數(shù)量已知。

4）每臺設(shè)備在同一時刻只能加工一批活件，一批活件在一臺設(shè)備加工完成。

5）設(shè)備加工速度，切換活件時間與首件試制時間已知。

6）在班組休息時間不進行作業(yè)，即滿足可用時間離散化約束。

7）活件在加工過程中，可部分運輸?shù)较碌拦ば颍视媱澆豢紤]活件轉(zhuǎn)運時間。首件試制生成的數(shù)量很少可忽略不計。

8）生產(chǎn)目標(biāo)是產(chǎn)品在滿足計劃釋放時間和交貨時間的前提下，最小化生產(chǎn)周期，降低在制品庫存成本。

2.2 變量定義

1）已知變量

Product產(chǎn)品集合；

p 產(chǎn)品；

Releasepp∈Product 產(chǎn)品的計劃釋放時間；

Duepp∈Product 產(chǎn)品的計劃完工時間；

Operation 工序集合；

o o∈Operation 工序；

OutsourcingOpertion 委外工序；

Machine 設(shè)備集合；

m m∈Machine 設(shè)備，除印刷車間正常設(shè)備，模型還設(shè)立了加工速度為1的outsourcingM，用以計算委外加工時間；

Speedmm∈Machine 設(shè)備加工速度；

ChangeTimemm∈Machine 設(shè)備更換活件時間，ChangeTimeoutsourcingM=0；

TestTimemm∈Machine 設(shè)備首件試制時間，TestTimeoutsourcingM=0；

Jobpp∈Product產(chǎn)品p包括的活件集合，除了產(chǎn)品正常包括活件的定義，設(shè)定Jobp中最后一個活件為一個虛擬活件，用以模型處理多個活件合成后的裝訂工序及后續(xù)工序；

j j∈Jobpp∈Product 產(chǎn)品p包括的活件；

JobOperation={〈p,j,o〉}p∈Product，j∈Jobp，o∈Operation 產(chǎn)品p的活件j需要經(jīng)過工序o；

Machinejojo∈JobOperation 活件jo.j在工序jo.o可使用設(shè)備集合；

JobOperationM={〈jo,m〉}jo∈JobOperation，

m∈Machinejo活件jo.j在工序jo.o可以使用設(shè)備m進行加工；

JobNumjojo∈JobOperation活件jo.j在工序jo.o需要加工數(shù)量。委外工序以加工數(shù)量表示委外加工時間；

{Precedencepre,post} pre∈Operation, post∈Operation并且pre≠post 工序先后執(zhí)行順序集合，pre工序先于post工序執(zhí)行；

{BreakstartT,endT} 工人休息時間集合，startT與endT分別為休息的開始時間和結(jié)束時間；

2）決策變量

JobOperationMChoojom∈{0,1}

jom∈JobOperationM

JobOperationMChoojom=0表示活件jom.jo.j在工序jom. jo.o不使用設(shè)備jom.m加工，JobOperationMChoojom=1表示活件jom.jo.j在工序jom.jo.o使用設(shè)備jom.m加工；

JobOperationMTimejom=〈StartTjom,EndTjom〉

jom∈JobOperationM

活件jom.jo.j的工序jom.jo.o在設(shè)備jom.m加工時間段,StartTjom與EndTjom分別為開始與結(jié)束加工時間。若不在設(shè)備中加工，EndTjom=StartTjom；

2.3 約束條件

1）釋放時間約束

活件工序開始時間大于等于產(chǎn)品計劃釋放時間。

2）完工時間約束

活件工序結(jié)束時間小于等于產(chǎn)品計劃完成時間。

3）生產(chǎn)時間約束

式(3)表示若活件在設(shè)備m中加工，生產(chǎn)時間等于加工時間、更換活件時間與首件試制時間之和。此式同時也處理了委外加工。式(4)表示活件不在設(shè)備m中加工。

4）先后工序約束

式(5)表示同一活件后道工序加工開始加工時間大于等于前道工序加工結(jié)束時間。式(5)通過虛擬活件last(Bj)基于同一約束式處理了裝訂工序。

5）一批活件在一臺設(shè)備加工完成

6）同一設(shè)備同一時間只能加工一批活件

在式(7)中，使用了ILOG中OPL語言“noOverlap”，表示除了處理委外的虛擬設(shè)備，設(shè)備被不同批次活件占用時間是不重疊的。

7）不能跨越工人休息時間約束

設(shè)備的生產(chǎn)時間不能占用工人的休息時間，約束關(guān)系如下表達：

2.4 目標(biāo)函數(shù)

在滿足各種生產(chǎn)約束的前提下，縮短產(chǎn)品平均生產(chǎn)周期，減少完工交付產(chǎn)品庫存。本文以α為加權(quán)系數(shù)將多目標(biāo)規(guī)劃問題轉(zhuǎn)換為單目標(biāo)規(guī)劃問題。式(9)以產(chǎn)品的最后一道工序完工時間與產(chǎn)品所有活件的首道工序最早開工時間的平均值獲取產(chǎn)品的加工周期，以此為基礎(chǔ)獲得產(chǎn)品的平均生產(chǎn)周期。式(10)表示產(chǎn)品計劃完工時間與實際完工時間時間差的平均值，計算提前完工產(chǎn)品時間的均值，用以表示提前完工占據(jù)庫存成本。

3 仿真實例

本文基于ILog Cplex軟件，利用OPL的系統(tǒng)規(guī)范化描述建立了約束模型文件和不同規(guī)模的樣例數(shù)據(jù)文件，進行計劃排產(chǎn)模型的仿真與驗證。模型基于Win7系統(tǒng)，4G內(nèi)存，Intel i3 CPU環(huán)境下運行。運行結(jié)果界面如圖3所示，包括產(chǎn)品，活件，工序，開始時間，結(jié)束時間，加工時間。

對不同規(guī)模的樣例數(shù)據(jù)進行驗證，如表1所示。經(jīng)試驗測得建立的排產(chǎn)模型針對稍大規(guī)模的數(shù)據(jù)，可在較短時間內(nèi)獲得問題的初始解，獲取優(yōu)化解時間隨企業(yè)規(guī)模增大而成指數(shù)增長。對于約束較多。

【】【】

Modeling and simulation of planning and scheduling based on constraint programming for printing enterprise

JIANG Li-ping

TP18

A

1009-0134(2016)12-0035-04

2016-07-20

智能制造專項綜合標(biāo)準(zhǔn)化試驗驗證項目（Y6CA050A01）

姜麗蘋（1980 -），女，遼寧人，副研究員，碩士，主要從事制造執(zhí)行技術(shù)研究。