第3章 车间生产计划制定与优化
生产作业计划是数字化智能化车间生产管控体系的中枢神经，它指挥并控制着车间生产转换过程的顺利和高效运行。生产计划体系和相关算法一直在不断发展变化，从最早的面向库存的订货点法到现代的MRP、MRPⅡ、JIT、ERP和APS等，都对生产计划制定与优化技术的改进起到了巨大的推动作用。车间生产计划制定问题本质上是一个约束规划问题，即在产品结构、工艺路线、工作时间、资源能力、订单交期等约束下，最优化安排生产顺序并合理分配执行资源，从而实现综合成本最低、延期风险最小、生产负荷均衡等优化目标。不同生产模式、不同产品类型、不同车间和工艺，生产计划优化模型是完全不同的。问题分析、数学建模、算法求解、应用实践(特别是与APS、MES等系统结合)是科学制定生产计划的几个基本步骤。本章结合汽车、电子、飞机等行业的典型应用案例，对几类车间生产计划优化问题的模型与算法进行详细探讨，高级计划排程系统的技术与应用将在第7章进行介绍。
3.1引言

制造企业的计划体系都是多层次、多视图的，比如销售与运作计划、主生产计划、物料需求计划、外购(外协)计划、车间作业计划、物料配送计划等，在ERP理论体系中对此有详细阐述。即便到车间作业计划层面，生产计划也通常可分为3个阶段： 
阶段1：  车间主计划阶段。该阶段的任务是根据需求(来自订单需求或者上层计划)，考虑库存量和正在执行量，确定一段时期内各类产品的投入量和产出量。
阶段2：  能力评估和产线分配阶段。该阶段的任务是依据主计划结果，进一步分析资源能力、延期风险和成本等因素，确定各项任务在哪条生产线(或关键设备)上完成。
阶段3：  详细作业计划阶段。该阶段的任务是最终确定每个任务的开工时间、生产顺序及所用资源。根据工艺类型和生产特点的不同，还可以进一步分为作业车间计划(job shop planning)、流水车间计划(flow shop planning)、项目型计划(project planning)等类型。
当然，在实际的车间中，上述3个计划阶段未必都同时存在。比如对于汽车加工车间来说，产线分工(冲压焊接涂装总装等)已经非常明确，因此，就只包括阶段1和阶段3的计划。而对于3C电子产品的结构件加工行业来说，由于同类产线众多，必须根据订单规模和交期等因素先进行产线分配，因此阶段2的计划就非常重要。
如图31所示，本章针对5类车间计划问题开展研究，它们涵盖了上述的3个阶段。每个计划问题对应的模型、生产计划问题的特点、生产计划制定与优化的目标均在图中有说明，下面分5节进行详细阐述。


图31本章研究的5类车间计划问题



3.2随机和模糊机会约束下的多产品集结生产计划优化

集结生产计划(aggregate production planning，APP)是针对多产品、多阶段的主生产计划，其目的是在一个中长期的生产计划周期内，确定车间投入、产出和库存水平，以最小的费用来满足不断变化的用户需求。在按库存生产模式以及按预测订单生产模式下，产品主生产计划模型通常可以抽象为APP模型。目前国内外学者分别从确定性优化方法、仿真解析混合算法及随机模糊方法3方面对集结生产计划进行了深入的研究［14］。本节考虑每阶段的投入产出量不相等的实际情况，建立了一个确定型扩展模型，并根据生产需求及设备能力约束的随机模糊性提出了改进的优化模型［3，4］。

3.2.1考虑跨阶段生产的多产品集结生产计划模型
文献［1］考虑产能约束和库存平衡等约束条件，以整个计划周期内的总费用最少为目标，提出了经典的集结生产计划确定型线性规划模型。在该模型中，假设每阶段的投入和产出量是相等的，即没有产品会延期到下一阶段而占用该阶段的生产能力。但在实际中，某些产品的生产周期较长(比如飞机部件)，要跨越多个计划阶段才能完成，在估算某阶段的所需设备工作能力时
须综合考虑本阶段新投入的加工任务及前一阶段未完成的任务。针对该问题，我们提出了一种将投入量与产出量分开考虑的策略，建立了如下扩展模型：  





min∑Ni=1∑Tt=1(ξitYit+ψitIit+πitBit)

s.t. ∑Ni=1wik∑Jj=1ρijk(Yit-Xit)+Xit≤ηkt，k=1，2，…，K，

