A Multiperiod Workforce Scheduling and Routing Problem with Dependent Tasks

• URL: http://arxiv.org/abs/2008.02849v1
• Date: Thu, 6 Aug 2020 19:31:55 GMT
• Title: A Multiperiod Workforce Scheduling and Routing Problem with Dependent Tasks
• Authors: Dilson Lucas Pereira, J\'ulio C\'esar Alves, Mayron C\'esar de Oliveira Moreira
• Abstract summary: We study a new Workforce Scheduling and Routing Problem. In this problem, customers request services from a company. Tasks belonging to a service may be executed by different teams, and customers may be visited more than once a day.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  Coalition structure generation is a fundamental computational problem in multiagent systems. We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
  arXiv  Detail & Related papers  (2025-02-14T15:21:27Z)
• Comprehensive Benchmarking Environment for Worker Flexibility in Flexible Job Shop Scheduling Problems [0.0]
  In Production Scheduling, the Flexible Job Shop Scheduling Problem (FJSSP) aims to optimize a sequence of operations and assign each to an eligible machine with varying processing times. The resulting problem is called Flexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W) This paper presents a collection of 402 commonly accepted FJSSP instances and proposes an approach to extend these with worker flexibility.
  arXiv  Detail & Related papers  (2025-01-27T15:56:12Z)
• Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems [5.896440476510869]
  Assignment problems are a classic optimization problem in which a group of agents is assigned to a group of tasks. In many modern-day applications such as satellite, power grids, and mobile robot scheduling, assignment problems unfold over time. We apply multi-agent reinforcement learning to this problem, learning the value of assignments by bootstrapping from a known RL-time greedy solver. We demonstrate that our algorithm is theoretically justified and avoids pitfalls experienced by other algorithms in this setting.
  arXiv  Detail & Related papers  (2024-12-20T05:10:34Z)
• Reinforcement Learning with Success Induced Task Prioritization [68.8204255655161]
  We introduce Success Induced Task Prioritization (SITP), a framework for automatic curriculum learning. The algorithm selects the order of tasks that provide the fastest learning for agents. We demonstrate that SITP matches or surpasses the results of other curriculum design methods.
  arXiv  Detail & Related papers  (2022-12-30T12:32:43Z)
• Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling [7.977161233209228]
  Job-shop Scheduling Problem (JSP) is a well-known and challenging optimization problem in which tasks sharing a machine are to be arranged in a sequence such that encompassing jobs can be completed as early as possible. In this paper, we investigate problem decomposition into time windows whose operations can be successively scheduled and optimized by means of multi-shot Answer Set Programming (ASP) solving.
  arXiv  Detail & Related papers  (2022-05-16T09:33:00Z)
• Task Adaptive Parameter Sharing for Multi-Task Learning [114.80350786535952]
  Adaptive Task Adapting Sharing (TAPS) is a method for tuning a base model to a new task by adaptively modifying a small, task-specific subset of layers. Compared to other methods, TAPS retains high accuracy on downstream tasks while introducing few task-specific parameters. We evaluate our method on a suite of fine-tuning tasks and architectures (ResNet, DenseNet, ViT) and show that it achieves state-of-the-art performance while being simple to implement.
  arXiv  Detail & Related papers  (2022-03-30T23:16:07Z)
• Efficiently Identifying Task Groupings for Multi-Task Learning [55.80489920205404]
  Multi-task learning can leverage information learned by one task to benefit the training of other tasks. We suggest an approach to select which tasks should train together in multi-task learning models. Our method determines task groupings in a single training run by co-training all tasks together and quantifying the effect to which one task's gradient would affect another task's loss.
  arXiv  Detail & Related papers  (2021-09-10T02:01:43Z)
• Elastic Architecture Search for Diverse Tasks with Different Resources [87.23061200971912]
  We study a new challenging problem of efficient deployment for diverse tasks with different resources, where the resource constraint and task of interest corresponding to a group of classes are dynamically specified at testing time. Previous NAS approaches seek to design architectures for all classes simultaneously, which may not be optimal for some individual tasks. We present a novel and general framework, called Elastic Architecture Search (EAS), permitting instant specializations at runtime for diverse tasks with various resource constraints.
  arXiv  Detail & Related papers  (2021-08-03T00:54:27Z)
• Reinforcement Learning for Assignment Problem with Time Constraints [0.0]
  We present an end-to-end framework for the Assignment Problem with multiple tasks mapped to a group of workers. We train a reinforcement learning agent to find near optimal solutions to the problem by minimizing total cost associated with the assignments. We also demonstrate our results on bin packing and capacitated vehicle routing problem, using the same framework.
  arXiv  Detail & Related papers  (2021-06-05T10:10:52Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.