A SIMULATED ANNEALING ALGORITHM FOR SOME CLASS OF DISCRETE-CONTINUOUS SCHEDULING PROBLEMS
Józefowska Joanna, Mika Marek, Węglarz Jan
Poznań University of Technology, Institute of Computing Science,
Piotrowo 3A, 60-965 Poznań, Poland
e-mail: mika@man.poznan.pl
DOI: 10.12921/cmst.1996.02.01.73-85
OAI: oai:lib.psnc.pl:476
Abstract:
In this paper a Simulated Annealing algorithm is proposed and applied to the n-job and m-machme discrete-continuous scheduling problem with the objective to minimize the makespan. This problem can be divided into two interrelated subproblems (i) constructing a feasible sequence of jobs on machines and (ii) allocating the continuos resource among jobs already sequenced. The application of the Simulated Annealing algorithm operating on a space of feasible sequences is presented. By computational experiment on randomly generated test problems, the proposed algorithm is compared with two other heuristics, namely Multi-start Iterative Improvement algorithm and Random Sampling Technique.
References:
[1] Aarts. E.H.L., and Korst. J., Simulated Annealing and Boltzman Machines, Wiley. Chichester. 1989.
[2] Błażewicz. J., Ecker. K.H.. Schmidt. G., Węglarz. J., Scheduling in Computer and Manufacturing Systems. 2nd edition. Springer Verlag, Berlin (1994).
[3] Józefowska. J., and Węglarz. J., On a methodology for discrete-continuous scheduling Research Report of the Institute of Computing Science. Poznań University of Technology . RA-004/95 (1995).
[4] van Laarhoven. P.J.M., and Aarts, E.H.L., Simulated Annealing: Theory and Applications. Kluwer Academic Publishers, Dordrecht. 1987.
[5] Węglarz. J., Multiprocessor scheduling with memory allocation – a deterministic approach . IEEE Trans. Computers C-29/8, 703-710 (1980).
In this paper a Simulated Annealing algorithm is proposed and applied to the n-job and m-machme discrete-continuous scheduling problem with the objective to minimize the makespan. This problem can be divided into two interrelated subproblems (i) constructing a feasible sequence of jobs on machines and (ii) allocating the continuos resource among jobs already sequenced. The application of the Simulated Annealing algorithm operating on a space of feasible sequences is presented. By computational experiment on randomly generated test problems, the proposed algorithm is compared with two other heuristics, namely Multi-start Iterative Improvement algorithm and Random Sampling Technique.
[1] Aarts. E.H.L., and Korst. J., Simulated Annealing and Boltzman Machines, Wiley. Chichester. 1989.
[2] Błażewicz. J., Ecker. K.H.. Schmidt. G., Węglarz. J., Scheduling in Computer and Manufacturing Systems. 2nd edition. Springer Verlag, Berlin (1994).
[3] Józefowska. J., and Węglarz. J., On a methodology for discrete-continuous scheduling Research Report of the Institute of Computing Science. Poznań University of Technology . RA-004/95 (1995).
[4] van Laarhoven. P.J.M., and Aarts, E.H.L., Simulated Annealing: Theory and Applications. Kluwer Academic Publishers, Dordrecht. 1987.
[5] Węglarz. J., Multiprocessor scheduling with memory allocation – a deterministic approach . IEEE Trans. Computers C-29/8, 703-710 (1980).
