Research Article Open Access

CONSTRAINT SOVLING ENGINE BASED NURSE ROSTERING WITH INTELLIGENT BACKTRACKING

S. Chitrakala1, S. P. Surendernath1 and R. Priyatharshini2
  • 1 Anna University, India
  • 2 , India
Journal of Computer Science
Volume 10 No. 10, 2014, 1977-1984

DOI: https://doi.org/10.3844/jcssp.2014.1977.1984

Submitted On: 9 December 2013 Published On: 22 May 2014

How to Cite: Chitrakala, S., Surendernath, S. P. & Priyatharshini, R. (2014). CONSTRAINT SOVLING ENGINE BASED NURSE ROSTERING WITH INTELLIGENT BACKTRACKING. Journal of Computer Science, 10(10), 1977-1984. https://doi.org/10.3844/jcssp.2014.1977.1984

Abstract

Efficient utilization of time and effort is essential in Personnel scheduling problems to evenly balance the workload among the people and attempt to satisfy the personnel preferences. In Constraint Satisfaction Problem based scheduling problems, when a branch of the search fails the backtracking search algorithm back up to the preceding variable and try a different value for it. So here the most recent decision point is revisited. Its run-time complexity for most nontrivial problems is still exponential. A solution is intelligent backtracking scheme in which backtracking is done directly to the variable that caused the failure. This study proposes Constraint Satisfaction Problem based Nurse Rostering using Intelligent Backtracking approach. The proposed Minimal Critical Set based Intelligent Backtracking (MCS-IBT) algorithm incorporates Critical Set detection which is followed by Minimal Critical Set reduction in order to reduce the search space for nurse rostering. MCS_IBT overcomes missing good MCSs by visiting optimal number of sets. This study finds its applications in scheduling, temporal reasoning, graph problems, floor plan design, the planning of genetic experiments and the satisfiability problems. The implemented system is tested on the real life data from the hospital and the results shown remarkable performance.

  • 863 Views
  • 1,620 Downloads
  • 0 Citations

Download

Keywords

  • Constraint Satisfaction Problem
  • Intelligent Backtracking
  • Nurse Rostering
  • Minimal Critical Set