Title: A multi-objective simulated annealing algorithm for permutation flow shop scheduling problem

Authors: B. Shahul Hamid Khan, Kannan Govindan

Addresses: Indian Institute of Information Technology Design and Manufacturing (IIITD&M), Kancheepuram, IIT Madras Campus, Chennai, India. ' School of Business, University of Southern Denmark, Odense, Denmark

Abstract: Exact and heuristic algorithms have been proposed over the years for solving static permutation flow shop scheduling problems with the objectives of minimising makespan, total tardiness, and total flow time, etc. Of late, attempts are being made to consider more than one objective at a time, and develop algorithms in order to obtain a set of Pareto-optimal solutions. In such multi-objective scheduling problems, it is common to obtain a set of Pareto-optimal or efficient solutions such that at least one such solution is not inferior to any other given solution not contained in the set, and the solutions in that set does not dominate each other. In this paper, we consider a multi-objective permutation flow shop problem with the aim of generating non-dominated solutions with the aim of minimising makespan and maximum tardiness of jobs. A multi-objective simulated annealing (MOSA) algorithm has been developed towards this purpose. The proposed algorithm is evaluated using randomly generated problems. The efficiency of proposed algorithm, based on some comparison metrics, is compared with a distinguished multi-objective genetic algorithm known as strength Pareto evolutionary algorithm II (SPEA-II) and multi-objective genetic local search (MOGLS). The computational results show that the proposed MOSA performs better than SPEA-II and MOGLS.

Keywords: flow shop scheduling; makespan; maximum tardiness; simulated annealing; multi-objective optimisation; permutation flow shops; genetic algorithms; local search.

DOI: 10.1504/IJAOM.2011.040661

International Journal of Advanced Operations Management, 2011 Vol.3 No.1, pp.88 - 100

Published online: 30 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article