求解具有混合约束流水车间调度问题的迭代贪婪算法  

Iterated greedy algorithm for mixed constraints flow shop scheduling problem

作　　者：张其亮[1] 陈永生[2] 

机构地区：[1]江苏科技大学电气与信息工程学院,江苏张家港215600 [2]同济大学电子与信息工程学院,上海200331

出　　处：《计算机应用研究》2016年第2期352-355,共4页Application Research of Computers

基　　金：国家"十一五"科技支撑计划资助项目(115-04-YK-048)

摘　　要：基于传统的流水车间调度问题,提出一种有限等待约束、阻塞约束以及无等待约束共存的混合约束流水车间调度问题。以问题的最小化最大完工时间为目标,提出一种利用迭代贪婪算法进行求解的方法。该方法利用改进的NEH算法计算初始解,通过迭代贪婪算法进行优化,并设计多点交叉策略和插入邻域搜索策略提高解的质量。通过经典实例测试,验证了所提算法的有效性。Based on the classical FSS problem, this paper proposed a new mixed constraints FSS （MFSS） problem with no- wait constraint, blocking constraints and limited buffers constraint. To minimize makespan of MFSS, this paper designed an it- erated greedy （IG） algorithm. The algorithm used the improved NEH algorithm to get the initial solution, and then applied IG algorithm to optimize globally. And it devised the multipoint crossing operator and neighborhood insert search strategy to im- prove the quality of solution. An classical experiment validates the effectiveness of the proposed algorithm.

关 键 词：混合约束 流水车间调度 迭代贪婪算法 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置] TP301.6[自动化与计算机技术—控制科学与工程]