【优化调度】遗传算法求解工件的并行调度组合优化问题【含Matlab源码 2234期】

⛄ 一、 遗传算法简介

1 问题描述
假定一个加工系统有m台机器和n件工件，每个工件包含一道或多道工序,工件的加工顺序是确定的,但每个工件可能有几条可行的加工路线,即每道工序可在多台不同的机床上加工,工序的加工时间和加工费用随机床的性能不同而变化。作业调度的任务是确定机器上工序的加工顺序,使得某个性能指标(如最大流程时间)取得最优值。下面是针对该调度模型的假设:

(1)每台机床一次只能加工一个工件。

(2)工序一旦进行不能中断。

(3)假定工件之间具备相同的优先级。

(4)不同工件的工序之间没有先后约束。

(5)工序在某台机床的加工时间是确定的。

(6)在零时刻,所有的工件都可被加工。

2 算法描述
遗传算法（Genetic Algorithms）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密歇根大学的Holland教授为研究自然与人工系统的自适应行为而提出的一种算法。近年来，遗传算法从理论到实际都已取得了许多重要成果。基于遗传算法求解NP问题的研究也相当活跃，对于求解NP问题，遗传算法已显示出了巨大的优势。

传统遗传算法从一组随机产生的初始解(种群)开始搜索。种群中的每个个体是问题的一个解(染色体)，这些染色体在后续迭代中不断进化,称为遗传。在每一代中用“适值”来测量染色体的好坏。生成的下一代染色体,称为子代。后代是由前一代染色体通过交叉或者变异操作形成的，在子代的形成过程中,根据适值的大小选择部分后代,淘汰部分后代,始终保持种群的大小是常数。适值高的染色体被选中的概率较高,体现了“适者生存”的进