LP-relaxation-simulated annealing manpower scheduling algorithm for service industry

In the increasingly competitive service industry, utilization of precious manpower resources can make the difference in terms of profitability or even survivability. Current scheduling methods and solutions are designed to suit particular case or class of problems; in which significant modification are often required when they are to be applied to different class of problems. In this paper, a general manpower scheduling model with flexible algorithm to provide consistent near optimal solution is proposed. The general set covering model is able to cater for overtime works, part time workers, flexible shift length, and multi-skilled workers; whereas the algorithm based on LP-relaxation and simulated annealing was consistently giving ~1% deviation from optimal solution, based on computational experiment on various distribution pattern of required staffing level with increasing complexity and problem size.