Abstract
This paper describes a hybrid grouping genetic algorithm for a multiprocessor scheduling problem, where a list of tasks has to be scheduled on identical parallel processors. Each task in the list is defined by a release date, a due date and a processing time. The objective is to minimize the number of processors used while respecting the constraints imposed by release dates and due dates. We have compared our hybrid approach with two heuristic methods reported in the literature. Computational results show the superiority of our hybrid approach over these two approaches. Our hybrid approach obtained better quality solutions in shorter time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Gajski, D.D., Dutt, N.D., Wu, A.C.-H., Lin, S.Y.-L.: High Level Synthesis: Introduction to Chip and System Design. Kluwer Academic Publishers, Norwell (1992)
Lee, J.-H., Hsu, Y.-C., Lin, Y.-L.: A New Integer Linear Programming Formulation for the Scheduling Problem in Data Path Synthesis. In: Proceedings of the 1989 IEEE International Conference on Computer-Aided Design, pp. 20–23. IEEE Computer Society Press, New York (1989)
Sevaux, M., Sörensen, K.: A Tabu Search Method for High Level Synthesis. In: Proceedings of the Francoro V / Roadef 2007, Grenoble, France, pp. 395–396 (2007)
Sevaux, M., Thomin, P.: Heuristics and Metaheuristics for Parallel Machine Scheduling: A Computational Evaluation. In: Proceedings of the 4th Metaheuristics International Conference (MIC 2001), Porto, Portugal, pp. 16–20 (2001)
Sevaux, M., Singh, A., Rossi, A.: Tabu Search for Multiprocessor Scheduling: Application to High Level Synthesis. Communicated to Asia Pacific Journal of Operational Research (2009)
Falkenauer, E.: New Representations and Operators for GAs Applied to Grouping Problems. Evolutionary Computation 2, 123–144 (1992)
Falkenauer, E.: Genetic Algorithms and Grouping Problems. John Wiley & Sons, Chichester (1998)
Davis, L.: Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York (1991)
Singh, A., Gupta, A.K.: Two Heuristics for the One-Dimensional Bin-Packing Problem. OR Spectrum 29, 765–781 (2007)
Rossi, A., Sevaux, M.: Mixed-Integer Linear Programming Formulation for High Level Synthesis. In: Proceedings of the Eleventh International Workshop on Project Management and Scheduling, Istanbul, Turkey, pp. 222–226 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Singh, A., Sevaux, M., Rossi, A. (2009). A Hybrid Grouping Genetic Algorithm for Multiprocessor Scheduling. In: Ranka, S., et al. Contemporary Computing. IC3 2009. Communications in Computer and Information Science, vol 40. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03547-0_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-03547-0_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03546-3
Online ISBN: 978-3-642-03547-0
eBook Packages: Computer ScienceComputer Science (R0)