Object

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

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

Format:

application/pdf

Resource Identifier:

oai:bc.itl.waw.pl:1235 ; ISSN 1509-4553, on-line: ISSN 1899-8852

DOI:

10.26636/jtit.2012.2.1269

ISSN:

1509-4553

eISSN:

1899-8852

Source:

Journal of Telecommunications and Information Technology

Language:

ang

Rights Management:

Biblioteka Naukowa Instytutu Łączności

Object collections:

Last modified:

Aug 29, 2024

In our library since:

Jul 10, 2013

Number of object content hits:

103

All available object's versions:

https://bc.itl.waw.pl/publication/1542

Show description in RDF format:

RDF

Show description in OAI-PMH format:

OAI-PMH

Objects Similar

×

Citation

Citation style:

This page uses 'cookies'. More information