Optimizing Bicriteria Flow Shop Scheduling Problem by Simulated Annealing Algorithm

https://doi.org/10.1016/j.procs.2013.05.259Get rights and content
Under a Creative Commons license
open access

Abstract

We consider the flow shop scheduling problem with minimizing two criteria simultaneously: the total completion time (makespan) and the sum of tardiness of jobs. The problem is strongly NP-hard, since for each separate criteria the problem is strongly NP-hard. There is a number of heuristic algorithms to solve the flow shop problem with various single objectives, but usage of those heuristics to multi-criteria flow shop problems is rather limited. In this paper we propose a new idea of the use of simulated annealing method to solve certain multi-criteria problem. Especially, we define a new acceptance rules and the mechanism of moving the search in different regions of solution space by using so called drift. To illustrate quality of the proposed approach, we present results of the computational experiment provided on well known benchmarks.

Keywords

flowshop
simulated annealing
bicriteria optimization ;

Cited by (0)

Selection and peer review under responsibility of the organizers of the 2013 International Conference on Computational Science.