A Solution Method for Manpower Scheduling Problems by RCPSP/τ

In the resource-constrained project scheduling problem (RCPSP), the available maximum amount of the resource in each time is restricted, and the total of the resource consumption of the activities in each time cannot exceed this value. This problem can deal with many types of scheduling problems by considering various kinds of attributes on the activities to be resource constraints. By contrast the manpower scheduling problem (it is called a staff-scheduling problem or a shift-scheduling problem, also) have peculiar shift constraints, such as the number of necessary staffs at each time, the interval between duties, the maximum consecutive duties of each staff, and the prohibition of the some staff's pair. It becomes difficult to solve within the frame of standard RCPSP by those constraints. In this research, we show that the manpower scheduling problems can be solved by RCPSP if we use the extended RCPSP (it is called RCPSP/tau) and use some dummy resources. We evaluate the method by a sample data of the nurse-scheduling problem that is a typical shift scheduling problem. The data is for the three shifts nurse scheduling problem that we made by slightly modifying a real problem. Using our method, we could solve the shift scheduling problem in 445 second by a standard PC. To solve the problem, we use our RCPSP engine by transforming the constraints to the resource constraints, and we did not change a programming code of the engine.