Abstract: By considering the scheduling objectives such as makespan,product cost and equipment utilization,a multi-objective flexible Job-Shop scheduling model of batch production was described.To solve batch partition and batch scheduling,a multi-objective batch scheduling algorithm based on differential evolution was proposed by using encoding mode of combining batch splitting chromosome with batch scheduling chromosome.A Pareto-based ranking and crowding distance strategy were introduced to select the next population,and an external archive was employed to hold and update the non-dominated solutions.To balance global exploration and local exploitation,a multi-objective local searching strategy combining dynamic random search with random mutation based on critical path was designed.Through scheduling examples and practical dye vat scheduling,the proposed algorithm could reduce the makespan effectively,and obtain more evenly distributed Pareto non-dominate solutions.

Key words: differential evolution algorithm, multi-objective optimization, local search, flexible Job Shop, batch scheduling

摘要： 考虑生产周期、生产成本、设备利用率等调度目标,给出了多目标柔性作业车间批量调度问题模型。为解决批量划分和批次调度,采用批量染色体和批次染色体相结合的编码方式,提出一种基于差分进化算法的多目标柔性批量调度算法,引入Pareto非支配排序和拥挤距离排序来选择下一代个体,并采用外部存档保存进化过程中的非支配解集。为平衡算法的全局搜索和局部探索能力,设计了基于关键路径的动态随机搜索和随机变异相结合的多目标局部搜索策略。通过调度算例及印染生产调度实例求解表明,所提批量划分方法能有效缩短生产周期,获得更多分布均匀的Pareto非支配解。

关键词: 差分进化算法, 多目标优化, 局部搜索, 柔性作业车间, 批量调度