原创文章，禁止转载、抄袭或用于报告、交流等学术或商业用途
全文（其它章节内容）
https://blog.csdn.net/qq_38757869/article/details/106885769
3.2 基于遗传算法的多机作业调度（Job-Shop scheduling）
3.2.1 问题描述
多机调度问题，也称为柔性作业车间调度（Job-shop scheduling problem, JSP），是最为常见的一种离散制造系统调度问题。此问题一般描述为，一组工件J，
每个工件有m道工序需要依次在m台机器上完成加工，
。thompson6*6的JSP问题如下图所示，左边代表工艺约束，右边表示对应的加工时间。
此问题需要解决的是，如何对工件进行排序，以满足生产目标，一般的生产目标为完工时间、交货期延迟等的最小化。
对于此问题，一般作出如下的假设：
? 每道工序的加工时间已知，且不考虑机器的准备时间，以及两个机器之间的运输时间；
? 每台机器最多同时加工一个工件；
? 不考虑机器的宕机；
3.2.2 数学模型
对于JSP问题，优化目标一般为所有工件的最短完工时间、平均流程时间、最小交货期延迟等。
一般需要满足的约束为：
? 每个工序当前仅当被加工一次；
? 工序的开始时间迟于前一道工序的完成时间；
? 机器每次当且仅当能加工一个工件；
? 每道工序的加工过程不可中断；
3.2.3 算法设计
通过对大量的文献回顾可以发现，求解JSP问题的算法可以分为精确求解算法和启发式算法。精确求解算法可以在较长的时间内找到小规模JSP问题的最优解，难以适用于大规模JSP问题的求解。各式各样的启发式算法被用于求解大规模JSP问题，以在较短的时间内找到问题的较优可行解，主要包括：粒子群，遗传算法、蚁群算法以及混合启发式算法等，近几年，超启发式算法也被广泛研究用于求解组合优化问题。
本文以遗传算法为例进行介绍。
首先，对问题的进行遗传编码，即问题的表征。如下图所示，相同的数字代表工件的编号，相同数字出现的次序代表工件的工序。例如：第一个“3”代表工件3的第一道工序，第二个“3”代表工件3的第二道工序，以此类推。
经过上述编码过程后，采用常用的求解组合优化的遗传算法进行求解，包括交叉、变异、选择等过程。需要注意的是，在交叉和变异后需要对子代染色体的合法性进行判断，以获取可行解。
需要自己完成的代码部分则为遗传算法的适应度计算函数，其主要功能是完成对个体的评价，在上述约束的条件下，计算个体的完工时间等目标函数值。一般步骤为：查询当前工件的本道工序的加工时间和加工机器；接着，获取本道工序的上一道工序的完工时间和上一道工序的完工时间；选择max(上一道工序的完工时间, 上一道工序的完工时间)作为本道工序的最早开始时间；迭代更新对应机器的最早开始时间和工序的完工时间；循环执行上述步骤，直到依次计算完所有的基因编码，即可获得对应的目标函数值。
遗传算法的具体的代码参考https://blog.csdn.net/qq_38757869/article/details/107706177
修改初始化编码函数和适应度计算函数即可。
3.2.4 实例验证
采用上述算法对标准的JSP案例集进行求解验证。
案例集
https://blog.csdn.net/qq_38757869/article/details/106746246?spm=1001.2014.3001.5501