Genetic Algorithm for Scheduling in a Grid

IJCA Proceedings on National Conference on Innovative Paradigms in Engineering & Technology 2013
© 2013 by IJCA Journal
NCIPET2013 - Number 2
Year of Publication: 2013
Namrata Mahakalkar
A. R. Mahajan

Namrata Mahakalkar and A R Mahajan. Article: Genetic Algorithm for Scheduling in a Grid. IJCA Proceedings on National Conference on Innovative Paradigms in Engineering & Technology 2013 NCIPET 2013(2):1-5, December 2013. Full text available. BibTeX

	author = {Namrata Mahakalkar and A. R. Mahajan},
	title = {Article: Genetic Algorithm for Scheduling in a Grid},
	journal = {IJCA Proceedings on National Conference on Innovative Paradigms in Engineering & Technology 2013},
	year = {2013},
	volume = {NCIPET 2013},
	number = {2},
	pages = {1-5},
	month = {December},
	note = {Full text available}


The computational grid provides a promising platform for the deployment of various high-performance computing applications. In computational grid, an efficient scheduling of task onto the processors that minimizes the entire execution time is vital for achieving a high performance. High throughput computing (HTC) is of great importance in grid computing environments. HTC is aimed at minimizing the total makespan of all of the tasks submitted to the grid environment in long execution of the system. To achieve HTC in grids, suitable task scheduling algorithms should be applied to dispatch the submitted tasks to the computational resources appropriately. In this paper we present a Genetic Algorithm approach for scheduling operating room (OR) nurses. Most studies in operating room scheduling deal with patient flow analysis and physician scheduling, limited literature has focused on scheduling OR nurses. Our objective is to minimize nurses' idle time, overtime and non-consecutive assignments during overtime hours while maximizing demand satisfaction. The major constraints are: 1) shift constraints and 2) match between nurses' skill sets and surgery requirements. Due to the large size of the problem, finding an optimal solution is extremely difficult. Therefore, a Genetic Algorithms approach is proposed to find a set of good schedules in a reasonable amount of time.


  • Fangpeng Dong and Selim G. Akl, "Scheduling Algorithms for Grid Computing": State of the Art and Open Problems, School of Computing, Queen's University Kingston, Ontario January 2006.
  • R. Buyya and D. Abramson and J. Giddy and H. Stockinger,"Economic Models for Resource Management and Scheduling in Grid Computing", in J. of Concurrency and Computation: Practice and Experience, Volume 14, Issue. 13- 15, pp. 1507-1542,Wiley Press,
  • Goux, J. P. and Leyffer, S. Solving large MINLPs on computational grids. Optimization and Engineering, Vol 3, 2002, p. 327. 346.
  • E. Alba, A. J. Nebro, J. M. Troya, "Heterogeneous Computing and Parallel Genetic Algorithms," Journal of Parallel and Distributed Computing 62, pp. 1362-1385, 2002. 21
  • E. Alba, J. M. Troya, "Synchronous and Asynchronous Parallel Distributed Genetic Algorithms," Future Generation Computer Systems, 17(4):451-465, January 2001.
  • M. Nowostawski, R. Poli, "Parallel Genetic Algorithm Taxonomy," Proceedings of the Third International conference on knowledge-based intelligent information engineering systems (KES'99), pp. 88-92, Adelaide, 1999.
  • E. Cantu-Paz, "A Survey of Parallel Genetic Algorithms," Calculateurs Paralleles, Reseaux et Systems Repartis vol. 10 No. 2 pp. 141-171, 1998.
  • F. J. Villegas, T. Cwik, Y. Rahmat-Samii, and M. Manteghi, "A parallel electromagnetic Generic-Algorithm Optimization (EGO) application for patch antenna design," IEEE Transactions on Antennas and Propagation, Vol. 52, No. 9, pp. 2424-2435, 2004.
  • D. Abramson, J. Abela, "A Parallel Genetic Algorithm for Solving the School Timetabling Problem," Technical Report, Division of Information Technology, C. S. I. R. O, Melbourne, 1991.
  • Edmund K. Burke et al. The State of The Art of Nurse Rostering Journal of Scheduling 7: 441–499, 2004. ©2004 Kluwer Academic Publishers. Printed in the Netherlands.
  • Tiago M. Dias, Daniel F. Ferber, Cid C. de Souza and Arnaldo V. Moura, Constructing nurse schedules at large hospital International Transaction in Operational Research 10 (2003) 245–265
  • Amol C. Adamuthe and Rajankumar Bichkar, Hybrid Genetic Algorithmic Approaches for Personnel Timetabling and Scheduling Problems in Healthcare International Conference on Technology Systems and Management (ICTSM) 2011 Proceedings published by International Journal of Computer Applications® (IJCA)
  • Ivo Blochliger, Modelling staff scheduling problems A tutorial European Journal of Operational Research 158 (2004) 533–542
  • K. Krauter, R. Buyya, M. Maheswaran,Ataxonomy and survey of Grid resource management systems for distributed computing, Software Pract. Exp. 2 (2002) 135–164.
  • Y. Zhang, H. Ranke, J. E. Moreira, A. Sivasubramaniam, An integrated approach to parallel scheduling using gang-scheduling, backfilling, and migration, in: Lecture Notes in Computer Science, Vol. 2221, Springer, Berlin, 2001, pp. 133–158.
  • D. Thain, T. Tannenbaum, M. Livny, Condor and the Grid, in: A. J. G. Hey, F. Berman, G. C. Fox (Eds. ), Grid Computering: Making the Global Infrastructure a Reality,Wiley,West Sussex, England, 2003, pp. 299–335.