【摘要】目前柔性车间作业调度问题已成为研究热点，本文采用遗传算法求解该问题。针对柔性车间作业调度问题的特点设计了染色体编码方法，即将基于工序的编码和基于机器的编码方式结合。同时在遗传操作方面设计了相应的交叉和变异算子。这些改进方法可以保证遗传操作每一步产生的染色体在工艺约束和选择机器方面都是合法的，避免了传统柔性车间作业调度中繁琐的染色体合法化修复工作。为了得到活动调度，在进行适应度计算时对染色体中的基因序列进行调整。仿真结果表明设计的遗传算法求解柔性车间作业调度是有效的。
　　【关键词】柔性车间作业调度；活性调度；遗传算法
　　
　　 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)每台机器每次只能加工一个工件；
　　 (4)不考虑工件之间的加工优先权。
　　 3.遗传算子设计
　　 3.1 适应度函数f(i)
　　 染色体i的适应度值由以下公式给出，其中C是一个大的正整数。
　　 f(i)=C-Cmax
　　 3.2 编码
　　 op=å(i=1，…，n)p(i)：所有工件工序数量总和。
　　 定义染色体为矩阵ch[3][op]，该染色体蕴涵工序和机器选择的双重信息。
　　 第一行是基于工序的编码：数字i代表工件Ji。从左到右扫描，数字i的第j次出现代表工件Ji的第j道工序，记为Oij。
　　 第二行是基于机器的编码：[k11，k12，…，k1p(1)，…，kn1，kn2，…，knp(n)]，其中kij表示工序Oij所选择的机器号码。
　　 第三行提供了加工时间的信息：[t11，t12，…，t1p(1)，…，tn1，tn2，…，tnp(n)]，其中tij代表工序Oij在机器kij上进行加工所需要的加工时间。
　　 3.3 交叉与变异
　　 为了避免交叉操作之后产生非法个体(某道工序选择了不可用的机器)，规定仅仅对染色体的第二行、第三行数据，以概率pc进行两点交叉操作。
　　 设计两种变异算子。
　　 对染色体第一行数据，以概率pmop进行互逆变异操作，其目的在于生成新的调度。
　　 对染色体第二行数据，以概率pmch改变某基因的值，注意要保证选择的机器合法。之后改变染色体第三行相应位置上的值，赋予其新机器上的加工时间。
　　 以上的编码方式结合交叉、变异操作可使得生成的染色体在工序和机器选择方面都是合法染色体。
　　 3.4 活动调度的调整
　　 对染色体解码时，从左到右依次扫描第一行基于工序的编码串，确定工序信息Oij，之后在第二行的编码串中找到该工序选择的机器号码，扫描完毕即得到了该染色体对应的调度形式。按照这种解码方式一般只能得到半活动调度，而不是活动调度[12]。因此，将一种插入式算法嵌入到适应度计算过程中，在有必要时调整染色体的基因序列，使其解码后生成活动调度。
　　 这种插入算法针对所有工件的非首道工序进行处理，将其插入到对应机器上最佳可行的加工时刻安排加工，以这种方式保证所有工序都安排在最佳可行的地方，使得机器利用率最大化。
　　 stij：当前工序Oij的开工时间；
　　 opij：当前工序Oij的加工时间，j>1；
　　 fti(j-1)：同一工件前道工序Oi(j-1)的完工时间，j>1；
　　 ftm：工序Oij所选用机器目前的可用时间；
　　 stm：同一机器上前道工序的开工时间；
　　 在基于工序的编码方式下，各个工件的加工已经按照其工艺顺序进行。给定染色体，设系统中所有机器的可用时间为0，所有待加工工件的初始可用时间为0。从左到右扫描染色体第一行数据，确定工序Oij的加工开始时间：
　　 for(k=1 to op)
　　 {对每一道工序ch[0][k-1]，判断其工序信息Oij；
　　 if(j=1)stij=ftm；
　　 else{
　　 if(fti(j-1)³ftm)stij=fti(j-1)；
　　 else{
　　 if((fti(j-1)+opij)£stm){stij=fti(j-1)；调用染色体调整过程；}
　　 else stij=ftm；}}
　　 }
　　 调整过程：代表当前工序Oi的数字为a，代表同一台机器上前道工序的数字为b。在染色体第一行编码串中，将a提到b之前。
　　 图1的甘特图中，字符串“i–j”表示工序Oij。图1(a)显示：工序O11的完工时间ft11=2；工序O21在st2=5时刻开始加工，加工完毕后有ft2=8；工序O12的加工时间op12=2。因满足条件(ft11+op12)　　 3.5 选择
　　 采用适应度比例方法，并执行保优策略。即当进行交叉、变异等操作时，生成的子代种群和父代种群合并成一个新的种群，对新种群应用适应度比例方法，即轮盘赌方法进行选择，且保存当代最优个体，即适应度最大且所有机器的总完工时间最小的染色体。
　　 4.实例仿真
　　 以表1所示的调度问题为例，表格中的数字代表各工序在相应机器上的加工时间。
　　 遗传算法的参数设置为：交叉概率Pc=0.85，变异概率Pmop=0.012，Pmch=0.2，种群规模popsize=40，运行次数maxrun=10，每次运行最大进化代数maxgen=100。最终得到的调度结果makespan=17。
　　 观察表1，令每道工序都选择最小加工时间的机器，可得到工件J1、J2、J3和J4的完工时间分别为5、9、17和12，所以对于该问题，若不限制工件访问同一台机器的次数，且系统缓冲区无限，makespan=17已经是最优的调度结果。
　　 在makespan=17的调度中，得到的最小的总完工时间为63。图2中，字符串“ij”表示工序Oij的开始加工时间是a，完工时间是b。调度的甘特图见图3，字符串“i-j”表示工序Oij。因任何工序都不可能提前操作而同时保证其他工序不延迟，因此该调度是活动调度。
　　 5.结论
　　 本文使用遗传算法来求解柔性车间作业活动调度问题。首先将基于工序的编码和基于机器的编码方式结合，同时对交叉操作和变异操作的对象作了规定，这些改进方法可以保证遗传操作每一步产生的染色体都是合法的，避免了传统柔性车间作业调度中繁琐的染色体合法化修复工作。为了得到活动调度的形式，在适应度计算的过程中对染色体的基因序列进行调整。用4工件6机器的柔性车间作业调度问题为例进行仿真，得到的调度结果为最优；在所有最小makespan值的调度中，进一步给出了机器总完工时间最小的调度。仿真结果表明，本文设计的遗传算法在求解柔性车间作业调度问题时是有效的。
　　
　　参考文献
　　[1]Zribi N,Kamel AE,Borne P.Scheduling in a flexible job shop under machine availability constraints[J].APII-JESA Journal Europeen des Systemes Automatises,2007,41(6):651-671.
　　[2]Guohui Zhang,Liang Gao,Yang Shi.An effective genetic algorithm for the flexible job-shop scheduling problem[J].Expert Systems with Applications,2011,4(38):3563-3573.
　　[3]白俊杰,龚毅光,王宁生,唐敦兵.批量生产柔性作业车间作业优化调度研究[J].机械科学与技术,2010,3(29):293-298.
　　[4]Kacem I.Genetic algorithm for the flexible job-shop scheduling problem[C],IEEE International Conference on Systems,Man and Cybernetics,OCT 05-08,WASHINGTON D.C.2003,1-5:3464-3469.
　　[5]Kun Y,Zhu JY.Improved genetic algorithm for the flexible job-shop scheduling with multi-object[J].China Mechanical Engineering,2007,18(2):156-160.
　　[6]光熠,刘心报,程浩.求解车间作业调度问题的一种改进遗传算法[J].计算机技术与发展,2007,11(17):171-174,178.
　　[7]陈亮,王世进,周炳海.柔性作业车间调度问题的集成启发式算法[J].计算机工程,2008,34(1):256-258.
　　[8]席卫东,乔兵,朱剑英.基于改进遗传算法的柔性作业车间调度[J].哈尔滨工业大学学报,2007,39(7):1151-1153.
　　[9]杨红红,吴智铭.混合遗传算法在柔性系统动态调度中的应用研究[J].信息与控制,2001,30(5):392-397.
　　[10]方红雨,崔逊学.基于遗传算法的调度问题研究[J].电脑与信息技术,2001(2):1-5.
　　[11]Ferrolho A,Crisostomo M.A hybrid and flexible genetic algorithm for the job-shop scheduling problem[C].IEEE International Symposium on Computational Intelligence in Robotics and Automation.IEEE Piscataway.NJ.USA Jacksonville.FI.USA,2007:421-426.
　　[12]王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003.
　　
　　作者简介：白康（1982—），女，河北保定人，硕士研究生，华北电力大学自动化系讲师，研究方向：智能调度与优化。