华北电力大学自动化系 白 康

1.引言

在基本的车间作业调度问题(Job Shop Problem，简称JSP)中，所有工件的工序都只能由指定的某一台机器进行加工。随着加工技术、自动化技术的发展，特别是柔性制造系统的出现，此传统限制已被突破，工件具有多个可选择的加工路线，即路径柔性已经成为生产的实际需求。生产技术的进步推动着调度理论研究的进深，具有柔性路径的柔性车间作业调度(Flexible Job Shop Problem，简称FJSP)研究也开始进入人们的视野并引起重视[1-3]。

目前，遗传算法以其优良的计算性能和显著的应用效果，在求解JSP问题和FJSP问题中获得了很大的成功[4-11]。本文使用遗传算法来求解FJSP问题，提出了多维矩阵的编码方式，以及相应的选择、交叉、变异操作设计，保证遗传操作每一步产生的染色体都是合法的，避免了传统柔性车间作业调度中繁琐的染色体合法化修复工作。最后用一个调度实例验证了算法的正确性和有效性。

2.调度问题描述

n种工件J={Ji|i=1，…，n}在一个由m台不同的加工机器组成的制造系统中进行加工。加工工件Ji需要p(i)道工序，每道工序都有一个可选的机器集合，其加工时间随机器的选择不同而变化。调度目标是确定每台机器上各工件的加工顺序及开工时间，使得系统的最大完成时间Cmax最小，同时给出满足要求的活动调度。假设：

(1)各工件经过准备时间后即可开始加工；

(2)每个工件在某一个时刻只能在一台机器上加工，中途不能打断；

(3)每台机器每次只能加工一个工件；……