EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3873. An exact solution for the energy constrained AGV scheduling problem
Invited abstract in session MB-26: Novel topics and recent advances in solution approaches in scheduling, stream Combinatorial Optimization.
Monday, 10:30-12:00Room: 012 (building: 208)
Authors (first author is the speaker)
| 1. | Amir Hosseini
|
| University of Passau | |
| 2. | Alena Otto
|
| Technical University of Munich |
Abstract
Automated Guided Vehicles (AGVs) play a pivotal role in modern transportation systems, revolutionizing the movement of goods and materials in warehouses and production systems. Yet, exploiting the performance of AGVs requires careful consideration of their operational constraints during the planning phase. In this study we consider the AGVs scheduling problem, where a fleet of AGVs are used to perform a set of transport requests. The AGVs are energy constrained and their battery needs to be swapped regularly. The problem is to assign transport activities to AGVs, sequence them, and determine optimal battery swap times, such that the makespan is minimized. In essence, this problem can also be viewed as a parallel machine scheduling problem with job-dependent activity cycles and constant maintenance time.
For this problem, we introduce a novel mixed-integer linear programming formulation that surpasses existing state-of-the-art models. Then, we develop a logic-based Benders decomposition algorithm embedded in a single search tree framework and strengthened by new sets of lower bounds and valid inequalities. Preliminary computational results indicate the algorithm's capability to solve previously unsolved instances reported in the literature.
Keywords
- Scheduling
- Branch and Cut
- Combinatorial Optimization
Status: accepted
Back to the list of papers