The week's pick
Random Articles
Reseach Article
Personnel Scheduling: Comparative Study of Backtracking Approaches and Genetic Algorithms
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 38 - Number 10 |
| Year of Publication: 2012 |
| Authors: Amol C. Adamuthe, Rajankumar S. Bichkar |
10.5120/4721-6834
|
Amol C. Adamuthe, Rajankumar S. Bichkar . Personnel Scheduling: Comparative Study of Backtracking Approaches and Genetic Algorithms. International Journal of Computer Applications. 38, 10 ( January 2012), 1-7. DOI=10.5120/4721-6834
Abstract
Scheduling and timetabling problems are multi-constrained constraint satisfaction problems that have huge search space. These problems are NP hard. This paper investigates the use of backtracking approaches to laboratory personnel scheduling problem in which the objective is to assign tasks to employees. The main objective of this work is to search for better solutions than those obtained by authors using genetic algorithmic approach. The performance of backtracking algorithms is tested for different variable orderings, value ordering and consistency enforcement techniques. It is observed that the variable and value ordering backtracking with consistency enforcement techniques gives better results than the chronological backtracking as well as the results reported in the literature. This work indicates that the problem instance under consideration might have even better solutions which can possibly be obtained by suitably modifying the genetic algorithmic approach used earlier by authors or by using other optimization techniques such as simulated annealing or Tabu search.
References
- Causmaecker, P.D., Demeester, P., Berghe, G.V., and Verbeke, B. 2004. Analysis of Real-world Personnel Scheduling Problems. 2004. In Proc. of 5th Practice and Theory of Automated Timetabling.
- Ernst, A. T., Jiang, H., Krishnamoorthy, M., and Sier, D. 2004. An annotated bibliography of personnel scheduling and rostering. J. Annals of Operations Research. 127, 21–144.
- Ernst, A. T., Jiang, H., Krishnamoorthy, M., and Sier, D. 2004. Staff scheduling and rostering: A review applications, methods and models. J. European Journal of Operational Research. 153, 3–27.
- Burke, E. K., Causmaecker, P. D., Berghe, G. V., and Landeghem, H. V. 2004. The state of the art of nurse rostering. J. Journal of Scheduling, 7, 441–499.
- Wren, A. 1996. Scheduling, Timetabling and Rostering - A Special Relationship? In Proc. of 1st Practice and Theory of Automated Timetabling, 46-75.
- Li, J., and Kwan, R.S.K. 2003. A Fuzzy Genetic Algorithm for Driver Scheduling. J. European Journal of Operational Research. 147, 334-344.
- Li J., Kwan, R.S.K. 2005. A Self-Adjusting Algorithm for Driver Scheduling. J. Journal of Heuristics. 11, 351-367.
- Miyashita, T. 2003. An Application of Immune Algorithms for Job-Shop Scheduling Problems. In Proc. of the 5th IEEE International Symposium on Assembly and Task Planning.
- Jensen, M.T. 2003. Generating Robust and Flexible Job Shop Schedules Using Genetic Algorithms. J. IEEE Transactions on Evolutionary Computation. 7, 275-288.
- Ombuki B.M., and Ventresca, M. 2004. Local Search Genetic Algorithms for the Job Shop Scheduling Problem. J. Applied Intelligence. 21, 99-109.
- Wilke, P., Grobner, M., and Oster, N. 2002. A Hybrid Genetic Algorithm for School Timetabling.
- Karova, M. 2004. Solving Timetabling Problems Using Genetic Algorithms. Proc. of 27th Int’l Spring Seminar on Electronic Technology.
- Qu R., and Burke, E. K. 2005. Hybrid Variable Neighborhood HyperHeuristics for Exam Timetabling Problems. In Proc. of 6th Metaheuristics International Conference.
- Kumar, V. 1992. Algorithms for Constraint Satisfaction Problems: A Survey. AI Magazine. 13(1), 32–44.
- Bartak, R. Constraint propagation and backtracking based search.
- Horowitz, E., Sahni, S., and Rajasekaran, S. 2008. Fundamentals of Computer Algorithms. Universities Press.
- Dechter, R., and Frost, D. 2002. Backjump-based backtracking for constraint satisfaction problems. J. Artificial Intelligence. 136, 147–188.
- Musliu, N. 2001. Intelligent search methods for workforce scheduling: New ideas and practical applications. PhD thesis. Fakultat Fur, Tecnische Universitat Wien, Vienna, Austria.
- Jegou, P., and Terrioux, C. 2003. Hybrid backtracking bounded by tree decomposition of constraint networks. J. Artificial Intelligence. 146, 43–75.
- Sadeh, N., Sycara, K., and Xiong, Y. 1995. Backtracking techniques for the job shop scheduling constraint satisfaction problem.
- Lau, H. C. 1996. Combinatorial approaches for hard scheduling problems in manpower scheduling. J. Operations research. 39(1).
- Brailsford, S. C., Potts, C. N., and Smith, B. M. 1999. Constraint satisfaction problems: Algorithms and applications. J. European Journal of Operational Research. 119, 557-581.
- Kondrak, G. 1994. A Theoretical Evaluation of selected backtracking algorithms. Thesis Master of Science, Edmonton, Alberta.
- Prosser, P. 1993. Domain filtering can degrade intelligent backtrack search. In Proc. of the International Joint Conference on Artificial Intelligence, 262-267.
- Prosser, P. 1993. Forward checking with backtracking. Technical report AISL 48-93, University of Strathclyde.
- Franses, P., and Post, G. 2002. Personnel Scheduling in Laboratories. In Proc. of 4th Practice and Theory of Automated Timetabling, 113-119.
- Sadeh, N. M, and Fox, M. S. 1995. Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem. Technical report CMU-RI-TR-95-39.
- Mackworth, A.K., and Freuder, E.C. 1985. The Complexity of some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems. J. Artificial Intelligence. 25, 65-74.
- Adamuthe, A. C., and Bichkar, R. S. 2011. Genetic algorithmic approach for personnel timetabling. In Proc. of International Conference on Technology Systems and Management 2011, 69-76, Springer- Verlag.
- Burke, E.K., Cowling, P., Causmaecker, P.D., and Berghe, G.V. 2001. A Memetic Approach to the Nurse Rostering Problem. J. Applied Intelligence. 15, 199-214.
- Ozcan, E. 2005. Memetic Algorithms for Nurse Rostering. In Proc. of 20th International Symposium on Computer and Information Sciences, 482-492.
- Maenhout, B., and Vanhoucke, M. 2006. A Comparison and Hybridization of Crossover Operators for the Nurse Scheduling Problem. Working Papers of Faculty of Economics and Business Administration, Ghent University.
Index Terms
Keywords