CONSTRAINT SOVLING ENGINE BASED NURSE ROSTERING WITH INTELLIGENT BACKTRACKING

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.