A new heuristic for the flowshop scheduling problem to minimize makespan and maximum tardiness

A new heuristic for the flowshop scheduling problem to minimize makespan and maximum tardiness

0.00 Avg rating0 Votes
Article ID: iaor20103983
Volume: 47
Issue: 1
Start Page Number: 273
End Page Number: 288
Publication Date: Jan 2009
Journal: International Journal of Production Research
Authors: ,
Keywords: flowshop
Abstract:

This paper presents a new heuristic for solving the flowshop scheduling problem that aims to minimize makespan and maximize tardiness. The algorithm is able to take into account the aforementioned performance measures, finding a set of non-dominated solutions representing the Pareto front. This method is based on the integration of two different techniques: a multi-criteria decision-making method and a constructive heuristic procedure developed for makespan minimization in flowshop scheduling problems. In particular, the technique for order preference by similarity of ideal solution (TOPSIS) algorithm is integrated with the Nawaz-Enscore-Ham (NEH) heuristic to generate a set of potential scheduling solutions. To assess the proposed heuristic's performance, comparison with the best performing multi-objective genetic local search (MOGLS) algorithm proposed in literature is carried out. The test is executed on a large number of random problems characterized by different numbers of machines and jobs. The results show that the new heuristic frequently exceeds the MOGLS results in terms of both non-dominated solutions, set quality and computational time. In particular, the improvement becomes more and more significant as the number of jobs in the problem increases.

Reviews

Required fields are marked *. Your email address will not be published.