Abstract
The paper considers multiprocessor task scheduling in multistage hybrid flowshops. To solve the above problem a population based approach is suggested. The population learning algorithm based on several local search procedures has been proposed and implemented. The algorithm has been evaluated by means of a computational experiment in which 160 benchmark instances have been solved and compared with the available upper bounds. It has been possible to improve 45% of previously known upper bounds.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blażewicz, J., Drozdowski, M., Węglarz, J.: Scheduling independent 2-processor tasks to minimize schedule length. Information Processing Letters 18, 267–273 (1984)
Blażewicz, J., Drozdowski, M., Węglarz, J.: Scheduling multiprocessor tasks to minimize schedule length. EEE Transactions on Computers C-35, 81–96 (1986)
Blażewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., Węglarz, J.: Scheduling Computer and Manufacturing Processes. Springer, Berlin (1996)
Lloyd, E.L.: Concurrent task systems. Operations Research 29, 189–201 (1981)
Brucker, P., Kramer, B.: Shop Scheduling Problems with multiprocessor tasks on dedicated processors. Annals of Operations Research 50, 13–27 (1995)
Feo, T.A., Resende, M.G.C.: A probabilistic heuristic for computationally difficult set covering problems. Operations Research Letters 8, 706–712 (1989)
Jędrzejowicz, P.: Social Learning Algorithm as a Tool for Solving Some Difficult Scheduling Problems. Foundation of Computing and Decision Sciences 24, 51–66 (1999)
Jędrzejowicz, J., Jędrzejowicz, P.: Permutation Scheduling Using Population Learning Algorithm. In: Damiani, E., et al. (eds.) Knowledge-based Intelligent Information Engineering Systems and Allied Technologies, pp. 93–97. IOS Press, Amsterdam (2002)
Moscato, P.: Memetic Algorithms: A short introduction. In: Corne, D., Dorigo, M., Glover, F. (eds.) New Ideas in Optimization, pp. 219–234. McGraw-Hill, New York (1999)
Oǧuz, C., Zinder, Y., Ha Do, V., Janiak, A., Lichtenstein, M.: Hybrid flow-shop scheduling problems with multiprocessor task systems. Working paper, The Hong Kong Polytechnic University, Hong Kong SAR (2001)
Reynolds, R.G.: An Introduction to Cultural Algorithms. In: Sebald, A.V., Fogel, L.J. (eds.) Proceedings of the Third Annual Conference on Evolutionary Programming, pp. 131–139. World Scientific, River Edge (1994)
Sivrikaya-Şerifoǧlu, F., Ulusoy, G.: A genetic algorithm for multiprocessor task scheduling in multistage hybrid flowshops. Working paper, Abant Izzet Baysal University, Bolu (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jędrzejowicz, J., Jędrzejowicz, P. (2003). Population-Based Approach to Multiprocessor Task Scheduling in Multistage Hybrid Flowshops. In: Palade, V., Howlett, R.J., Jain, L. (eds) Knowledge-Based Intelligent Information and Engineering Systems. KES 2003. Lecture Notes in Computer Science(), vol 2773. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45224-9_40
Download citation
DOI: https://doi.org/10.1007/978-3-540-45224-9_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40803-1
Online ISBN: 978-3-540-45224-9
eBook Packages: Springer Book Archive