A GRASP meta-heuristic for the hybrid flowshop scheduling problem

Abstract

This paper considers a hybrid flowshop scheduling problem (HFSP). Since this problem is NP-hard, most of literature has been centred on the analysis of meta-heuristics and hybridised procedures. However, intelligent manufacturing systems in actual industrial practices mostly prefer the use of simple algorithms. The greedy randomised adaptive search procedure (GRASP) is among the simplest approximation algorithms providing good results when solving hard combinatorial optimisation problems that currently exist in literature. The objective is to propose a GRASP to solve the classical HFSP under the optimisation of different objectives. The goal is not to solve a multi-objective problem, instead to design a solution procedure that performs well under various optimisation criteria. This performance is analysed through a set of computational experiments using well-known data-sets from the literature. The proposed GRASP obtains satisfactory results in comparison with traditional dispatching rules and can be easily implemented for efficient decision-making in real industrial practice.

Keywords:

• Scheduling
• hybrid flowshop
• GRASP
• dispatching rules