-
生产批量计划(lot-sizing planning,LSP)是企业制定主令生产计划(master production schedule,MPS)及物料需求计划(material requirements planning,MRP)所要解决的关键问题。经济订购批量(economic order quantity,EOQ)方法是最早用于平衡生产准备费用和库存费用的算法,但是LSP问题本质上是非确定性(NP)困难的组合优化问题,传统的数学规划算法难以有效解决此类问题,为此,Wagener和Whitin于1958年最早提出了著名的W-W启发式算法,用于解决需求固定不变的LSP问题,随后在考虑市场需求不确定性因素影响时,出现了一系列以W-W算法为蓝本的改进启发式算法[1-4]。
在实践中,为了适应市场的变化和增强需求预测的可靠性,LSP往往需要以一种随时间不断“滚动”的方式进行,即时域滚动计划(rolling horizon planning,RHP)[5],同时在实际生产时往往不希望每个周期的生产计划波动太大,为此出现了对LSP稳定性的要求,Steele最早考虑生产计划的稳定性,Berry等则在1979年针对LSP稳定性问题最早提出了冻结期(freezing period,FP)的概念,即在冻结期内生产计划不能再进行调整,该方法至今仍被广泛应用于LSP问题中以保持生产计划的稳定性[6]。另外,关于生产计划稳定性的评价和度量,也出现了很多不同的模型,其中Sridharan等提出的稳定性测量方法至今仍被广泛采用[7]。近些年来,随着智能优化算法的迅速发展,遗传算法(GA)、蚁群算法(ACO)、微粒群算法(PSO)等智能算法也逐渐用于LSP问题[8-12],现有智能优化算法主要用于解决静态的LSP问题,在动态RHP问题中的应用还不多见。总之,LSP问题是企业批量生产必须面临的问题,而且针对不同的产品及其生产过程,LSP具有不同的决策模型。
近十年来,我国人造板行业进入了飞速发展的阶段,每年新增企业均在500家左右,然而,由于人造板企业投入门槛较低,不仅呈现出规模小的特点,而且市场无序竞争的现象比较突出。人造板市场的不稳定性迫使企业要有可靠的生产批量计划加以应对,但是现在人造板行业的生产批量计划仍然按照订单和原材料而定,根本无法动态反映市场和需求的波动,容易导致企业市场竞争力下降,规模不大的企业甚至会面临被市场淘汰的危险境地。目前,关于人造板行业的LSP问题的研究还很少见,但是该问题又是行业健康发展不可回避的问题之一,所以本研究将以刨花板生产为例,在考虑生产成本、库存成本和缺货损失等因素的基础上,建立LSP问题的数学模型,并且设计改进的微粒群算法作为LSP问题时域滚动计划的智能优化算法。
-
基本的LSP问题是以生产成本最低为目的,根据市场需求优化每个时期的生产批量的数量,其中市场需求是依据市场变化和订单状况制定的预测值。因为市场需求和订单往往是动态变化且具有随机性,所以在求解LSP问题时,通常只能保证未来一定时期内需求预测的可靠性,这就要求实际LSP问题求解应该以某种沿时间“滚动”的方式不断进行,这就是时域滚动计划的基本思路。
RHP方法的基本概念和执行过程如图 1所示。对于总共T个计划周期的LSP问题,值得注意的是,这里的周期T的划分视具体问题而定,可以是月、周、天,甚至小时等,首先确定短期的计划周期数n,n的值取决于实际的需求预测周期长度,然后对最初的n个周期求解LSP问题。在完成前一次n个周期的LSP问题求解后,向后移动一个周期,并补充新的需求预测数量,再次求解新的n个周期组成的LSP问题,然后以此类推地沿时间域“滚动”重复求解LSP问题,为便于叙述,将每次重新的LSP称为循环,显然,对于T个规划周期,需要进行(T-n+1)次循环。因为每次LSP的第一个周期的需求量在未来不再改变,所以每个循环中仅执行LSP的第一个周期的批量计划。当要考虑LSP问题的稳定性时,通常设置一定长度的冻结周期为FP,即在每次LSP问题中,前(FP-1)个周期的生产批量值维持上次LSP问题所对应的解不变,因为前次LSP的第一个周期计划已经执行,所以仅剩(FP-1)个周期被冻结。
为了更直观地解释RHP方式的执行过程,本文以一个总计划周期为8个月的LSP问题为例加以说明,其中计划周期n为5个月,冻结周期为3个月。该问题一共需要进行4次循环LSP问题求解,具体的过程在表 1中列出,其中:dj表示周期j的需求量;di, j表示第i次循环Ci时周期j的需求量,该值的变化反映了需求随市场变化的情况;Qi, j表示循环Ci时周期j的生产计划量。以循环C2为例,在5个周期的LSP中,前两个周期的生产计划量维持C1循环对应的计划量Q1, 2和Q1, 3,这反映了冻结期为3个月的效果。最终执行的生产批量计划都是每个循环第1个周期的计划量,最后一次循环则全部执行。
表 1 时域滚动计划表(冻结周期为3个月)
Table 1. Schedule of rolling horizon planning (freezing period was 3 months)
循环
Cycle计划周期月份
Months of planning horizon1 2 3 4 5 6 7 8 C1 d1 d2 d3 d4 d5 Q1, 1 Q1, 2 Q1, 3 Q1, 4 Q1, 5 C2 d2, 2 d2, 3 d2, 4 d2, 5 d6 Q1, 3 Q1, 3 Q2, 4 Q2, 5 Q2, 6 C3 d3, 3 d3, 4 d3, 5 d3, 6 d7 Q1, 3 Q2, 4 Q3, 5 Q3, 6 Q3, 7 C4 d4, 4 d4, 5 d4, 6 d4, 7 d8 Q2, 4 Q3, 5 Q4, 6 Q4, 7 Q4, 8 计划Plan Q1, 1 Q1, 2 Q1, 3 Q2, 4 Q3, 5 Q4, 6 Q4, 7 Q4, 8 注:dj表示周期j的需求量,di, j表示第i次循环Ci时周期j的需求量,Qi, j表示循环Ci时周期j的生产计划量。Notes: dj is the requirement value at j-th period. di, j is the requirement value at Ci and j-th period. Qi, j is the execution lot-sizing at Ci and j-th period. -
根据人造板产业特点,在构建人造板生产过程LSP问题的数学模型时,以生产成本最低为优化目标,暂时不考虑生产批量计划的稳定性,其中生产成本主要由制造成本、库存成本、缺货损失和启动成本4个部分组成。制造成本主要包括产品的原料成本和人工费用等,库存成本是指产品存放所需的费用,缺货损失是生产计划少于需求量时造成缺货而导致的收益损失,启动成本主要指生产线每次开动所消耗的基本能源费用。在数学模型中,采用单个产品的制造成本、启动成本、库存成本及缺货损失作为参数计算总成本,并且以上4部分成本在每个周期是动态变化的,这也符合人造板生产的实际情况;另外,在数学模型中没有考虑原材料的约束,即假设不会出现原材料短缺的情况。
LSP问题的数学模型如下:
$$ \text{Minimize}\;Z_{i}=\sum\limits_{t=i}^{i+n-1}\left(p_{i, t} Q_{i, t}+h_{i, t} s_{i, t}+b_{i, t} r_{i, t}+q_{i, t} Y_{i, t}\right) $$ (1) $$ \begin{array}{l}{\text { Subject to }} \\ {\qquad \sum\limits_{t=i}^{i+n-1} Q_{i, t}=\sum\limits_{i=i}^{i+n-1}\left(d_{i, t}-s_{i-1, i-1}+r_{i-1, i-1}\right)} \\ {i=1, 2, \cdots, T-n+1}\end{array} $$ (2) $$ n \leqslant T $$ (3) $$ s_{0, 0}=r_{0, 0}=0 $$ (4) $$ Q_{i, t}, s_{i, t}, r_{i, t} \geqslant 0, \\ i=1,2,\cdots ,T-n+1,t=i,i+1,\cdots ,i+n-1 $$ (5) $$ Y_{i, t} \in\{0, 1\}, Y_{i, t}=\left\{\begin{array}{ll}{0} & {\text { if } Q_{i, t}=0} \\ {1} & {\text { otherwise }}\end{array}\right. $$ (6) $$ X_{i, t}=Q_{i, t}-d_{i, t}+s_{i, t-1}-r_{i, t-1}, $$ $$ i=1, 2, \cdots, T-n+1, t=i, i+1, \cdots, i+n-1 $$ $$ s_{i, t}=\left\{\begin{array}{ll}{\left|X_{i, t}\right|} & {\text { if } X_{i, t}>0} \\ {0} & {\text { otherwise }}\end{array}\right.\\ r_{i, t}=\left\{\begin{array}{ll}{\left|X_{i, t}\right|} & {\text { if } X_{i, t}<0} \\ {0} & {\text { otherwise }}\end{array}\right. $$ (7) $$ \begin{array}{c}{Q_{i, t} \leqslant C_{i, t}, i=1, 2, \cdots, T-n+1}, \\ {t=i, i+1, \cdots, i+n-1}\end{array} $$ (8) 式中:Zi是优化的代价函数(cost function);n是滚动计划期的长度; pi, t代表第i次循环中,第t个周期的单位制造成本;Qi, t代表在第i次循环中,第t个周期的计划生产批量;hi, t代表在第i次循环中,第t个周期的单位库存成本;si, t代表在第i次循环中,第t个周期的库存量;bi, t代表在第i次循环中,第t个周期的单位缺货损失;ri, t代表在第i次循环中,第t个周期的缺货量;qi, t代表在第i次循环中,第t个周期的设备启动成本;如果第i次循环中,第t个周期进行生产,Yi, t取值为1,否则取值为0;di, t代表在第i次循环中,第t个周期的需求量;T是计划期的总长度;Xi, t是根据前一个周期的执行计划情况计算当前周期的库存和缺货量的中间变量;Ci, t代表在第i次循环中,第t个周期的最大生产能力。
目标函数式(1)包括了制造成本、库存成本、缺货损失、启动成本4个部分;约束(2)表示生产批量计划与需求总量平衡方程;约束(3)表示每次循环的LSP问题的长度不能超过总计划周期;约束(4)表示初始库存和缺货量均为0;约束(5)表示计划生产批量、库存量和缺货量不能为负值;约束(6)表示二进制的决策变量及其计算方法;约束(7)表示每个周期需求量、计划量、库存量和缺货量之间的平衡关系,以及库存和缺货量的计算方法;约束(8)表示每个周期的生产能力限制。
-
人造板LSP是一种NP困难的混合整数规划问题,启发式W-W算法及其改进算法在一定程度上为LSP问题求解提供了可行的途径,但是此类确定性算法只能给出需求量确定的LSP问题的次优解,为此,一些智能优化算法被用于求解LSP问题,其中最常用的是遗传算法。因为GA主要用于求解组合优化问题,所以在求解LSP问题时,GA通常只能通过二进制编码确定将需求量安排到哪些周期中生产,具体的生产计划的数量仍需要借助某种确定性算法确定,因此,实际求解时通常采用基于GA的混合优化算法。
微粒群算法是一种用于求解复杂函数优化问题的群集智能优化算法,通过简单地改变个体定义,改进的PSO算法被广泛应用于求解各类生产调度问题。与调度问题类似,LSP问题本质上也是组合优化和连续函数优化的结合。为此,本研究设计一种改进的PSO算法用于求解人造板LSP问题。在PSO算法中,每个微粒子个体具有位置和速度两个矢量,其中位置矢量代表问题在解空间中的一个可行解,个体以随机的方式在解空间中搜索,并通过信息共享机制,不断更新群体发现的最优解,具体的位置和速度更新公式如下式所示:
$$ \left\{\begin{array}{c}{v_{i, d}^{j+1}=w v_{i, d}^{j}+\varphi_{1} \operatorname{rand}_{1}( )\left(p_{\text { best }}-x_{i, d}^{j}\right)+} &\\ {\varphi_{2} \operatorname{rand}_{2}( )\left(g_{\text { best }}-x_{i, d}^{j}\right)} \\ {x_{i, d}^{j+1}=x_{i, d}^{j}+v_{i, d}^{j+1}}&\end{array}\right. $$ (9) 式中:xi, dj和vi, dj分别表示第j次迭代中,第i个微粒子的位置和速度矢量的第d维数值;w是惯性权值,φ1和φ2是两个常数;pbest和gbest分别表示每个微粒子个体和整个群体迄今为止找到的最优解。rand1()和rand2()表示两个随机数。
PSO中微粒子个体通过适应值(fitness)来衡量位置的优劣,在求解人造板LSP时,适应值函数的计算公式如下:
$$ f=\sum\limits_{i=i}^{i+n-1}\left[p_{i, t} Q_{i, t}+h_{i, t} s_{i, t}+b_{i, t} r_{i, t}+q_{i, t} Y_{i, t}\right] $$ (10) 式中:f是优化代价函数(cost function),也被称为目标函数。
为了满足式(2)~(8)的约束条件,本研究对经典PSO算法作了以下改进:1)为了保证由算法确定的生产批量计划是整数值,在改进的PSO算法中,所有个体都在连续的实数空间中搜索,但是在位置矢量更新后,对位置矢量的每一维分量值进行取整后作为最终用于计算适应值的位置矢量;2)为了满足式(2)所示的平衡关系,对于n周期的LSP问题,首先在(n-1)维空间中进行搜索,即将每个个体的位置和速度设置为(n-1)维矢量,然后用n个周期的需求总量减去(n-1)维位置矢量的各维分量的和,如果计算得到的差值是非负的,则将其直接补充为n维位置矢量的最后一维分量值,否则在n维解空间中采用随机方式重新产生新的位置矢量。
改进后的PSO算法流程如图 2所示,其中初始化主要包括设置种群的规模和相关参数、在(n-1)维解空间中初始化个体的位置和速度矢量;然后根据公式(9)更新个体的位置并取整,并采用前面提到的方法将个体位置矢量补充为n维矢量;接着根据式(10)计算个体的适应值,并通过比较确定群体的最优解;最后根据需求量和生产批量计划确定每个周期的库存量或缺货量。
-
为了验证LSP数学模型及改进PSO算法的有效性,在Matlab软件中进行建模和仿真研究。人造板LSP数学模型以年产10万m3的刨花板生产线为原型,设置计划周期的单位为月,总计划周期为12个月,每3个月计算一次生产批量计划,即LSP问题的周期长度为3个月。同时,利用在一定范围内随机分布的数值模拟市场需求量、制造成本、库存成本、缺货损失、启动成本等参量的动态变化特点,其中成本部分的变化范围主要依据目前刨花板生产的平均成本而定,相关的LSP数学模型的仿真参数设置如表 2所示。表中需求量在7 500~8 500 m3之间均匀分布,每次循环的每个周期的需求量还要附加一个在区间(100,150) m3上均匀分布的扰动量,以模拟突发的市场需求变化。
表 2 LSP数学模型的仿真参数
Table 2. Simulation parameters of LSP model
参数Parameter 取值Value 总计划周期/月Total planning horizon/month 12 LSP计划周期/月LSP planning period/month 3 需求量Requirement/m3 U(7 500, 8 500) 需求扰动Requirement disturbance/m3 U (100, 150) 制造成本/(元·m-3)
Manufacture cost/(CNY·m-3)U (2 000, 2 400) 库存成本/(元·m-3)
Stock cost/(CNY·m-3)U (100, 150) 缺货损失/(元·m-3)
Shortage cost/(CNY·m-3)U (300, 400) 启动成本/元Setting cost/CNY U (4 000, 4 500) 改进的PSO算法的相关参数设置为:种群规模为20,最大迭代次数为500,更新公式(9)中的两个常数φ1和φ2均为2.1,惯性权值w从开始迭代时的0.9至最后一次迭代时的0.4按线性变化。为了反映生产能力对算法的影响,首先在无生产能力约束情况下,取消公式(8)的约束条件,采用PSO算法求解LSP问题,然后将式(8)中的参数Ct设为12 000 m3,即每月的最大产量为12 000 m3,再次采用PSO算法求解同样的LSP问题。
仿真结果如表 3~7所示,其中表 3和表 4中数据均根据表 2列出的取值范围随机生成。表 3列出了每次循环所涉及的3个周期的市场需求预测量,从表中可以看出,每次循环将增加一个新周期的需求预测量,并且同一周期的需求量在不同循环中存在差异,这种变化模拟了市场需求的不确定性,最后一行是每个月的实际需求量。表 4列出了每个计划周期的单位产品生产成本值,通过数值变化模拟每个计划周期生产成本的波动。表 5列出了两种情况下采用改进PSO算法求解LSP问题的过程,表中Q1代表没有生产能力约束时的生产批量计划,Q2代表有生产能力约束时的生产批量计划,从表中数据值可以看出,有生产能力约束时,所有循环的LSP问题的解均小于设定的12 000 m3,表中最后一行表示两种情况下最终执行的生产批量计划。表 6和表 7分别列出了两种情况下决策变量的取值。
表 3 市场需求量变化情况
Table 3. Change in the market requirement
m3 循环Cycle 月份Month 1 2 3 4 5 6 7 8 9 10 11 12 1 7 919 8 083 8 062 2 8 694 8 672 7 927 3 8 162 8 060 8 247 4 7 538 7 561 7 526 5 8 452 8 255 8 528 6 8 462 8 758 7 929 7 8 114 8 017 7 787 8 7 555 7 485 7 822 9 8 315 8 412 8 106 10 7 790 7 800 8 323 需求量
Requirement7 919 8 694 8 162 7 538 8 452 8 462 8 114 7 555 8 315 7 790 7 800 8 323 表 4 单位产品生产成本分布 元/m3
Table 4. Cost of the unit product CNY/m3
成本Cost 月份Month 1 2 3 4 5 6 7 8 9 10 11 12 生产成本Production cost 2 052 2 243 2 266 2 038 2 366 2 445 2 337 2 361 2 437 2 120 2 097 2 380 仓储成本Stock cost 148 149 144 142 143 144 144 144 148 146 145 140 缺货损失Shortage cost 389 303 305 348 388 363 380 314 374 386 339 315 启动成本Setting cost 4 053 4 294 4 175 4 240 4 489 4 205 4 477 4 216 4 380 4 450 4 079 4 077 表 5 生产批量时域滚动计划过程
Table 5. Schedule process of rolling horizon lot-sizing planning
m3 循环
Cycle生产批量计划
Lot-sizing planning月份Month 1 2 3 4 5 6 7 8 9 10 11 12 1 Q1 16 002 0 8 062 Q2 11 696 4 310 8 058 2 Q1 611 8 672 7 927 Q2 4 917 8 672 7 927 3 Q1 8 162 16 307 0 Q2 8 162 11 996 4 311 4 Q1 22 625 0 0 Q2 11 986 3 133 7 506 5 Q1 0 1 620 8 528 Q2 4 004 8 255 8 528 6 Q1 1 827 8 758 7 929 Q2 8 462 8 758 7 929 7 Q1 8 114 8 017 7 787 Q2 8 114 8 017 7 787 8 Q1 7 555 7 485 7 822 Q2 7 555 7 485 7 822 9 Q1 8 315 8 412 8 106 Q2 8 315 8 412 8 106 10 Q1 7 790 16 123 0 Q2 7 818 11 999 4 096 执行计划 Q1 16 002 611 8 162 22 625 0 1 827 8 114 7 555 8 315 7 790 16 123 0 Execution plan Q2 11 696 4 917 8 162 11 986 4 004 8 462 8 114 7 555 8 315 7 818 11 999 4 096 注:Q1代表没有生产能力约束时的生产批量计划,Q2代表有生产能力约束时的生产批量计划。Notes: Q1 represents LSP without the constrains of production capacity, and Q2 represents LSP with the constrains of production capacity. 表 6 无生产能力约束最优决策
Table 6. Optimization decision without constrains of production capacity
m3 项目Item 月份Month 1 2 3 4 5 6 7 8 9 10 11 12 计划Plan 16 002 611 8 162 22 625 0 1 827 8 114 7 555 8 315 7 790 16 123 0 库存Stock 8 083 0 0 15 087 6 635 0 0 0 0 0 8 323 0 缺货Shortage 0 0 0 0 0 0 0 0 0 0 0 0 表 7 有生产能力约束最优决策
Table 7. Optimization decision with constrains of production capacity
m3 项目Item 月份Month 1 2 3 4 5 6 7 8 9 10 11 12 计划Plan 11 696 4 917 8 162 11 986 4 004 8 462 8 114 7 555 8 315 7 818 11 999 4 096 库存Stock 3 777 0 0 4 448 0 0 0 0 0 28 4 227 0 缺货Shortage 0 0 0 0 0 0 0 0 0 0 0 0 根据表 3的数据统计,此次仿真中12个月计划周期的总共市场需求量为97 124 m3,表 5最后一行最终执行的生产批量计划Q1和Q2的总和分别都是97 124 m3,从而满足式(2)的总量平衡约束。
为了验证改进PSO算法求解的优越性,本研究对3种情况下的生产成本总值加以比较,首先计算不采用LSP的理想情况下的生产成本总值,即每个周期的生产批量计划严格等于相应周期的市场需求,这种情况下不会产生库存和缺货,根据式(10)计算得到生产总成本为2.20亿元。然后,将无生产能力约束情况下的生产批量计划Q1代入式(10),计算出生产总成本为2.16亿元。最后,将有生产能力约束情况下的生产批量计划Q2代入式(10),计算出生产总成本为2.18亿元。计算结果表明:以第一种情况为基准,在无生产能力约束情况下,采用改进PSO算法获得的生产批量计划可以节约1.8%的成本,有生产能力约束时可以节约近0.9%的成本。虽然无生产能力约束情况下的生产批量计划更能节约成本,但实际生产过程中一定会存在生产能力约束,所以Q2更加接近实际情况,并且随着式(8)中生产能力约束量Ci, t数值的增加,采用改进PSO算法求解时总生产成本具有更大的节约空间,但同时也会要求更高的库存水平。
-
对于生产规模不断扩大的人造板行业,合理地规划和安排生产计划,不仅可以在不改变生产环境的前提下进一步节省生产成本,而且能够达到动态适应市场需求变化的目的,有效的生产批量计划的制定也正逐渐成为提升企业核心竞争力的关键。虽然,针对批量生产优化的LSP问题的发展已经超过半个世纪,但是在人造板行业中的应用研究还不多见。为此,本研究根据人造板生产的成本组成,建立了以成本最小化为目标的LSP问题的数学优化模型,并且针对时域滚动计划下的动态LSP问题,提出改进的降维搜索PSO优化算法。与现有用于求解LSP问题的群集智能优化算法相比,本研究提出的改进PSO算法不再需要编码和解码等离散化过程,从而在满足优化要求的同时有效控制了算法的复杂度。本研究是人造板批量生产优化方面的初步研究,研究结果表明:针对不断变化的市场需求,采用时域滚动计划方式,能够在节约成本的基础上,动态调整生产计划以适应市场需求;同时,针对NP困难的LSP问题,群集智能优化算法能够在合理的时间内提供可行的优化解,从而为LSP问题提供一类有效的解决途径。
本研究在优化目标中仅考虑了制造成本、库存成本、缺货损失、启动成本4个经济影响因素,而生产成本的实际影响因素还很多,譬如考虑原材料的约束、多种规格产品的综合生产计划等。为此,在今后的研究中,需要进一步完善LSP问题的数学模型。此外,为了考虑生产计划的波动性和稳定性,在LSP问题优化时,可以采用具有冻结期的时域滚动计划方法。虽然本研究提出的改进PSO算法能够有效求解动态LSP问题,但是从优化角度来看,还有较大的研究空间,特别是将PSO算法的改进与其他启发式算法融合,进一步提高算法求解的精度和速度,也是今后研究的主要方向。
Rolling horizon lot-sizing planning of wood-based panel based on an improved particle swarm optimization
-
摘要:
目的生产批量计划是企业制定主令生产计划和物料需求计划的依据,生产批量计划的优化也是企业节约成本和原料的关键所在。目前人造板企业都采用批量生产模式,并且依据事先设定的生产计划确定各个阶段的生产任务,但随着市场竞争的日益激励和个性化需求的提高,每个阶段的实际生产任务通常需要根据市场需求及时调整。为此,针对人造板生产批量计划问题,提出基于微粒群优化算法(PSO)的时域滚动计划。 方法首先,根据人造板批量生产特点,制定决策变量和约束条件,建立生产批量计划的混合整数决策模型。然后依据决策模型的约束条件,采用降维搜索的方式,提出改进的微粒群求解算法。最后,采用时域滚动计划进行模拟仿真。 结果仿真结果表明:对于年产10万m3的刨花板生产线而言,以3个月作为一个滚动计划单元,在12个月的生产批量计划中,采用改进PSO算法获得的生产批量计划可以节约1.8%的成本,有生产能力约束时可以节约近0.9%的成本。 结论对于人造板批量生产模式,时域滚动计划能够使得生产计划动态满足市场需求,同时时域滚动计划模型是一类非确定性(NP)困难问题,智能群集优化算法为此类问题的求解提供了较好的解决途径。未来的研究可以关注生产批量计划问题数学模型的完善以及智能优化算法设计方面。 Abstract:ObjectiveIn general, lot-sizing planning (LSP) is the basis of master production schedule and material requirements planning. Obviously, optimization of LSP is the key to save cost and materials. At present, bulk-production mode is widely adopted in wood-based panel industries. For arranging the productive task, the detail planning needs to be made in advance. However, the scheduled planning usually needs to be re-planned to cope with the change of market requirement dynamically. For this reason, an improved particle swarm optimization (PSO) and a kind of rolling horizon planning (RHP) method are proposed to solve the LSP problem of wood-based panels in this paper. MethodFirstly, according to the characters of production process, a series of decision variables and constrains were determined, and then, a mathematical mixed integer decision method was built for LSP problem. Secondly, an improved PSO algorithm was designed by reducing the dimension of the solution space. At last, with RHP method, the improved PSO algorithm was used to solve a series of sub-LSP problems repeatedly. A simulation example was designed to verify the performance of the LSP model and improve PSO algorithm. ResultAccording to the simulation results, to a wood-based panel production line with an annual output of 100 000 m3, when the planning horizon and total planning period were set to 3 months and 12 months respectively, 1.8% production cost could be saved through RHP method and the improved PSO approach. In addition, to the same model with production capacity constrains, the production cost could be reduced by 0.9%. ConclusionRHP is an efficient way to make lot-sizing planning of wood-based panel. The important advantage of RHP is that the production schedule could be adjusted with the changing market requirement dynamically. Due to the NP-hard of RHP, the intelligent swarm optimizations could solve these problems with an acceptable period of time. In addition, future research will focus on the model of LSP with actual constrains and the algorithms of intelligent swarm optimization. -
表 1 时域滚动计划表(冻结周期为3个月)
Table 1. Schedule of rolling horizon planning (freezing period was 3 months)
循环
Cycle计划周期月份
Months of planning horizon1 2 3 4 5 6 7 8 C1 d1 d2 d3 d4 d5 Q1, 1 Q1, 2 Q1, 3 Q1, 4 Q1, 5 C2 d2, 2 d2, 3 d2, 4 d2, 5 d6 Q1, 3 Q1, 3 Q2, 4 Q2, 5 Q2, 6 C3 d3, 3 d3, 4 d3, 5 d3, 6 d7 Q1, 3 Q2, 4 Q3, 5 Q3, 6 Q3, 7 C4 d4, 4 d4, 5 d4, 6 d4, 7 d8 Q2, 4 Q3, 5 Q4, 6 Q4, 7 Q4, 8 计划Plan Q1, 1 Q1, 2 Q1, 3 Q2, 4 Q3, 5 Q4, 6 Q4, 7 Q4, 8 注:dj表示周期j的需求量,di, j表示第i次循环Ci时周期j的需求量,Qi, j表示循环Ci时周期j的生产计划量。Notes: dj is the requirement value at j-th period. di, j is the requirement value at Ci and j-th period. Qi, j is the execution lot-sizing at Ci and j-th period. 表 2 LSP数学模型的仿真参数
Table 2. Simulation parameters of LSP model
参数Parameter 取值Value 总计划周期/月Total planning horizon/month 12 LSP计划周期/月LSP planning period/month 3 需求量Requirement/m3 U(7 500, 8 500) 需求扰动Requirement disturbance/m3 U (100, 150) 制造成本/(元·m-3)
Manufacture cost/(CNY·m-3)U (2 000, 2 400) 库存成本/(元·m-3)
Stock cost/(CNY·m-3)U (100, 150) 缺货损失/(元·m-3)
Shortage cost/(CNY·m-3)U (300, 400) 启动成本/元Setting cost/CNY U (4 000, 4 500) 表 3 市场需求量变化情况
Table 3. Change in the market requirement
m3 循环Cycle 月份Month 1 2 3 4 5 6 7 8 9 10 11 12 1 7 919 8 083 8 062 2 8 694 8 672 7 927 3 8 162 8 060 8 247 4 7 538 7 561 7 526 5 8 452 8 255 8 528 6 8 462 8 758 7 929 7 8 114 8 017 7 787 8 7 555 7 485 7 822 9 8 315 8 412 8 106 10 7 790 7 800 8 323 需求量
Requirement7 919 8 694 8 162 7 538 8 452 8 462 8 114 7 555 8 315 7 790 7 800 8 323 表 4 单位产品生产成本分布 元/m3
Table 4. Cost of the unit product CNY/m3
成本Cost 月份Month 1 2 3 4 5 6 7 8 9 10 11 12 生产成本Production cost 2 052 2 243 2 266 2 038 2 366 2 445 2 337 2 361 2 437 2 120 2 097 2 380 仓储成本Stock cost 148 149 144 142 143 144 144 144 148 146 145 140 缺货损失Shortage cost 389 303 305 348 388 363 380 314 374 386 339 315 启动成本Setting cost 4 053 4 294 4 175 4 240 4 489 4 205 4 477 4 216 4 380 4 450 4 079 4 077 表 5 生产批量时域滚动计划过程
Table 5. Schedule process of rolling horizon lot-sizing planning
m3 循环
Cycle生产批量计划
Lot-sizing planning月份Month 1 2 3 4 5 6 7 8 9 10 11 12 1 Q1 16 002 0 8 062 Q2 11 696 4 310 8 058 2 Q1 611 8 672 7 927 Q2 4 917 8 672 7 927 3 Q1 8 162 16 307 0 Q2 8 162 11 996 4 311 4 Q1 22 625 0 0 Q2 11 986 3 133 7 506 5 Q1 0 1 620 8 528 Q2 4 004 8 255 8 528 6 Q1 1 827 8 758 7 929 Q2 8 462 8 758 7 929 7 Q1 8 114 8 017 7 787 Q2 8 114 8 017 7 787 8 Q1 7 555 7 485 7 822 Q2 7 555 7 485 7 822 9 Q1 8 315 8 412 8 106 Q2 8 315 8 412 8 106 10 Q1 7 790 16 123 0 Q2 7 818 11 999 4 096 执行计划 Q1 16 002 611 8 162 22 625 0 1 827 8 114 7 555 8 315 7 790 16 123 0 Execution plan Q2 11 696 4 917 8 162 11 986 4 004 8 462 8 114 7 555 8 315 7 818 11 999 4 096 注:Q1代表没有生产能力约束时的生产批量计划,Q2代表有生产能力约束时的生产批量计划。Notes: Q1 represents LSP without the constrains of production capacity, and Q2 represents LSP with the constrains of production capacity. 表 6 无生产能力约束最优决策
Table 6. Optimization decision without constrains of production capacity
m3 项目Item 月份Month 1 2 3 4 5 6 7 8 9 10 11 12 计划Plan 16 002 611 8 162 22 625 0 1 827 8 114 7 555 8 315 7 790 16 123 0 库存Stock 8 083 0 0 15 087 6 635 0 0 0 0 0 8 323 0 缺货Shortage 0 0 0 0 0 0 0 0 0 0 0 0 表 7 有生产能力约束最优决策
Table 7. Optimization decision with constrains of production capacity
m3 项目Item 月份Month 1 2 3 4 5 6 7 8 9 10 11 12 计划Plan 11 696 4 917 8 162 11 986 4 004 8 462 8 114 7 555 8 315 7 818 11 999 4 096 库存Stock 3 777 0 0 4 448 0 0 0 0 0 28 4 227 0 缺货Shortage 0 0 0 0 0 0 0 0 0 0 0 0 -
[1] Heady R B, Zhu Z W. An improved implementation of the Wagner-Whitin algorithm[J]. Production and Operations Management, 1994, 3(1):55-63. [2] Baltacioǧlu G, Temiz I, Erol S. Fuzzy Wagner Whitin algorithm and an application of class I supplies [J]. Gazi University Journal of Science, 2011, 24(1): 125-134. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=Open J-Gate000001025327 [3] Fandel G, Trockel J. Investment and lot size planning in a supply chain: coordinating a just-in-time-delivery with a Harris- or a Wagner/Whitin-solution [J]. Journal of Business Economics, 2016, 86(1-2):173-195. doi: 10.1007/s11573-015-0800-6 [4] Fu C C, Huang S Y. The maximum setup time and setup cost of achieving Just-in-Time system[J]. Journal of Business Theory and Practice, 2016, 4(1):75-84. [5] Sahin F, Narayanan A, Robinson E P. Rolling horizon planning in supply chains: review, implications and directions for future research[J]. International Journal of Production Research, 2013, 51(18):5413-5436. doi: 10.1080/00207543.2013.775523 [6] Tiacci L, Saetta S. Demand forecasting, lot sizing and scheduling on a rolling horizon basis[J]. International Journal of Production Economics, 2012, 140(2):803-814. doi: 10.1016/j.ijpe.2012.02.007 [7] Herrera C, Belmokhtar-Berraf S, Thomas A, et al. A reactive decision-making approach to reduce instability in a master production schedule[J]. International Journal of Production Research, 2016, 54(8):2394-2404. doi: 10.1080/00207543.2015.1078516 [8] Xia H, Li X Y, Gao L. A hybrid genetic algorithm with variable neighborhood search for dynamic integrated process planning and scheduling [J]. Computers & Industrial Engineering, 2016, 102:99-112. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=ae252d1a40e3ed8bb445093d1413226b [9] Buer T, Homberger J, Gehring H. A collaborative ant colony metaheuristic for distributed multi-level uncapacitated lot-sizing [J]. International Journal of Production Research, 2013, 51(17):5253-5270. doi: 10.1080/00207543.2013.802822 [10] Karimi-Nasab M, Modarres M, Seyedhoseini S M. A self-adaptive PSO for joint lot sizing and job shop scheduling with compressible process times [J]. Applied Soft Computing, 2015, 27:137-147. doi: 10.1016/j.asoc.2014.10.015 [11] 王雷, 赵秋红, 许绍云.考虑柔性检修计划的圆钢热轧批量调度[J].北京航空航天大学学报, 2016, 42(3):435-443. http://d.old.wanfangdata.com.cn/Periodical/bjhkhtdxxb201603003 Wang L, Zhao Q H, Xu S Y. Hot-rolling batch scheduling in round steel production with flexible maintenance planning [J]. Journal of Beijing University of Aeronautics and Astronautics, 2016, 42(3):435-443. http://d.old.wanfangdata.com.cn/Periodical/bjhkhtdxxb201603003 [12] 闫萍, 焦明海, 赵冰梅.粒子群算法在Lot-sizing问题中的应用[J].控制与决策, 2012, 27(7):1077-1081. http://d.old.wanfangdata.com.cn/Periodical/kzyjc201207022 Yan P, Jiao M H, Zhao B M. Application of particle swarm optimization algorithm in lot-sizing problem [J]. Control and Decision, 2012, 27(7):1077-1081. http://d.old.wanfangdata.com.cn/Periodical/kzyjc201207022 -