求解加工计划和Job-Shop调度集成问题的遗传算法.pdfVIP

计算机科学2004Vo1.31N2.10(增刊) 求解加工计划和Job-Shop调度集成问题的遗传算法 ACoevolutionaryGeneticAlgorithmfortheIntegrationofProcessPlanningandJob-ShopScheduling 李 强 邱洪泽 (山东大学计算机科学与技术学院 济南250061) AbstractSchedulingproblemhasnotonlyastrongappliedbackground,butalsobeenofgreatvalueintheoretical research.Forprocessplanningandjob-shopschedulingarehighlyrelatedwitheachotherinFlexibleManagement System,weputforwardacoevolutinarygeneticalgorithmforthisintegrationproblem.Largenumbersofexperi- mentdemonstratetheeffectivenessandoptimizationperformanceoftheproposedalgorithm. KeywordsCoevolutionarygeneticalgorithm,Processplanning,Job-shopscheduling,Integration 1 引言 传统的Job-Shop调度问题一般假设每一个工 件仅仅有单一的加工计划，这意味着在加工计划上 没有柔性。在柔性制造系统中，提出了各种柔性指 标，打破了上述传统问题的限制，因此加工计划和 Job-shop调度的集成问题，更符合实际应用的情 况。 对于Job-Shop调度问题，很多文献都强调了要 把加工计划和调度结合起来解决，但是由于其复杂 性，有的考虑了特定情况下的集成问题，有的把加工 计划和调度问题分成两个层次分别解决。我们针对 加工计划和Job-Shop调度问题的紧密联系特点，尝 试采用共生遗传算法给出这个集成问题的一种解决 方案。 Job1的网络图 Jo脸的网络翔 2 问题描述 给定要处理的n个工件，确定每一个工件的加 工计划和所有工件的调度方案，使得makespan最 3加工计划的编码、解码和遗传操作 小。加工方式是非抢占式的，每个工件都在。时刻可 3.1编码与解码 用，每台机器同一时刻只能处理一个操作。 加工计划种群Pop[k](k=1,2,--,n)，表示了 采用H。和Moodiell]提出的一种网络图，来表 第k个工件中各个操作的机器选择和路径选择。其 示工件的工艺约束和操作的可选机器及处理时间。 中个体有下面的形式: S,E节点分别表示虚拟的开始操作和结束操作，它 机器序列和选择序列(如果有OR类型的连线) 们不参与编码。其他节点表示了操作。节点内以“可 其中，“机器序列”根据该操作的可用机器随机选择; 用机器:处理时间”的形式表示了该操作的可用机器 “选择序列”中对OR连线进行选择，。表示选择最左 和在该机器上的处理时间。操作之间的连线表示了 边的路径，1表示选择左边第二条路径，以此类推。 操作的先后次序。标记OR的连线，表示后继操作是 3.2 交叉操作 对机器序列部分和选择序列部分，分别采用简 可选的，在标记OR连线中选择且只能选择一条路 单的单点交叉。具体操作是，在机器序列部分随机选 线。 李 强 硕士研究生，研究方向:智能并行软件. .488 · 择一个交叉点，第1个父代交叉点左边的所有位与第 r’的机器m; 2个父代交叉点右边直到机器序列部分结束之间的 Step3:集合A中所有由机器m’进行处理的 所有位，组成子代的机器序列部分;如果有选择序列 操作，构成冲