遗传算法的车间调度算法求解PPT.ppt

遗传算法在 Job-Shop 调度问题中的应用 遗传算法是解决 Job-Shop 调度问题的一种有效方法，它可以找到近似最优解。Job-Shop 调度问题是一个典型的 NP 难问题，研究它的方法始终以启发式算法为主导，但这些方法存在着难以克服的弱点，如计算规模不可能较大，寻优结果不具备全局特性等等。近年来，学者们提出了基于神经网络的车间作业调度系统，但此种方法在 JSS 规模较大时，却存在着计算速度慢与结构参数难以确定的弱点。因此，遗传算法的出现给这类问题带来了新的希望，并取得了较为满意的成果。 Job-Shop 调度问题的描述是指在 n 台机器上加工 m 个工件的顺序问题，每个工件都需要经过若干台机器的加工，并且每台机器上加工的顺序都是固定的。问题的目标是找到一种最优的加工顺序，使得总的完成时间最小。 遗传算法在 Job-Shop 调度问题中的应用有很多，例如基于遗传算法的 Job-Shop 调度系统、基于遗传算法的并行 Job-Shop 系统、基于遗传算法的 Job-Shop 专家系统等等。这些方法都取得了较为满意的成果，但是它们的实现都需要进行大量的计算和优化。 遗传算法在 Job-Shop 调度问题中的优点是可以找到近似最优解，且计算速度较快，可以解决大规模的 Job-Shop 调度问题。但是，它也存在一些缺点，如需要进行大量的参数调整，很难找到最优的参数设置。 Job-Shop 调度问题的约束条件包括：1. 一个工件不能同时在不同的机器上加工；2. 对整个工件来说，在加工过程中采取平行移动方式；3. 不允许中断，当一个工件一旦开始加工，必须一直进行到完工，不允许中途停下来，插入其他工件；4. 每道工序只在一台机器上完成，每台机器只完成一道工序；5. 工件数、机器数、加工时间已知，且加工时间与加工顺序无关；6. 允许工件在工序之间等待，允许机器在工件未到达是闲置；7. 工件加工技术上的约束事先给定； 8. 每台机器同时只能加工一个工件。 遗传算法在 Job-Shop 调度问题中的应用可以找到近似最优解，且计算速度较快，但需要进行大量的参数调整和优化。