Effective heuristic procedures for a field technician scheduling problem

This paper addresses a field technician scheduling problem faced by many se rvice providers in telecommunication industry. The problem is to assign a s et of jobs, at different locations with time windows, to a group of field t echnicians with different job skills. Such a problem can be viewed as a gen eralization of the well-known vehicle routing problem with time windows sin ce technician skills need to be matched with job types. We designed and tes ted several heuristic procedures for solving the problem, namely a greedy h euristic, a local search algorithm, and a greedy randomized adaptive search procedure (GRASP). Our computational results indicate that GRASP is the mo st effective among them but requires more CPU time. However, the unique str ucture of GRASP allows us to exploit parallelism to achieve linear speed-up with respect to the number of machines used.