t=1，2，…，T，J=1，2，…，ni(Ⅰ)

∑tt=1(Yit-Xit)≤0，i=1，2，…，N，t=1，2，…，T(Ⅱ)

Yit+Ii(t-1)-Iit+Bit-Bi(t-1)=dit，i=1，2，…，N，t=1，2，…，T(Ⅲ)

Xit，Yit，Iit，Bit≥0(Ⅳ)

Xi0=Yi0=Ii0=Bi0=0(Ⅴ)
(31)


模型式(31)中，变量的含义如表31所示。


表31变量含义


变量含义


i产品序号，i=1，2，…，N，其中N是产品总数
t阶段序号，t=1，2，…，T，其中T是阶段总数
k工作中心序号，k=1，2，…，K，其中K是工作中心总数
ξit阶段t内产品i的单位生产成本
ψit阶段t内产品i的单位库存成本
πit阶段t内产品i的单位缺货成本
ωik单位产品i在工作中心k上所需的时间
ρijk产品i需在工作中心k上完成的第j道工序尚未开始的概率，其中0<j≤ni，ni表示产品i总的工序数
ηkt阶段t内工作中心k的最大生产能力

续表



变量含义


dit阶段t内对产品i的需求量
Xit阶段t内产品i的投入量，决策变量
Yit阶段t内产品i的产出量，决策变量
Iit阶段t内产品i的库存量，决策变量
Bit阶段t内产品i的缺货量，决策变量


模型(31)的目标函数是使计划周期T内的生产成本∑Ni=1∑Tt=1ξitYit、库存成本∑Ni=1∑Tt=1ψitIit和缺货成本∑Ni=1∑Tt=1πitBit的总和最小。
式(Ⅰ)代表产能约束，即每个阶段所需的总生产时间不大于工作中心的可用能力。定义Zit为t阶段投入的产品i在t阶段未完成的数量(Zit≥0)，则Zit=Zi(t-1)+Xit-Yit。J表示每个阶段未完成的产品在该阶段结束时所处的工序，在阶段t内产品i所需的工作中心k的能力Ckt包括在阶段t内投入并产出的产品所消耗的能力
C1kt=∑Ni=1ωik(Xit-Zit)、阶段t-1内未完成的产品在阶段t内消耗的能力C2kt=∑Ni=1∑Jj=1ρijkωikZi(t-1)和阶段t内未完成的产品在阶段t内消耗的能力C3kt=∑Ni=11-∑Jj=1ρijkωikZit，故阶段t内加工中心k上消耗的总生产能力为


Ckt=C1kt+C2kt+C3kt

=∑Ni=1wik(Xit-Zit)+∑Jj=1ρijkZi(t-1)+1-∑Jj=1ρijkZit

=∑Ni=1wikXit+∑Jj=1ρijk(Yit-Xit)


从而能力约束为


Ckt=∑Ni=1wikXit+∑Jj=1ρijk(Yit-Xit)≤ηkt


ρijk可以通过仿真近似得到。为了计算的方便，假设产品i在整个周期内每一时间点未完成的概率均服从均匀分布，且每一阶段结束时，加工中心k都处于待机状态，即产品i的第j道工序在加工中心k上或尚未开始或已完成。则有


ρijk=产品i的第j道工序在加工中心k上的加工时间完成产品i的整个加工时间



式(Ⅱ)是截止阶段T的投入产出约束，即到阶段T为止，总产出须小于或等于总投入； 式(Ⅲ)是生产和库存(缺货)的平衡约束，且Iit×Bit=0即库存和缺货不能并存； 式(Ⅳ)、式(Ⅴ)给出了初始变量的非负约束和初始条件。
当上述模型的输入量为确定值时，可利用数学软件求得唯一最优解。
3.2.2多产品集结生产计划的随机模糊优化模型

由于集结生产计划跨越的生产周期一般较长，所涉及的数据不仅繁多，且动态多变，为了使计划模型更符合生产实际情况，须定量描述各种不确定因素。考虑到成本系数、生产能力等可从历史数据中推测出一定的规律，假设
ξ~it、ψ~it、
π~it、ω~it和
η~it为随机变量，而市场需求dit因季节性及产品类型的变化具有模糊性，则用模糊变量表示，随机模糊优化问题的求解需要用到随机规划和模糊规划理论。

机会约束规划是由Charnes和Cooper提出的第二类随机规划，其显著特点是随机目标和随机约束条件均以一定的置信水平成立。随机机会约束规划模型如下： 



