求解零等待流水线调度问题的混合群搜索算法  

A Hybrid Group Search Algorithm for the No-wait Flow-shop Scheduling Problem

作　　者：李永林[1] 叶春明[1] 刘勤明[2] 

机构地区：[1]上海理工大学管理学院,上海200093 [2]上海交通大学安泰经济与管理学院,上海200052

出　　处：《工业工程与管理》2013年第5期24-29,共6页Industrial Engineering and Management

基　　金：国家自然科学基金资助项目(71271138);教育部人文社会科学规划基金项目(10YJA630187);上海市研究生创新基金项目(JWCXSL1101)

摘　　要：针对以最小化最大完工时间为目标的零等待流水线调度问题,提出了一种有效的混合群搜索算法。首先设计了一种IMM编码使群搜索算法能用于解决工件排序问题,其次根据零等待流水线调度问题的特征提出了一种完工时间的简化计算方法,最后构建了一种新的多邻域局部搜索策略以提高算法的性能。多邻域局部搜索中Swap邻域搜索只进行简单的邻域交换,复杂的计算发生在全邻域快速Insert邻域搜索过程中,以平衡计算代价和性能。通过对典型算例仿真和比较,验证了算法的有效性和优越性。This paper proposes a hybrid group search algorithm for the no-wait flow-shop scheduling problem with the makespan criterion.First of all,an IMM coding mechanism is proposed to transform the continuous variables into the job permutation.Then,a speed-up evaluation is employed.In addition,a local search algorithm based on multi-neighbourhood search is embedded to enhance exploitation,in which the Swap neighbourhood search only exchange neighbourhood,calculation occurs only in the fast Insert neighbourhood whole search process.Simulations and comparisons demonstrated the effectively and superiority of the proposed hybrid group search.

关 键 词：群搜索算法 零等待流水线调度 最大完工时间 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]