  In this paper, we study a new Workforce Scheduling and Routing Problem,
denoted Multiperiod Workforce Scheduling and Routing Problem with Dependent
Tasks. In this problem, customers request services from a company. Each service
is composed of dependent tasks, which are executed by teams of varying skills
along one or more days. Tasks belonging to a service may be executed by
different teams, and customers may be visited more than once a day, as long as
precedences are not violated. The objective is to schedule and route teams so
that the makespan is minimized, i.e., all services are completed in the minimum
number of days. In order to solve this problem, we propose a Mixed-Integer
Programming model, a constructive algorithm and heuristic algorithms based on
the Ant Colony Optimization (ACO) metaheuristic. The presence of precedence
constraints makes it difficult to develop efficient local search algorithms.
This motivates the choice of the ACO metaheuristic, which is effective in
guiding the construction process towards good solutions. Computational results
show that the model is capable of consistently solving problems with up to
about 20 customers and 60 tasks. In most cases, the best performing ACO
algorithm was able to match the best solution provided by the model in a
fraction of its computational time.
