1.基本概念
车间调度是指根据产品制造的合理需求分配加工车间顺序,从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上加工。问题需要满足的条件包括每个零件的各道工序使用每台机器不多于1次,每个零件都按照一定的顺序进行加工。
车间调度问题实例:
现共有6个工件,在10台机器上加工,每个工件都要经过6道加工工序,每个工序可选择机器序号如表一所列。每道工序的加工时间如表二所列。请合理分配工件在机器上的加工顺序(即指明每个工件的每个工序在什么时间在哪台机器上加工),使得总加工耗时最短(成本最小)。
表一:工序可选机器表
工序1 工序2 工序3 工序4 工序5 工序6
工件1 5 6 4 [2,9] [3,7] 5
工件2 4 [2,9] 8 [6,7] 5 [1,10]
工件3 3 [6,8] 7 [2,1] [4,10] 5
工件4 5 2 [4,7] 10 [2,5] [3,6]
工件5 [4,5] 5 [9,10] 6 2 [3,8]
工件6 [2,6] 4 [6,9] 7 8 [3,9]
表二:工件加工时间表
工序1 工序2 工序3 工序4 工序5 工序6
工件1 3 10 9 [5,4] [3,3] 10
工件2 6 [8,6] 4 [2,6] 3 [3,3]
工件3 4 [5,7] 7 [5,5] [9,11] 1
工件4 7 3 [4,6] 3 [1,7] [3,6]
工件5 [6,4] 10 [7,9] 8 5 [4,7]
工件6 [3,7] 10 [8,7] 9 4 [9,4]
求解算法:狼群算法
狼群算法简介:
1、狼群算法中的狼种类分为以下几种:头狼、探狼、猛狼。
2、猎物分配规则:论功行赏,先强后弱。
3、狼群算法的主体构成:探狼游走、头狼召唤、猛狼围攻3种智能行为,“胜者为王”的头狼角逐规则和“优胜劣汰”的狼群更新规则。
Step1:在解空间中随机初始化狼群的空间坐标,依据目标函数值的大小角逐出人工头狼。
Step2:探狼开始随机游走搜索猎物,若发现某个位置的目标函数值大于头狼的目标函数值,将更新头狼位置,同时头狼发出召唤行为;若未发现,探狼继续游走直到达到最大游走次数,头狼在原本的位置发出召唤行为。
Step3:听到头狼召唤的猛狼以较大的步长快速向头狼奔袭,若奔袭途中猛狼的目标函数值大于头狼的目标函数值,则将对头狼位置进行更新;否则,猛狼将继续奔袭直到进入围攻范围。
Step4:靠近头狼的猛狼将联合探狼对猎物(把头狼位置视为猎物)进行围捕,围捕过程中若其他人工狼的目标函数值大于头狼的目标函数值,则对头狼位置进行更新,直到捕获猎物。
Step5:淘汰狼群中目标函数值较小的人工狼,并在解空间中随机生成新的人工狼,实现狼群的更新。
Step6:最后判断头狼的目标函数值是否达到精度要求或算法是否达到最大迭代次数。
4、人工狼群算法的若干规则:
(1)头狼产生规则
初始解空间中,具有最优目标函数值的人工狼即为头狼;在迭代过程中,将每次迭代后最优狼的目标函数值与前一代中头狼的值进行比较,若更优则对头狼位置进行更新,若此时存在多匹的情况,则随机选一匹成为头狼。头狼不执行3种智能行为,直接进入迭代,直到被其他更强的人工狼代替。
(2)游走行为
(3)召唤行为
(4)围攻行为
5、人工狼群算法的具体步骤:
编程求解结果:
免责声明:本文系网络转载或改编,未找到原创作者,版权归原作者所有。如涉及版权,请联系删