minf0

s.t.Pr{f(X，E～)≤f0}≥β

Pr{gj(X，E～)≤0}≥αj，j=1，2，…，p
(32)


一般情况下，该模型只能通过随机模拟、神经网络和遗传算法相结合的混合智能算法来近似求解。特殊情况下，可将模型转化为其确定的等价形式，但需满足以下假设条件： 
(1) f(X，E～)和gj(X，E～)都是线性函数； 
(2) 所有的随机变量都相互独立且服从期望和方差已知的正态分布。
基于以上两个假设，有如下定理： 
定理1［5］： 假设随机向量
E=(a～1，a～2，…，a～n，b～)，函数f(X，E～)的形式为
f(X，E～)=a～1x1+a～2x2+…+a～nxn-b～。若ai和b是相互独立的服从正态分布的随机变量，那么Pr{f(X，E～)≤0}≥α当且仅当
∑ni=1E［ai］xi+φ-1(α)∑ni=1Vaix2i+V［b］≤E［b］，其中φ是标准正态分布函数。


用三角模糊数D代表需求量，隶属函数μD表示为


μD=
μLD(x)，d-≤x≤d

μRD(x)，d≤x≤d-

0，其他
(33)



其中，d是模糊数的最可能值，越偏离d，可能性越小。隶属函数是线性的，μLD： ［d-，d］→［0，1］是连续且严格单调递增的，μRD： ［d，d-］→［0，1］是连续且严格单调递减的。
根据模糊数学理论和扩展原理，模糊机会约束规划具有以下定理：  

定理2［6］： 设三角模糊数
r～为(r-，r，r-)，则对任意给定的置信水平γ(0≤γ≤1)，当且仅当

z≥(1-γ)r-+γr


z≤(1-γ)r-+γr时，有Pos{r～=z}≥γ成立，其中Pos{}是可能性测度。
由上面的讨论可知，在假设ξ~it、ψ~it、π~it、ω~it和η~it为已知分布的随机变量和生产需求dit为隶属函数是已知的三角型模糊数的前提下，模型中的随机/模糊机会约束均可转化为各自的确定等价类，即可转化为确定型模型，步骤如下。
步骤1： 建立集结生产计划的随机模糊综合型模型。
假设置信水平分别为α、βkt和γit(0<α，βkt<1，0<γit≤1)，考虑相应的随机因素及模糊需求，将模型式(31)转化为如下的随机模糊模型： 




minf0

s.t. Pr∑Ni=1∑Tt=1(ξ
itYit+ψitIit+πitBit)-f0≤0≥α

Pr∑Ni=1［∑Jj=1ρijk(Yit-Xit)+Xit］-ηkt≤0≥βkt，

k=1，2，…，K，t=1，2，…，T，J=1，2，…，ni

∑T′t=1(Yit-Xit)≤0，i=1，2，…，N，T′=1，2，…，T

Pos(Yit+Ii(t-1)-Iit+Bit-Bi(t-1)=dit)≥γit，i=1，2，…，N，

t=1，2，…，T

Xit，Yit，Iit，Bit≥0

Xi0=Yi0=Ii0=Bi0=0
(34)


步骤2： 确定随机因素的分布及模糊参数的隶属函数。
正态分布可以很好地反映独立变量随平均值波动的事实，且市场需求也随着外部环境而变动，故为了简化模型，假设模型式(34)中所有的随机变量都服从期望和方差已知的正态分布，需求量是已知隶属函数的三角型模糊数。

步骤3： 结合定理1和定理2，可将不确定规划模型转化为如下确定的等价形式： 




minf0

s.t.∑Ni=1∑Tt=1(E［ξ
it］Yit+E［ψit］Iit+E［πit］Bit)-f0+

-1(α)∑Ni=1∑Tt=1(V［ξit］Y2it+V［ψ
it］I2it+V［πit］B2it)≤0

∑Ni=1E［ωik］∑Jj=1ρijk(Yit-Xit)+Xit-E［ηkt］+

-1(βkt)∑Ni=1V［ωik］∑Jj=1ρijk(Yit-Xit)+Xit2+V［ηkt］≤0

∑T′t=1(Yit-Xit)≤0，i=1，2，…，N，T′=1，2，…，T

Yit+Ii(t-1)-Iit+Bit-Bi(t-1)≥(1-γit)dit+γitdit


i=1，2，…，N，t=1，2，…，T

Yit+Ii(t-1)-Iit+Bit-Bi(t-1)≤(1-γit)dit+γitdit


