一种基于引力搜索算法的阻塞流水车间调度优化方法

	一种基于引力搜索算法的阻塞流水车间调度优化方法
	赵付青; 薛飞龙; 唐建新; 张建林
	2019-11-19
专利权人	兰州理工大学
公开日期	2019-11-19
授权国家	中国
专利类型	发明申请
摘要	一种基于引力搜索算法的阻塞流水车间调度优化方法，以引力搜索算法为基础，优化以最小化总流经时间为目标的阻塞流水车间调度问题。采用基于工件序列的整数编码方式，这种方法简单而高效；在种群的初始化阶段，使用了一种新型的初始化方法产生优质的初始化种群；在算法的每一次迭代中，对原始算法的更新的方式进行了改进；在种群的加速度更新阶段，使用了减法操作()、乘法操作()以及求和操作(∑)；在种群的速度更新阶段，使用了⊙操作；在种群的位置更新阶段，使用了操作；最后，采用了一个简单的模拟退火规则来确定新粒子是否更新到下一代。实验结果表明了DGSA在解决阻塞流水车间调度问题时的高效性和有效性。
申请日期	2019-08-23
优先权日	2019-08-23
专利状态	实质审查
申请号	CN201910782776.6
公开（公告）号	CN110472799A
IPC 分类号	G06Q10/04 ; G06Q10/06 ; G06Q50/04 ; G06N3/00
专利代理人	董斌
代理机构	兰州振华专利代理有限责任公司
CPC分类号	G06Q10/04 ; G06Q10/0631 ; G06Q50/04 ; G06N3/006 ; Y02P90/30
权利要求	1.一种基于引力搜索算法的阻塞流水车间调度优化方法，其特征在于，其步骤为：步骤1：使用VPF+NEH方法初始化种群；步骤2：使用新的更新方式更新种群的加速度、速度和位置；步骤3：使用简单的模拟退火规则选择新种群。 2.根据权利要求1所述的基于引力搜索算法的阻塞流水车间调度优化方法，其特征在于，在步骤1中，此优化方法使用VPF+NEH方法来产生num个初始解，num是算法设定的初始解数量；经过VPF+NEH方法计算以后，就可以得到一个多样性和质量都很优良的初始化种群。 3.根据权利要求1所述的基于引力搜索算法的阻塞流水车间调度优化方法，其特征在于，在步骤2中，标准的引力搜索算法的加速度、速度和位置的更新方式都是连续的，在此优化方法中，将对连续的更新方式进行离散化处理，使其符合调度问题的特性， (1)对于加速度，加速度的计算公式为：使用上述公式计算各个粒子的加速度，其中，表示两个序列之间的减法操作，具体按以下过程实施：xi(t)和xj(t)相同位置上的元素相同时则置为0，不同则置为xj(t)，HRi,j(t)表示两个序列之间的汉明距离，表示序列中的选择操作，具体按以下过程实施：随机选择k个非零的元素保持不变，其他的元素都置为0，k的计算公式为： ra是控制参数，n是工件数量，rand是一个随机值，G(t)是引力系数，∑表示将不同的序列组合成粒子的加速度序列； (2)对于速度，速度的计算公式为： vi(t+1)＝vi(t)⊙ai(t) 使用上述公式计算序列的速度，vi(t)是粒子当前的速度序列，ai(t)是粒子对应的加速度序列，⊙表示粒子序列速度的更新方式，具体按以下过程实施：记vc是一个大于0小于1的常数，当rand
引用专利	CN102222268A;CN108053119A
被引用专利数量	2
简单法律状态	审中
文献类型	专利
条目标识符	https://ir.lut.edu.cn/handle/2XXMBERH/108132
专题	兰州理工大学
推荐引用方式 GB/T 7714	赵付青,薛飞龙,唐建新,等. 一种基于引力搜索算法的阻塞流水车间调度优化方法[P]. 2019-11-19.