多目标混合遗传算法求解流水车间调度问题

基于遗传算法的车间调度系统研究车间调度系统是生产制造中非常重要的一个环节。

为了在有限的时间内完成尽可能多的生产任务，需要合理地安排工人和机器的运转，使得生产效率最大化。

而遗传算法是一种智能化的求解算法，可以很好地应用到车间调度系统的优化问题中。

本文将介绍基于遗传算法的车间调度系统研究。

一、车间调度系统的意义与挑战车间调度系统是生产制造过程中的一个关键环节，它的优化与否对整个生产制造过程的效率和质量都会产生影响。

车间生产是一个复杂的过程，需要对众多生产任务进行安排和分配。

不同的任务需要不同的工序和生产资源，因此需要在有限的时间内合理地安排机器和人工的运转，以最大化生产效率，使得生产线实现高效的转换。

车间调度系统需要解决的主要问题是如何将各个任务分配到机器和工人之间，使得整个生产过程的效率和质量都得到保证。

车间调度系统的优化问题是一个NP问题，它的解决过程非常困难。

首先是搜索空间非常大，需要寻找一个最佳解，而这个最佳解可能隐藏在无数个组合中。

其次，不同的任务有不同的加工时间和优先级，需要在实际的生产环境中高效地进行调度。

因此，对车间调度系统的研究与开发不仅需要面对上述问题，还需要考虑到实际生产过程中的其他特殊因素，如物料准备、工序调整等。

二、遗传算法的基本原理遗传算法是一种生物学启发的求解算法，它模拟了生物进化的过程来求解问题。

它的基本思想是通过模拟生物群体的演化过程，以局部搜索为主并加入概率量化搜索的方式，通过表征问题的染色体来求解问题。

遗传算法的求解过程主要分为以下几个步骤：1. 初始群体的产生：将问题的解空间划分成若干个个体空间，然后从中随机生成一个初始种群。

2. 适应度函数的定义：针对问题，定义适应度函数将每一个个体映射到一个实数值上，表示此个体在问题解空间中的优越程度。

3. 选择运算：利用适应度函数把种群中的优良个体选择出来，作为解的素材，为下一代提供"优良遗传基因"。

求解置换流水车间调度问题的一种混合算法0. 前言置换流水车间调度问题（PFSP是对经典的流水车间调度问题进行简化后得到的一类子问题，最早在石化工业中得到应用，随后扩展到制造系统、生产线组装和信息设备服务上[1] 。

该问题一般可以描述为，n个待加工工件需要在m台机器上进行加工。

问题的目标是求出这n 个工件在每台机器上的加工顺序，从而使得某个调度指标达到最优，最常用的指标为工件的总完工时间（makespar）最短。

PFSP最早由Johnson于1954年进行研究[2]，具有NP难性质[3] 。

求解方法主要有数学规划，启发式方法和基于人工智能的元启发式算法[4] 。

数学规划等适用于小规模问题，启发式方法计算便捷，却又无法保证解的质量。

随着计算智能的发展，基于人工智能的元启发式优化算法成为研究的重点。

遗传算法（GA是研究与应用得最为广泛的智能优化算法，利用遗传算法求解PFSP问题的研究也有很多。

遗传算法具有操作简单、容易实现的优点，且求解时不受约束条件限制。

然而，遗传算法通常存在着过早收敛，容易陷入局部最优的现象。

导致这一现象的原因在于遗传算法的交叉、变异操作具有一定的随机性，在求解PFSP问题的过程中往往会破坏构造块，产生所谓的连锁问题。