i=1，2，…，N，t=1，2，…，T

Xit，Yit，Iit，Bit≥0

Xi0=Yi0=Ii0=Bi0=0
(35)


步骤4： 经过确定性转化所得的模型(35)是一个规模较大的非线性规划模型，可借用Lingo等数学软件求解。

从随机模糊优化的角度分析，对于特定的满意水平来说，模型的最优解是随机模糊优化问题的模糊解，即特定意义上的最优解。因为此最优解依赖于决策者的偏爱和主观性，即置信水平α、βkt和γit的取值，置信水平越大，代表决策者的满意度越高。
3.2.3案例分析

假设某工厂在计划期1、2、3内准备生产P1、P2、P3等3种产品，成本系数、需求矩阵、加工时间、加工路线等基本参数如表32、表33所示。该工厂有4个工作中心，每个加工中心的生产能力为2400min/周。假定该系统是闭环式的，即在计划期外无额外需求，因此在第3阶段末需较高成本以维持剩余库存。此外，假设此案例中允许生产延期，即上一阶段未完成的产品可以累积到下一阶段继续加工。
首先求解确定型扩展模型(31)。取成本系数和时间系数为期望值，需求量为三角模糊数的中间值，3个阶段的总需求量是1250个，计算得到总产出量为1176个，总成本为208125元。


表32成本系数

元



成本单位生产成本(期望，方差)单位库存成本(期望，方差)单位缺货成本(期望，方差)


阶段123123123
P1100，100100，100100，10025，6.2525，6.2525，6.25400，1600400，1600400，1600
P2150，225150，225150，22530，930，9150，225450，2025450，2025450，2025
P3125，156.3125，156.3125，156.335，12.335，12.3200，400500，2500500，2500500，2500


表33模糊需求量及加工时间、路线

需求量单位： 个，时间单位： min



产品

模糊需求量(三角模糊数)操作1操作2操作3

阶段1阶段2阶段3工作中心(时间期望，时间方差)



P1(125，150，175)(100，125，150)(140，160，180)MC1(5，0.25)MC4(10，1)MC3(4，0.16)
P2(90，100，110)(125，150，175)(125，150，175)MC1(7，0.49)MC2(7，0.49)MC3(5，0.25)
P3(120，125，130)(160，165，170)(120，125，130)MC1(7，0.49)MC2(6，0.36)MC3(10，1)




然后求解随机模糊扩展模型(32)。假设α=0.95，βkt=0.85，γit=0.85，计算得到总产出量为1065个，总期望成本为308557元，对应的最佳生产计划为


Xit=
155120158

10212195

98110107，Yit=150125157

10012395

96  108111，

Iit=501

200

240，Bit=0  0  0

0  2760

285312



进一步研究显示： γ值越大即满足用户需求的可能性水平越高时，总期望成本也会随之升高。表34
给出了用户满意度为100%条件下(即用户的需求完全能够满足)，置信因子α、生产能力成本β对生产水平及总成本的影响。结果表明： α、β越大，总成本越高，且生产能力因子β对生产成本的影响速率远远大于置信因子α。在实际生产中，应在尽可能满足生产能力的前提下降低成本，因此可以通过控制生产能力消耗的置信水平来控制总成本，以取得生产成本和生产能力的一个最佳平衡。


表34置信水平α、β不同的结果比较


β


α

0.50.60.70.750.80.850.9



0.5215218216794218462219389220440221614223158
0.6234675236423238274239302240467241770243483
0.7257023258981261053262204263509264967266885
0.75271438273540275765277002278403279970282031
0.8287640289916292326293665295183296879299111
0.85305593308073310700312159313812315660318092
0.9328991331751334672336295338135340191342896

3.3基于风险评估的多生产线计划优化
满足交货期是生产计划的基本要求。虽然计划寻优时一定会考虑交货期约束，但由于生产过程中存在多种随机因素，计划的实际执行结果必然存在不满足交货期的风险。本节定义了生产计划的风险评估指标，将生产计划导入预先建立的计划仿真模型，驱动模型按离线仿真机制运行，评估计划的可执行性和风险大小，并设计了混合优化算法，寻找延期风险最小的优化生产计划。
3.3.1生产计划的风险值定义

包含n个任务的生产计划X在执行过程中，由于车间存在设备故障、生产时间波动等随机因素R，任务i的实际完工周期fi(X，R)可能大于所要求的交货期DLi。定义P{fi(X，R)>DLi}为任务i的风险值。
若将风险指标最小作为生产计划优化的目标，则该目标可表述为


