有n个零件Ji（ i= 1， 2， n） ，要在m台机床M j（ j= l ， 2， m）上进行加工。根据工艺要求，每个零件的加工过程由若干道工序组成，并按各自的顺序通过这些设备，这就是通常所说的n m排序问题。若在零件加工中*多需要p道工序，每台机床拥有Kj（ j= 1， 2， l ）个与本次加工有关的不同的加工功能，上述问题可简单地表述问题，其中k= max{Kj}（ j= 1， 2， l ）。取作业计划优化目标为全部零件的通过时间*短，即从**个零件开始加工起，到*后一个零件加工结束止这一段时间*短。同时考虑加工过程中的各种约束条件，如工序不可调换，工序不可中断等。
对于待加工的工件来说，所关心的只是按规定的工艺顺序完成全部加工工序，至于具体在哪些机床上完成这些工作并无要求。生产作业计划的*终结果就是要得到每个工件各道工序在各台机床上的加工次序。而加工次序的表示方法并不是**的，由于本文采用遗传算法进行作业计划的优化搜索，再根据多功能机床的特点，采用自然数编码来表示工件的加工次序，把问题的解，即零件的加工次序对应为算法中个体位串的排列状态。具体方法为，在一个nk的生产作业计划问题中，用一个长度为n 的位串来表示零件的加工次序，位串采用自然数字表{1， 2， 3， 4， 5，}进行编码。取个体的位串长度为nm，并使位串中恒有m个1， m个2， m个n；位串中第j次出现的数码a表示第a个零件第j次加工。由于每个零件中各道工序的加工顺序和每道工序的加工时间已知，根据工序机的调度规则，每个位串就代表一种排序方案和这种排序方案所对应的全部零件的通过时间。每个位串的初始状态为随机排列。这样的表示方法可将许多约束条件比较自然地包含在位串的编码中。
2加工资源的描述
在多功能机床的加工系统中，传统的按机床类型区分加工资源的方法已不足以有效地描述机床间共有的和独有的加工功能，必须研究一种新的方法来描述加工机床群的各种加工功能。同时也必须考虑到在遗传算法并行随机搜索的过程中，防止产生使个体的位串长度或整个种群的个体数有较大的增加，造成每次迭代所需的计算量有很大增加，从而可能导致一个无法接受的慢收敛率的各种因素，因为位串的长度或种群的大小将直接影响计算速度和搜索效率。本文用工序机的概念描述加工系统必需的资源，将需要加工的所有工件的每一道不同工序相应地描述为一台工序机，使每一道不同的工序都对应着一台功能专一的工序机。每一台工序机都可能包含着若干台实际机床，工序机之间的实际机床允许相互交叉，也就是说每台工序机都对应着一个允许相互交叉的实际机床的集合。若所有工件在加工过程中*多需要完成P1、P2、P3、P4、P5五道工序，其中有一台机床M k同时具有完成P1和P5的功能，本文就认为此次工件的加工系统一共由五台工序机Pm1、Pm2、Pm3、Pm4、Pm5组成，实际机床Mk则同时属于Pm1和Pm5两台工序机。实际调度过程中，当工件来到工序机前时，工序机根据所属实际机床的完工时刻，自动将工件与所属的*早完工的实际机床匹配。若出现多台功能相同的机床，则仍将其作为不同的实际机床，在考虑工序机时，按其功能归入相应的同类工序机。
工序机的调度过程实际上就是遗传算法迭代过程中个体位串的解码过程。按序从位串中取一代码Ji（即工件号，其出现次数k表示第k道工序） ，依据设定的规则，在与工序机所属的实际机床中选出一台*早完工的机床与Ji（ i= 1， 2， n）的第k道工序匹配。当所有代码均匹配完毕，就表示所有工件均已加工完毕后，即可求得全部工件的通过时间。在这一调度过程中，优化的依据是根据优化过程给出的某一个体位串中代码出现的先后次序，也即是工件的加工次序，实现工序机、实际机床、待加工工件的较为合理的匹配。
3算法实现
若种群内的个体数为N，迭代次数中K、交叉概率为Pc，变异概率为Pm.设置好计算过程中所需的初始数据，随机选取N个个体作为初始种群。从种群中随机取出两个个体作为父辈位串进行交叉，交叉得到两个子一代个体。从两个父辈个体和两个子辈个体中，选取适值大的两个进入新一代种群，这种操作共进行PcN/ 2次。然后，分别从原种群剩余的个体中随机取出PmN/ 2个进行变异操作，变异操作采用同一位串内的两个基因交换的方式来进行，这种方法可保证位串中各种基因的数量不变，变异后的个体也选入新一代种群。剩余的原种群内的全部个体则直接选入新一代种群。在完成这些操作后，根据工序机的调度规则对个体位串解码，计算新种群内各种调度方案的工件通过时间及各位串的适值，然后将新种群内的*大适值和保留的原*大适值比较：若保留的适值小于当前种群内的*大适值，则将当前种群内的*大适值及其它相应的数据取代原保留的数据；否则，保留原有数据。如果遗传操作次数已到预定值，则停止迭代，输出*大适值对应的优化值和位串其它数据；否则进行下一次迭代所示。
4数值实验
以遗传算法为基础建立的面向多功能加工机床的Job Shop作业计划模型，反映了现代制造系统的发展趋势和作业计划问题的新特征，提高了加工系统的动态应变能力。为了验证文中方法的有效性，本文对若干种不同规模的Job Shop作业排序问题进行了计算。
Job Shop作业排序问题的优化结果，为了简化计算过程，假设每台机床有两种功能，机床数与全部零件中的*大工序数相同，除机床的两种功能外，其它原始数据均与J10 M 10标准问题相同。选择不同的初始种群，其优化结果一般均在741以内；随机选取10万种排序方案，其平均值为1114 3.对其它规模问题的计算也得到了类似的结果。计算结果表明，遗传算法结合工序机动态调度的优化方法对求解多功能机床的Job Shop作业计划是较为有效的，采用编码的位串方式来表示零件的加工次序，考虑了各工序的相互关系，可使其优化方案更趋合理。