为了克服遗传算法的缺陷，研究人员提出了一种不进行遗传操作的分布估计算法[5] (EDA。

EDA是一种运用统计学习的新型优化算法。

相比GA EDA在全局搜索上有较大的优势，而局部搜索能力不足，同样会导致局部最优[6][7] 。

以混合优化为思路，本文将设计一种EDA与GA吉合的混合算法来求解PFSP 问题，混合算法通过EDA的概率模型和GA的交叉变异操作两种方式来生成个体，并引入模糊控制理论[8] 来自适应调节两种算法生成个体的比例。

1. 置换流水车间调度问题PFSP问题通常假设：(1)n台工件在m台机器上加工。

(2)每个工件以相同的顺序在m台机器上加工。

(3)每个工件在每台机器上的加工时间是预先确定的。

基于遗传算法的混合流水线车间调度多目标求解姚丽丽;史海波;刘昶;韩忠华【期刊名称】《计算机应用研究》【年(卷),期】2011(028)009【摘要】为了解决传统的多目标优化算法难以很好实现企业的实际决策需要问题,针对混合流水线车间调度(HFSP)的多目标优化调度问题,提出了一种新的多目标遗传算法.根据企业实际需求,采用分模块两层建模的思想,将多目标分为约束性目标和优化性目标.算法根据目标性质的不同分别进行不同的搜索.最后将新算法应用于HFSP多目标优化问题进行实例验证.结果表明,所提出的算法具有很好的可行性,与其他多目标优化方法相比,该算法具有明显的优越性、实用性和可操作性.%In order to solve the problem that the traditional multi-objective optimization algorithm is difficult to realize the practical decision of the enterprise, brought a novel multi-objective genetic algorithm forward to solve the hybrid flow-shop scheduling problems. According to the demand of the enterprise, based on sub-module using two modeling ideas, objectives were fallen into two categories; constrained objective and optimized objective, and the different objective had the different searching process. Finally, it used the novel algorithm to solve the multi-objective hybrid flow-shop scheduling problem. The result shows that the novel algorithm has the good feasibility, and it also has an obvious advantage, the better practicability and maneuverability, compared with the traditional multi-objective optimization methods.【总页数】5页(P3264-3267,3271)【作者】姚丽丽;史海波;刘昶;韩忠华【作者单位】中国科学院研究生院,北京 100049;中国科学院沈阳自动化研究所工业信息学重点实验室,沈阳 110016;中国科学院沈阳自动化研究所工业信息学重点实验室,沈阳 110016;中国科学院研究生院,北京 100049;中国科学院沈阳自动化研究所工业信息学重点实验室,沈阳 110016;中国科学院研究生院,北京 100049;中国科学院沈阳自动化研究所工业信息学重点实验室,沈阳 110016【正文语种】中文【中图分类】TP315【相关文献】1.基于小生境的自适应多目标遗传算法求解流水车间调度问题 [J], 金焕杰;许峰2.多目标混合遗传算法求解流水车间调度问题 [J], 杨开兵3.基于改进多目标遗传算法求解混合流水车间调度问题 [J], 张志鹏;黄明4.基于小生境的自适应多目标遗传算法求解流水车间调度问题 [J], 金焕杰;许峰5.基于遗传算法的多目标柔性工作车间调度问题求解 [J], 谷峰;陈华平;卢冰原因版权原因，仅展示原文概要，查看原文内容请购买。

基于能耗的柔性作业车间调度多目标优化算法柔性作业车间调度是指在车间内有多个不同的作业，这些作业的加工时间、设备需求等均有所不同，需要根据车间的能力情况和生产计划安排合适的作业顺序和设备分配，以达到生产效率和质量的最大化。

然而，由于车间内作业的差异性，车间调度难度较大。

为了解决这一问题，需要设计一种能够有效处理柔性作业车间调度问题的多目标优化算法。

柔性作业车间调度问题的目标是最大化生产效率和质量，同时减少生产能耗。

因此，多目标优化算法是解决这一问题的有效途径。

本文提出的基于能耗的柔性作业车间调度多目标优化算法，旨在通过综合考虑能耗、生产效率和质量三个方面的问题，来求解柔性作业车间调度问题。

算法的主要步骤如下：1. 建立车间模型将车间表示为一个图论模型，每个车间内的机器设备与作业均表示为图的节点，作业之间的先后顺序和设备之间的联动按边表示。

根据作业的加工时间和设备需求，确定每个节点的处理时间和处理能力。

2. 设计初始种群采用随机策略生成初始种群，每个个体表示待执行的作业序列及对应的设备分配。

动态分配车间设备，采用交叉互换和变异算子对个体进行调整。

3. 目标函数定义以生产效率和质量为优化目标，并引入一项能耗目标作为约束条件。

生产效率和质量可以通过工时和产品合格率来描述，能耗目标可通过机器使用时间及处理数量来计算。

4. 多目标遗传算法求解采用多目标遗传算法，通过交叉、变异和选择等方法对种群进行优化，以得到最优解。

在遗传算法中，将车间模型和目标函数定义作为输入，通过迭代优化得到一组合理的作业调度解决方案，实现车间的柔性作业调度。