Title:

Effective Design of the Simulated Annealing Algorithm for the Flowshop Problem with Minimum Makespan Criterion, Journal of Telecommunications and Information Technology, 2012, nr 2

Creator:

Hurkała, Jarosław ; Hurkała, Adam

Subject and Keywords:

simulated annealing ; heuristics ; flowshop ; makespan

Description:

In this paper we address the n-job, m-machine flowshop scheduling problem with minimum completion time (makespan) as the performance criterion. We describe an efficient design of the Simulated Annealing algorithm for solving approximately this NP-hard problem. The main difficulty in implementing the algorithm is no apparent analogy for the temperature as a parameter in the flowshop combinatorial problem. Moreover, the quality of solutions is dependent on the choice of cooling scheme, initial temperature, number of iterations, and the temperature decrease rate at each step as the annealing proceeds. We propose how to choose the values of all the aforementioned parameters, as well as the Boltzmann factor for the Metropolis scheme. Three perturbation techniques are tested and their impact on the solutions quality is analyzed. We also compare a heuristic and randomly generated solutions as initial seeds to the annealing optimization process. Computational experiments indicate that the proposed design provides very good results – the quality of solutions of the Simulated Annealing algorithm is favorably compared with two different heuristics.

Publisher:

Instytut Łączności - Państwowy Instytut Badawczy, Warszawa

Date:

2012, nr 2

Resource Type:

artykuł

Format:

application/pdf

Resource Identifier:

ISSN 1509-4553, on-line: ISSN 1899-8852

Source:

Journal of Telecommunications and Information Technology

Language:

ang

Rights Management:

Biblioteka Naukowa Instytutu Łączności