遗传算法的应用
流水车间调度问题
问题描述:
n 个工件要在 m 台机器上加工,每个工件需要经过 m 道工序,每道工序要求不同的机器,n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的,设为
问题的目标:
确定 n 个工件在每台机器上的最优加工顺序,使最大流程时间达到最小。
假设:
(1) 每个工件在机器上的加工顺序是给定的。
(2) 每台机器同时只能加工一个工件。
(3) 一个工件不能同时在不同的机器上加工。
(4) 工序不能预定。
(5) 工序的准备时间与顺序无关,且包含在加工时间中。
(6) 工件在每台机器上的加工顺序相同,且是确定的。
问题的数学模型:
求解流水车间调度问题的遗传算法设计
FSP的编码方法
对于FSP,最自然的编码方式是用染色体表示工件的顺序。
FSP的适应度函数
求解FSP的遗传算法实例
例6.1 Ho 和 Chang(1991) 给出的5个工件、4台机器问题。
用穷举法求得最优解:4-2-5-1-3,加工时间:213;
最劣解:1-4-2-3-5,加工时间:294;平均解的加工时间:265。
最优解收敛图
平均值收敛图
欢迎大家加我微信交流讨论(请备注csdn上添加)