基于交替迭代遗传算法的成批车间生产计划与调度的集成优化

熊福力，严洪森

（1. 东南大学 自动化学院，南京 210096；2. 复杂工程系统测量与控制教育部重点实验室，南京 210096）

基于交替迭代遗传算法的成批车间生产计划与调度的集成优化

熊福力1,2，严洪森1,2

（1. 东南大学 自动化学院，南京 210096；2. 复杂工程系统测量与控制教育部重点实验室，南京 210096）

研究了一类零部件混批生产车间需要加工准备的多周期成批生产计划与调度的集成优化问题，建立了生产计划和调度集成优化的非线性混合整数规划模型。并提出了一种交替式混合遗传协调优化算法求解该集成优化问题。其主要思想是给定计划用一混合遗传算法求调度，反过来给定已求调度用另一混合遗传算法求取新计划，如此不断交替使用两个混合遗传算法实现计划与调度的同时优化。仿真结果证明了该方法的可行性和有效性。

批量；作业车间调度；集成优化；交替迭代方法；遗传算法

0 引言

生产计划与调度问题一直是生产运作与管理领域的研究热点，通常生产计划层和调度层是紧密联系的，处在不同层次的生产计划和调度都必须进行有效地沟通。生产计划与调度集成优化问题的求解方法目前主要有以下几类：

1）采用递阶方法分层求解，即将生产计划递阶分解为一系列不同的层次，然后采用一种自顶向下的方法由高层到低层依次作出决策[1]。这种递阶生产计划在过去一段时间内曾被认为是求解大型复杂计划问题的有效途径。但是由于忽略了实际调度操作过程中的具体的能力约束而使得递阶分解的结果在实际生产过程中变得不可行。

2）采用集成模型优化的方法，同时考虑不同层次的约束条件，建立整体优化模型。在进行问题的求解时，有两种主要的求解方法：一种是整体法[2-4]，对不同层次的所有决策同时进行处理。另一种是集成法[5,6]，同样针对整体的优化模型，先对不同层次的生产计划分层求解，然后对不同层次的优化结果进行协调和传递。

上述研究在求解集成优化问题的时候，往往很难较快地得到满意解，模型往往过于简单，没有充分考虑详细的工序约束关系或者考虑的集成优化目标过少，因此难以应用于实际，鉴于此，本文针对有准备时间的多周期成批jobshop车间生产计划与调度的集成优化问题，给出了批量连续生产的工序约束关系，为了解决求解时收敛速度较慢的问题，提出了一种交替迭代遗传算法来求解改模型。

1 成批jobshop车间生产计划和调度的集成优化模型

本文研究的成批job-shop车间生产计划与调度的集成优化问题可描述如下：在车间中有M台设备，需要生产N种零件，每种零件i包含ni道工序，每道工序必须在特定的一台机器上加工，零件的加工工艺路线互不相同，该车间所生产的产品具有种类多、数量大的特点，采用成批生产，零件批量生产过程是连续不间断的。生产过程中更换生产品种时需要不可忽略的准备时间。

综合考虑零部件生产费用、零部件库存费用和欠产惩罚费用、设备上加工任务的提前费用、加班费用以及零部件加工准备工作费用。集成优化目标函数可以表示成如下形式：

生产平衡约束考虑产品库存量、产品需求量和计划生产量之间的平衡关系

同时有非负约束：

由于零件在做好准备工作之后才能开始加工,有

要保证批量为连续生产，应该满足下述工序约束：

1）当pi,j+1＞pi,j时

2) 当pi,j+1＜pij时

同时有工件加工顺序约束：

利用调度约束来细化设备负荷约束有：

2 模型算法及算例

为了有效地求解上述集成优化模型, 本文研究了一种交替式迭代遗传算法（AIHGA）。该算法的工作流程如下：

步骤 1：采用混合遗传算法求解粗计划模型得到初始生产计划。

步骤 2：以初始生产计划作为约束，采用另一混合遗传算法寻找集成优化模型的一个可行调度排序，作为初始调度。

步骤 3：以上一步得到的调度顺序作为约束，采用生产计划层混合遗传算法来优化生产计划。

步骤 4：以上一步得到的生产计划作为约束，采用调度层遗传算法来优化调度顺序。

步骤 5：如果满足算法终止条件，则停止，输出结果；否则，转步骤3。

上述混合交替迭代遗传算法已经用Matlab7.0实现， 为了说明该算法的计算效果，这里给出一种计划调度同时优化遗传算法（MOHGA）做比较，其基本思想是将计划解和调度解编码到同一染色体上，采用选择，交叉和变异等操作同时优化生产计划和调度。表1是不同算例情况下本文提出的AIHGA算法和MOHGA算法的性能比较，所有算例都由软件采用随机的方式自动生成。为方便比较，2种算法中所用遗传算法的交叉率均取为0.9，变异率均取为0.1。以设定的最大运行时间为终止条件。

实验结果中可以看出，在相同运行时间下，从ITERGA获得的目标函数值平均比CONTGA 的要小15.4%，同时也说明本文提出的集成优化方法能够较快地收敛到一个满意解。

表1 ITERGA和CONTGA计算性能的比较

3 结论

本文研究了一类零件加工有准备时间且为批量生产的job shop车间多周期生产计划和调度的集成优化问题，建立了该类问题的非线性混合整数规划模型，并给出了一个交替式迭代集成优化方法。由于该模型的复杂性并考虑到遗传算法在求解大规模复杂组合优化问题时表现出的优越性，文中提出了一种混合交替迭代遗传算法(ITERGA)用以求解该类问题。这相当于在在生产计划和调度求解两个过程之间加一个循环迭代过程，将递阶算法构成一个闭环系统，提高了求解速度，文中给出的大量算例的数值实验中，ITERGA方法所获得的平均目标值比CONTGA的要小15.4%，具有较快的求解速度和精度。

[1] Bowers M R, Jarvis J P.A hierarchical production planning and scheduling model[J].Decision Sciences, 1992, 23(1)： 144-159.

[2] Karimi B, Fatemi G.The capacitated lot sizing problem： a review of model algorithms[J].The International Journal of Management Science, 2003, 31： 365-378.

[3] 张晓东, 严洪森. 一类Job-Shop 车间生产计划与调度的集成优化[J] . 控制与决策, 2003, 18(5) ： 581-584.

[4] 何霆, 刘文煌, 梁力平. MES的计划、调度集成问题研究[J]. 制造业自动化, 2003, 25(3)： 24-26.

[5] Lasserre J B. An integrated model for job-shop planning and scheduling [J]. Management Science, 1992, 38(8)： 1201-1211.

[6] 尚文利, 范玉顺. 成批生产计划调度的集成建模与优化[J]. 计算机集成制造系统, 2005, 11(12)： 1163-1167.

Alternant iterative method based on genetic algorithm for integrated batch production planning and scheduling of a kind of jobshop

XIONG Fu-li1,2, YAN Hong-sen1,2

TB491

A

1009-0134(2011)5(下)-0095-02

10.3969/j.issn.1009-0134.2011.5(下).28

2011-01-07

国家863计划现代制造集成技术专题资助项目(2007AA04Z112)；国家自然科学基金资助项目(60934008, 50875046)

熊福力（1974－），男，黑龙江肇东人，博士生，主要从事制造系统的生产计划与调度建模和智能优化算法等研究工作。