A Multiperiod Workforce Scheduling and Routing Problem with Dependent Tasks
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.
Code (1)
Tasks
SchedulingSimilar Papers 제목 키워드 기반
Optimisation and Illumination of a Real-world Workforce Scheduling and Routing Application via Map-Elites
Workforce Scheduling and Routing Problems (WSRP) are very common in many practical domains, and usually, have a number of objectives. Illumination algorithms such as Map-Elites (ME) have recently gained traction in appli…
SchedulingEnhanced Iterated local search for the technician routing and scheduling problem
Most public facilities in the European countries, including France, Germany, and the UK, were built during the reconstruction projects between 1950 and 1980. Owing to the deteriorating state of such vital infrastructure …
SchedulingA Multi-Objective Genetic Algorithm for Healthcare Workforce Scheduling
Workforce scheduling in the healthcare sector is a significant operational challenge, characterized by fluctuating patient loads, diverse clinical skills, and the critical need to control labor costs while upholding high…
A Two-Phase Safe Vehicle Routing and Scheduling Problem: Formulations and Solution Algorithms
We propose a two phase time dependent vehicle routing and scheduling optimization model that identifies the safest routes, as a substitute for the classical objectives given in the literature such as shortest distance or…
ARCSchedulingSchool bus routing by maximizing trip compatibility
School bus planning is usually divided into routing and scheduling due to the complexity of solving them concurrently. However, the separation between these two steps may lead to worse solutions with higher overall costs…
BlockingScheduling