姜麗蘋

（中國(guó)科學(xué)院沈陽(yáng)自動(dòng)化研究所，沈陽(yáng) 110016）

加工與制造

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

姜麗蘋

（中國(guó)科學(xué)院沈陽(yáng)自動(dòng)化研究所，沈陽(yáng) 110016）

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

2.1 問(wèn)題分析與描述

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

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

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

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

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

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

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

7）活件在加工過(guò)程中，可部分運(yùn)輸?shù)较碌拦ば?，故?jì)劃不考慮活件轉(zhuǎn)運(yùn)時(shí)間。首件試制生成的數(shù)量很少可忽略不計(jì)。

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

2.2 變量定義

1）已知變量

Product產(chǎn)品集合；

p 產(chǎn)品；

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

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

Operation 工序集合；

o o∈Operation 工序；

OutsourcingOpertion 委外工序；

Machine 設(shè)備集合；

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

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

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

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

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

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

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

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

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

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

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

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

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

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加工時(shí)間段,StartTjom與EndTjom分別為開(kāi)始與結(jié)束加工時(shí)間。若不在設(shè)備中加工，EndTjom=StartTjom；

2.3 約束條件

1）釋放時(shí)間約束

活件工序開(kāi)始時(shí)間大于等于產(chǎn)品計(jì)劃釋放時(shí)間。

2）完工時(shí)間約束

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

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

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

4）先后工序約束

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

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

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

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

7）不能跨越工人休息時(shí)間約束

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

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

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

3 仿真實(shí)例

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

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

【】【】

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

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

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