Efficient heuristics for the parallel blocking flow shop scheduling problem. (15th May 2017)

• Record Type: Journal Article
• Authors: Ribas, Imma; Companys, Ramon; Tort-Martorell, Xavier
• Is Part Of: Expert systems with applications. Volume 74(2017)
• Page Start: 41
• Page End: 54
• Publication Date: 2017-05-15
• Subjects: Parallel flow shop -- Distributed permutation flow shop -- Blocking flow shop -- Scheduling; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2017.01.006
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: New Constructive heuristic for both the PBFSP and the DBFSP. Combination of IGA and ILS methods with two types of VNS. A MILP model solved for small-sized instances. The proposed methods are very effective. Abstract: We consider the NP-hard problem of scheduling n jobs in F identical parallel flow shops, each consisting of a series of m machines, and doing so with a blocking constraint. The applied criterion is to minimize the makespan, i.e., the maximum completion time of all the jobs in F flow shops (lines). The Parallel Flow Shop Scheduling Problem (PFSP) is conceptually similar to another problem known in the literature as the Distributed Permutation Flow Shop Scheduling Problem (DPFSP), which allows modeling the scheduling process in companies with more than one factory, each factory with a flow shop configuration. Therefore, the proposed methods can solve the scheduling problem under the blocking constraint in both situations, which, to the best of our knowledge, has not been studied previously. In this paper, we propose a mathematical model along with some constructive and improvement heuristics to solve the parallel blocking flow shop problem (PBFSP) and thus minimize the maximum completion time among lines. The proposed constructive procedures use two approaches that are totally different from those proposed in the literature. These methods are used as initial solution procedures of an iterated local search (ILS) and an iterated greedy algorithm (IGA), both of which are combined with a variable neighborhood search (VNS). The proposed constructive procedure and the improved methods take into account the characteristics of the problem. The computational evaluation demonstrates that both of them –especially the IGA– perform considerably better than those algorithms adapted from the DPFSP literature.