Fast Iterated Local Search Algorithm with High Order Neighborhood for No-wait Flowshop Scheduling Problem
Most of the metaheuristic algorithms for the no-wait flowshop scheduling problem with makespan criterion have adopted the O(n2)size insertion neighborhoods,and higher order(polynomial size)neighborhoods are seldom tried.However,higher order neighborhoods can improve the solution quality of metaheuristic algorithms.The paper presents a high order neighborhood with O(n4)size called nonadjacent job block exchange neighborhood and develops a fast search algorithms with O(n2)time complexity for it.An iterated local search algorithm is further presented for the considered problem,where the new neighborhood along with the insertion neighborhood is used in variable neighborhood decent to provide a local search procedure for iterated local search.Experimental comparison shows that the higher order neighborhood based iterated local search algorithm is both fast and effective.
Scheduling No-wait Flowshop Makespan Iterated Local Search Neighborhood
Chuyang Wang
Department of Computer Science & Application,Zhengzhou Institute of Aeronautical Industry Management,Zhengzhou,China,450015
国际会议
长沙
英文
4460-4464
2014-05-31（万方平台首次上网日期，不代表论文的发表时间）