求解带缓冲区和机器可用性约束的非置换流水车间调度

来源期刊：东北大学学报(自然科学版)2014年第9期

论文作者：郑永前 李燕

文章页码：1329 - 2679

关键词：缓冲区;非置换;机器可用性;析取图;量子蚁群;

摘    要：为得到非置换流水车间更好的调度方案,考虑到缓冲区、机器可用性约束和序列相关换模时间,以最小化最大完工时间为目标,建立数学模型和析取图模型,构造了一种面向NPFS的列表启发式算法.算法通过允许列表和候选列表记录启发式过程信息,采用量子蚁群和SPT启发式规则搜索并选择析取边的可行移动方案,得到一个没有冲突的有向非循环图.通过正交试验法验证了算法关键参数,实例验证了算法求解和CPLEX的精确解相同.同时采用8组Demirkol测试问题,与MHD-ACS和ACO算法比较评估,验证了算法的有效性和鲁棒性.