Optimizing Bicriteria Flow Shop Scheduling Problem by Simulated Annealing Algorithm

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.