一、课题研究的目的、背景及意义

进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。

二、国内外研究现状

K.A.De Jong完成了他的博士论文《一类遗传自适应系统的行为分析》（An Analysis of the Behavior of a Class of Genetic Adaptive System）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。

目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。

三、遗传算法基本流程

标准遗传算法的主要步骤可描述如下：

步骤1：随机产生初始种群，并评价各个体的适配值（fitness value）.

步骤2：判断算法收敛准则是否满足。若满足则输出搜索结果；否则执行一下步骤。

步骤3：根据适配值大小以一定的方式执行复制操作来从种群中选取两个个体。

步骤4：若交叉概率Pc>ξ，则对选中个体执行交叉操作来产生两个临时个体；否则将选中父代个体作为临时个体。

步骤5：按变异概率Pm对临时个体执行变异操作产生两个新个体。

步骤6：返回步骤2。

标准遗传算法的流程图描述。如下图所示：

图3.1 标准遗传算法流程框图

四、绿色柔性作业车间调度问题仿真

4.1绿色柔性作业车间调度问题的描述与数学模型

绿色柔性作业车间调度问题一般可以描述为n个工件要在m台机器上加工，每个工件需要经过m道工序，每道工序要求不同的机器n，n个工件在m台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为tij(i＝l，…，n；j＝l，…，m)。问题的目标是确定n个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。

对该问题常常作如下假设：

(1).每个工件在机器上的加工顺序是给定的；

(2).每台机器同时只能加工一个工件；

(3).一个工件不能同时在不同的机器上加工；

(4).工序不能预定；

(5).工序的准备时间与顺序无关，且包含在加工时间中；

(6).工件在每台机器上的加工顺序相同，且是确定的。

令c(ji，k)表示工件ji在机器k上的加工完工时间，{j1，j2，…jn}表示工件的调度，那么对于无限中间存储方式，n个工件、m台机器的绿色柔性作业车间调度问题的完工时间可表示为

最大流程时间为：

调度目标就是确定j1，j2，…，jn使得Cmax最小。

4.2绿色柔性作业车间调度问题仿真

首先说明Johnson法则：如果作业i和j满足，则作业i和j满足Johnson不等式。如果不满足，则交换作业i和j的加工顺序，作业i和j满足Johnson不等式。由此可知，任意两个满足Johnson法则的调度具有相同的加工时间。现在，流水线问题转化为求满足Johnson法则的调度问题。

可以证明，应用Johnson法则的算法是本问题的一个最优算法。

算法的大致步骤如下：，分别为第个作业在机器、上的作业时间。先取，.，然后将中作业按照的非递减顺序排序，将中作业按照的非递增顺序排序。之后将中作业接着构成满足中作业Johnson法则的调度算法。

具体实现时，可以通过完善比较函数，而将n个作业通过一次排序即可得到满足的Johnson法则的调度顺序。

图4-1仿真程序代码

图4-2仿真程序代码

图4-3仿真程序代码

图4-4仿真程序代码

图4-5仿真程序

4.3基于遗传算法的绿色柔性作业车间调度问题仿真

图4-6

4.4结果分析

由以上的演示可以看出，优秀的父代经过交叉变异后产生会产生更加优秀的后代，也可能产生不良的后代，因此，将所有父代和新产生的染色体组合成一个大于父代群体大小的中间群体，并依据适应度进行重新排列，并选择靠前的作为子代，这样就保证了子代群体是优于父代群体的，并随着交叉变异的代数越多而子代群体越趋向于优化。

五、总结

本文以绿色柔性作业车间的调度作为研究对象，以遗传算法为基础，分别对一般绿色柔性作业车间和具有可跨工位操作的绿色柔性作业车间两种生产车间计划调度进行了系统的研究。在理论研究的基础上完成了基于遗传算法的调度的算法设计，展示了算法的实现过程并对调度结果进行分析。本论文的主要工作总结如下：

1.阐述了车间调度问题国内外研究现状，探讨了车间调度的问题以及可能的解决途径。

2.对车间调度问题进行了简单的描述的，对车间调度问题的复杂性进行了探讨。将静态和动态车间调度，作业车间调度和绿色柔性作业车间调度进行了区别。最后对车间调度方法进行了总结。接着简单介绍了遗传算法的形成与发展，基本思路和操作步骤。详细介绍了遗传算法中常用的一些编码方式，交叉变异方法，查询到了常用参数范围和对算法的终止条件进行了简单理解。

3.对一般绿色柔性作业车间问题进行了描述和数学建模，针对绿色柔性作业车间调度问题，对遗传算法进行了设计，选择出最优的调度方案。

尽管调度问题的研究己经取得了很多的成果，但是这些成果与实际的调度问题之间都存在一定的差距，尚不能很好地解决复杂的实际生产调度问题。要更好地解决实际的复杂调度问题，需研究更加有效的调度优化方法以及研究解决实际调度问题的合理有效的调度策略。在实际的调度中，计划与调度往往是分层进行的，但这可能造成计划在实际调度中的不可行问题，如何将计划与调度结合考虑，以求总体的优化也需要作进一步的研究。

参考文献

[1] 刘玉婷. 高维多目标绿色柔性作业车间调度问题研究.

[2] 吕思焱, 余鹏. 绿色柔性作业车间调度问题研究综述[J]. 物流工程与管理, 2022(005):044.

[3] 崔鹏举. 双资源多目标柔性作业车间调度问题研究[D]. 西安电子科技大学.

[4] 卫少鹏, 王婷, 周彤. 考虑调整时间的绿色柔性作业车间调度研究[J]. 机电工程, 2021.

[5] 杨立熙, 王秀萍. 考虑低碳的柔性作业车间调度问题研究[J]. 组合机床与自动化加工技术, 2018(6):5.

[6] 包哲人, 徐华. 面向能耗机制的多目标柔性作业车间调度[J]. 计算机应用研究, 2017, 34(12):6.

[7] 吕文军, 雷琦. 面向绿色制造的多目标柔性作业车间调度方法研究[J].  2015.

[8] 费凡. 面向节能优化的多目标柔性作业车间生产调度方法研究[D]. 合肥工业大学.

[9] 张国辉, 党世杰, Zhang,等. 考虑机器速度的低碳柔性作业车间调度问题研究[J]. 计算机应用研究, 2017, 34(4):4.

[10] 吴秀丽, 孙树栋, 余建军,等. 多目标柔性作业车间调度优化研究[J]. 计算机集成制造系统, 2006.

[11] 李盛, 宋豫川, 雷琦,等. 基于BOM的柔性作业车间调度方法研究[J]. 中国科技论文在线精品论文, 2018(008):011.

[12] 朱文凡. 基于遗传算法的多柔性作业车间调度问题研究[D]. 合肥工业大学, 2015.

[13] 王建华, 潘宇杰, 孙瑞. 自适应Jaya算法求解多目标柔性车间绿色调度问题[J].  2021.

[14] 何院生. 考虑能耗优化的柔性作业车间动态调度方法研究[D]. 哈尔滨工业大学.

[15] 张国辉, 卫世文, 张海军,等. 考虑时间与能耗约束的柔性作业车间调度优化[J]. 计算机应用研究, 2022, 39(12):5.

[16] 李香怡何星月王磊唐红涛. 考虑工件运输时间的绿色柔性作业车间调度研究[J]. 数字制造科学, 2020, 000(002):P.102-106.

[17] 盖海江. 考虑多时间因素的柔性作业车间绿色调度与多行布局集成优化[D]. 安徽工业大学, 2019.

[18] 刘伟. 双柔性多目标作业车间调度方法研究及原型系统开发[D]. 湖南大学.