Constraint satisfaction problem based modelling and value ordering based heuristic for nurse scheduling

• Autorzy: Djeffal L. , Goncalves G. , Babes M.
• Języki publikacji: EN

Abstrakty

EN

Nurse Scheduling Problem (NSP) consists of assigning shift-types (morning, afternoon and night) to qualified personnel over a certain planning period. It is a difficult and time-consuming task. In this paper we present a formulation of the hospital Nurse Scheduling Problem just like Constraint Satisfaction Problem "CSP" based constraint programming in order to find a solution, which minimizes the violation of Nurses' preferences. We would suggest a flexibility tool for helping to decide and for making negotiation easier. Our originality lies in the modelling of the problem, by defining the global constraints and in the algorithm of resolution to solve it, by proposing a new value ordering based heuristic for assignment of the decision variables taking into account the set of Nurses preferences. Our heuristic is based on the structure of the CSP and on the properties of constraints. It allows the reduction of the search space for solution and returns a solution within few second.

Słowa kluczowe

EN

constraint programming; global constraints; NP-complete; scheduling; heuristic

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2006
• Tom: Vol. 14, nr 2
• Strony: 7--28
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Djeffal L.

autor

Goncalves G.

autor

Babes M.

• Universite Hadj-lakhdar Batna - Faculte des sciences 05000 - Algerie,

Bibliografia

• [1] E. BURKE, P. De CAUSMAECKER, S. PETROVIC, G. VANDEN BERGHE, Variable Neighbourhood Search for Nurse Rostering Problems, In Mauricio G.C. RESENDE, Jorge PINOH de Sousa (editors), Meta-heuristics: Computer Decision-Making, Capter7, Kluwer, 2003, 153-172.
• [2] J.H. OLDENKAMP, Quality in Fives: On the analysis, Operationalization and application of Nursing Schedule Quality, University of Groningen, 1996
• [3] B. CHEAN. H. LI, A. LIM, B. RODRIGUES, Nurse Rostering Problems-a bibliographic Survey, European journal of operational research, www.elsevier.com/locate/dsw, 2003
• [4] K.A. DOWSLAND, Nurse scheduling with taboo search and strategic oscillation, European Journal of Operational Research 106, 1998, pp 393-407.
• [5] K. NONOBE, T. IBARAKI, A taboo search approach to the constraint satisfaction problem as a general problem solver, European Journal of Operational Research 106, 1998, pp 599-623.
• [6] L. DJEFFAL, M. BABES, Contribution à l’élaboration d’un algorithme de recherche arborescent par la programmation par contrainte et la programmation orientée objet, « Application Hospitalière », Proceeding of Conférence Internationale en Informatique Appliquée CIIA’05, Bourdj-BouArréridj, Algérie, November 2005
• [7] S. KUSUMOTO, Nurse Scheduling Using ILOG Solver, Proceeding of the second Ilog solver and scheduler users Conference. Paris: ILOG, 1996
• [8] S. ABDENNADHER, H. SCHLENKER, Nurse scheduling using CLP, AAAI/IAAI, 1999, pp. 838-843.
• [9] A.H.W. CHUN, S.H.C CHAN, and al, Nurse Rostering at the Hospital Authority of HONG–KONG, AAAI/IAAI, 2000, pp 951-956.
• [10] H. MEYER auf’m HOFE, Nurse Rostering as Constraint Satisfaction with Fuzzy Constraints and inferred control stratégies, DIMACS, 2001, pp67-99.
• [11] C. LECOUTRE, F.BOUSSEMART, F.HEMERY, Technique de retour arrière intelligent versus heuristiques dirigées par les conflits. JNPC'04, pp 235-250, 2004.
• [12] S. ABDENNADHER and H. SCHLENKER, INTERDIP-An interactive constraint based nurse scheduler, in PACLP-99. Available from http://www.pms.informatik.unimuenchen.de/~interdip, 1999
• [13] H. MEYER auf’m HOFE, Nurse rostering as constraint satisfaction with fuzzy constraints and inferred control strategies, in E.C FREUDER, R.J. WALLACE, constraint programming and large scale discrete optimization, DIMACS Series in Discrete Mathematics and TCS, VOL 75, DIMACS, pp 67- 99, 2001
• [14] H. MEYER auf’m HOFE, ConPlan/SIEDA plan: Personal assignment as a problem of HCSP, in proceedings of ICPA of Constraint technology, pp 257-272, 1997
• [15] N. SADEH and M.S. FOX. Variable and value ordering heuristics for Activity Based Job-Shop Scheduling. In proceedings of the fourth International conference on Expert Systems in production and opération Management, pp 134-144, 1990
• [16] S. MINTON and al, Minimizing Conflicts: A Heuristic Repair Method for Constraint Satisfaction and Scheduling Problems.1994
• [17] R. DETCHER and D. FROST. Look a-head value ordering for constraint satisfaction Problem. In proceeding of IJCAI'95; pages 572-578, Montréal Canada 1995
• [18] D. SABIN and E.C. FREUDER, Understanding and Improving the MAC Algorithm. In G. SMOLKA, editor, principle and practice of constraint pprogramming – CP97, LNCS 1330, pp167–181, Springer 1997.
• [19] G.Y.C. WONG, A.H.W. CHUN, Constraint-based rostering using meta-level reasoning and probability-based ordering. Engineering Applications of Artificial Intelligence, pp599-610, 2004.
• [20] G. PESANT, A Filtering Algorithm for the Stretch constraint. In proceeding of the seventh ICPP of Constraint programming, pp183-195, 2001
• [21] G. PESANT, A Regular Language Membership Constraint for finite sequence of Variables, In CP’04, pp482-495, 2004.