Application of Lagrangean duality for preference scheduling of nurses
MetadataShow full item record
The growing nursing shortage requires sufficient efforts be made to keep nurse satisfaction levels high for staff retention. Providing considerable flexibility by allowing the nurses to have a say in their schedule either by means of shift bidding or through preference requests has shown to increase satisfaction levels among nurses. Nurse scheduling is known to be a very difficult combinatorial problem because of many the constraints and many possible solutions. In addition, an attempt to satisfy nurse preferences, meet variable nursing requirements subject to acuity and number of admits, various rules and regulations, combination of numerous overlapping shift types for a 24 hour a day, 7 day a week operation, while trying to produce a balanced schedule adds to the complexity of the problem. A preference scheduling problem is formulated as a mixed integer-linear program and solved using a commercial algorithm. The idea is to allow an increased number of working day preferences for individual nurses. Later, an alternate algorithm is presented for the same problem, with the aim of reducing the run time especially in large scale scenarios. This method is based on Lagrangean duality and employs an implicit enumeration scheme to generate feasible schedules for each nurse. With the shift demand constraints relaxed, the associated Lagrange multipliers are updated using a sub-gradient search algorithm. The methodology has been tested over a period of time and a series of problems on data provided by a large hospital in Western New York which currently generates schedules manually. Our methods can generate high quality solutions within a few minutes. The algorithm was also tested with an artificial scaling up of the number of nurses, and the results were promising. This method presents a unique advantage of linear correlation of computation time with the scale of data.