Article ID: | iaor19996 |
Country: | Netherlands |
Volume: | 90 |
Issue: | 2 |
Start Page Number: | 285 |
End Page Number: | 302 |
Publication Date: | Apr 1996 |
Journal: | European Journal of Operational Research |
Authors: | Valls Vicente, Prez Angeles, Quintanilla Sacramento |
Keywords: | scheduling, personnel & manpower planning, graphs |
We analyze a heterogeneous workforce assignment problem in which the minimum number of workers required to carry out a machine load plan is calculated. The problem is formulated as a restricted vertex colouring problem and a branch and bound algorithm is presented. The special characteristics of the graph to be coloured allow an efficient implementation of the branch and bound. Computational results show that the algorithm can solve problems of 50 activities, 5, 10 and 15 machines and between 2 and 15 different types of workers in just a few seconds.