基于不确定条件下的MPBP鲁棒调度研究

摘要： 本文针对多产品批处理实际生产中加工时间不确定的情况，基于鲁棒调度的思想，提出了一种将加工时间用区间范围表示的鲁棒模型和方法，并使用遗传算法实现该方法。最后，仿真实验的结果表明该鲁棒调度模型和算法的有效性。

Abstract: A robust model and method based on the idea of robust scheduling is proposed for the multi-product batch plant when the processing time is uncertain in the actual production process, which used the interval range to represent the processing time; and the paper uses a genetic algorithm to implement this method. Finally, simulation results show the effectiveness of the robust scheduling model and algorithm.

关键词： 鲁棒优化；遗传算法；不确定性；区间表示

Key words: robust optimization；genetic algorithm；uncertainty；interval expressed

中图分类号：TP18 文献标识码：A 文章编号：1006-4311（2012）24-0200-03

0 引言

制造企业调度的目的是实现制造资源的合理分配以保证车间有序、协调、可控和高效的执行生产任务。然而在实际的企业生产和调度过程中往往会存在各种各样的不确定因素，从而导致在确定性假设下得到的最优计划和调度变为次优，甚至不可行。因此在选择调度策略的过程中充分考虑各种不确定因素,以保证策略的可行性和最优性显得非常重要[1]。

产品的加工时间是生产调度的基础核心数据，但由于设备的新旧程度、工人的技能水平以及工艺的编制水平等方面的差异，导致产品的实际加工时间很难具有一个明确的固定值。因此，在制作生产调度计划时，如何考虑不确定的加工时间成为一项关键的核心问题。鲁建厦、施锦峰[2]等人用概率分布描述不确定的作业时间，提出了一类已知概率分布下的混合车间鲁棒调度方法；丁雷、王爱民[4]等根据生产过程中工艺流程及设备的使用顺序将不确定工时的生产调度分解为4种不同的调度方法；[5]等将不确定的工序时间作为服从正态分布的随机变量处理。在概率分布描述下，不确定的加工时间主要是通过对实际生产操作数据进行统计分析后获得，但实际上采用的概率分布模型与实际的不确定性之间存在一定的差距。

本文将采用区间范围表示不确定的加工时间，提出了基于不确定加工时间的流水车间中多产品批处理过程的鲁棒调度模型。

1 问题描述

多产品批处理（multi-product batch plant, MPBP）调度问题一般可以描述为[8]：N种生产流程和工艺相似度较高的产品通过S道工序进行加工。每道工序包括Zi个完全相同的并行生产设备，每种产品都要按照相同的顺序经过所有的工序，如图1所示。其中，每种产品的每一道工序都可以在加工该工序的任一并行设备上进行，并且加工时间可以不同。

对该MPBP调度问题做如下假设：

①所有产品优先级相同；②同一产品的工序有严格先后顺序，不同产品的工序没有先后约束；③每个设备在每个时刻只能加工某个产品的某道工序；④一个产品不能同时在不同的设备上加工；⑤所有产品在零时刻都可以被加工，且工序的准备时间与顺序无关，包含在加工时间中；⑥每个产品的每道工序一旦开始就不能中断。

2 鲁棒调度理论

鲁棒优化问题的一般描述如下[1]：

Min F（X）=（f1（X′），f2（X′），…，fm（X′））（1）

X′=X+?啄；X′，X∈?赘

鲁棒优化问题的目的是寻找最优解X，使式（1）达到最优。其中，X=（x1，x2，…，xn）是决策向量，X∈Ω，Ω∈Rn，Ω是可行解集，δ=（δ1，δ2，…，δn）为干扰向量，n为决策变量的维数，m为目标维数。当m=1时，称为单目标鲁棒优化问题，当m>1时，成为多目标鲁棒优化问题。

3 鲁棒调度模型

本文调度问题的目标是最小化最大流程时间，具体数学模型如下：

模型的目标函数为：

MinF=Min（max（Ck））

对产品的加工顺序进行约束[7]：

B（j，izi）?叟B（j，（i-1）zi-1）+W（j，（i-1）zi-1）

1?燮j?燮N，1?燮i?燮S

对同一个设备上产品加工的约束[7]：

B（j，izi）?叟B（j-1，izi）+W（j-1，izi）

1?燮j?燮N，1?燮i?燮S

每个产品在每道工序上的开始加工时间必须满足该产品上一道工序已经完成并且该道工序的该设备上没有在加工产品的要求，即为：

B（j，izi）=max（C（j-1，izi），C（j，（i-1）zi-1））

1?燮j?燮N，1?燮i?燮S

每个产品在每道工序上的完工时间为：

C（j，izi）=B（j，izi）+W（j，izi）

1?燮j?燮N，1?燮i?燮S

其中W（j，izi）=S（j，izi）+ε（j，izi），ε（j，izi）?燮?琢（j，izi）

Sj=■

式中，B（j，izi）为产品j在第i道工序的设备Zi上开始加工的时间，C（j，izi）为产品j在第i道工序的设备Zi上的完工时间，W（j，izi）为产品j在第i道工序的设备Zi上实际的加工时间，S（j，izi）为产品j在第i道工序的设备Zi上标准的计划加工时间，不同产品以及不同设备加工时间均不相同，ε（j，izi）为产品j在第i道工序的设备Zi上实际加工时间与计划加工时间的差，设备Zi为第i道工序上的任一设备，Ck为最终的完工时间。