Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion. (January 2017)

• Record Type: Journal Article
• Authors: Tasgetiren, M. Fatih; Kizilay, Damla; Pan, Quan-Ke; Suganthan, P.N.
• Is Part Of: Computers & operations research. Volume 77(2017)
• Page Start: 111
• Page End: 126
• Publication Date: 2017-01
• Subjects: Meta-heuristics -- Blocking flowshop -- Iterated greedy algorithm -- Variable neighborhood search -- Constructive heuristics; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.07.002
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: Recently, iterated greedy algorithms have been successfully applied to solve a variety of combinatorial optimization problems. This paper presents iterated greedy algorithms for solving the blocking flowshop scheduling problem (BFSP) with the makespan criterion. Main contributions of this paper can be summed up as follows. We propose a constructive heuristic to generate an initial solution. The constructive heuristic generates better results than those currently in the literature. We employ and adopt well-known speed-up methods from the literature for both insertion and swap neighborhood structures. In addition, an iteration jumping probability is proposed to change the neighborhood structure from insertion neighborhood to swap neighborhood. Generally speaking, the insertion neighborhood is much more effective than the swap neighborhood for the permutation flowshop scheduling problems. Instead of considering the use of these neighborhood structures in a framework of the variable neighborhood search algorithm, two powerful local search algorithms are designed in such a way that the search process is guided by an iteration jumping probability determining which neighborhood structure will be employed. By doing so, it is shown that some additional enhancements can be achieved by employing the swap neighborhood structure with a speed-up method without jeopardizing the effectiveness of the insertion neighborhood. We also show that the performance of the iterated greedy algorithm significantly depends on the speed-up method employed. The parameters of the proposed iterated greedy algorithms are tuned through a design of experiments on randomly generated benchmark instances. Extensive computational results on Taillard's well-known benchmark suite show that the iterated greedy algorithms with speed-up methods are equivalent or superior to the best performing algorithms from the literature. Ultimately, 85 out of 120 problem instances are further improved with substantial margins. Highlights: A new constructive heuristic is proposed. Speed-up methods from the literature are adapted very well. IG algorithm is superior with the speed-up method. But without a speed-up method, its performance is poor. We propose an iteration jumping probability to employ the swap neighborhood structure. Ultimately, 85 out of 90 problem instances are further improved.