A hybrid metaheuristic algorithm for a parallel machine scheduling problem with dependent setup times. (May 2019)

• Record Type: Journal Article
• Authors: Báez, Sarahí; Angel-Bello, Francisco; Alvarez, Ada; Melián-Batista, Belén
• Is Part Of: Computers & industrial engineering. Volume 131(2019)
• Page Start: 295
• Page End: 305
• Publication Date: 2019-05
• Subjects: Parallel machine scheduling -- Total completion time -- Setup time -- GRASP -- Variable neighborhood search; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.03.051
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We tackle a parallel machine scheduling problem with dependent setup times. We consider the goal of minimizing the total completion time. We design a Hybrid Metaheuristic Algorithm (HMA) based on GRASP and VNS. HMA is compared with the optimal results achieved by a mathematical model. HMA outperforms the results obtained by the current state of the art algorithm. Abstract: This work proposes a hybrid algorithm that combines GRASP and Variable Neighborhood Search for solving a parallel machine scheduling problem with dependent setup times for minimizing the total completion time. The aim of the problem is to assign jobs to machines and determine the order in which jobs have to be processed on the machines, in such a way that the sum of the completion times of all jobs is minimized. The designed algorithm consists of two phases: construction and improvement, that is performed by means of a general variable neighborhood search. The instances considered to test our algorithm are taken from the literature and the results are compared with the exact solutions obtained by a mathematical model and with the solutions provided by the best heuristic from the literature, which is outperformed by the proposed hybrid algorithm.