min［P{f1(X，R)>DL1}，…，P{fi(X，R)>DLi}，…，P{fn(X，R)>DLn}］(36)



也可设定风险指标的阈值ai，寻找使得各个任务的完工周期FTi尽可能短的排产计划［7］，可表示为



min{minFT1，minFT2，…，minFTi，…，minFTn}


s.t. P{fi(X，R)≥FTi}<ai，1≤i≤n
(37)



一般的数学模型难以准确表达复杂且动态的车间生产系统，尤其是式(36)和式(37)这些含有概率计算的问题求解十分困难。仿真模型可实现对车间元素及元素间交互关系的模拟，并通过提前对车间随机因素进行统计分析，实现对随机过程的规律再现，在车间仿真模型中引入加工时间波动、设备故障等车间随机因素，并导入生产计划，预演车间生产物流过程，实现对目标数据的取样。重复进行r次计划仿真试验，分别记录所有任务完成时的仿真时刻，
可以快速获得最大完工周期(makespan)数据，并应用统计的方法获得风险值评估，其计算公式可表示为



P{fi(X，R)>DLi}=∑rj=1(fj(X，R)>DLi)r，1≤i≤n(38)


3.3.2生产计划风险评估与优化模型
1. 问题描述


含有m条生产线的并行流水车间，每一条生产流水线结构相似，能够加工所有类型产品。每一条生产线上加工产品类型需要切换时，需要停线进行生产准备工作，包括替换加工程序、刀具、夹具等，一般来说应尽量减少同一生产线上加工产品类型的切换，以提升生产线利用率，保障产品质量的一致性。当对某一种类型产品进行加工时，生产线工序机台分配、生产线控制调度都是事先调整确定的，生产线按照工件上料顺序完成所有加工作业。

n个生产任务需要在并行流水车间生产，其调度只需要解决每个任务分配在哪条生产线上加工，以及各生产线上加工任务的先后排序这两个根本问题。生产计划风险评估A(X)是指对于一个生产计划X∈θ，求解获得每一个任务i的风险，值即该任务完工时间fi(X，R)大于任务交期DLi的概率P{fi(X，R)>DLi}的集合，可表达为


A(X)=［P{f1(X，R)>DL1}，…，P{fi(X，R)>DLi}，…，

P{fn(X，R)>DLn}］(39)


而生产计划风险优化则是指从解空间θ中寻找出最优X*，使得所有任务的综合风险最小。对于每一个任务i，设计其惩罚函数为


gi(X)=
eλ(P{fi(X，R)>DLi}-ai)-1，P{fi(X，R)>DLi}>ai


0，其他(310)



其中，ai为任务i的风险指标的阈值，λ为大于0的惩罚系数。那么生产计划风险优化的综合目标函数可定义为所有任务的平均惩罚值最小，其表达公式为


G(X*)= minX∈θ1n∑ni=1gi(X)(311)



2. 基于仿真的生产计划风险评估方法
采用仿真结合遗传算法的方法对该并行流水线调度问题进行求解，其过程如图32所示。遗传编码采用扩展的单染色体顺序编码方式［8］，以自然整数作为分隔。具体而言，以任务编号(1~n)为染色体基因，在任务最大编号n后增加m-1(m为并行生产线数量)个连续的自然整数，以6任务、3生产线为例，染色体基本基因为1~6，增加染色体的长度到6+3-1=8，［4，2，7，1，6，5，8，3］表示任务4、2在生产线1上先后执行，任务1、6、5在生产线2上按顺序完成，任务3在生产线3上进行。


图32求解算法流程图



选择所有任务的最大完工时间作为染色体适应度值，在建立的包含工艺、时间等约束的仿真模型的基础上，根据个体染色体的基因编码规则进行以上解码过程，并据此设置仿真策略，通过仿真的方法获得所有任务的最大完工时间。选择算子为根据个体适应度值以轮盘赌的方式选择亲代个体，交叉算子为次序交叉OX，变异算子为基因元素两个整数位置交换，根据实际问题规模选择合适的种群数量和最大迭代数，实施遗传迭代，获得最优生产计划。在仿真模型中引入随机因素，模拟智能车间系统设备故障、加工时间波动等典型生产扰动事件，输入所获得的优化生产计划进行多次仿真，统计各个任务完工时间，并基于该生产计划计算各个任务