6533b86efe1ef96bd12cb1fa

RESEARCH PRODUCT

A graph colouring model for assigning a heterogeneous workforce to a given schedule

Sacramento QuintanillaÁNgeles PérezVicente Valls

subject

Vertex (graph theory)Mathematical optimizationScheduleInformation Systems and ManagementGeneral Computer ScienceBranch and boundManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringModeling and SimulationGraph (abstract data type)Resource allocationBranch and cutAssignment problemWeapon target assignment problemMathematics

description

Abstract 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 to 15 different types of workers in just a few seconds.

yearjournalcountryeditionlanguage
1996-04-01European Journal of Operational Research
https://doi.org/10.1016/0377-2217(95)00355-x