A heuristic neighbourhood search-based algorithm for the solution of resource-task network scheduling problems
| Main Authors: | Dalle Ave, Giancarlo, Wang, Xing, Harjunkoski, Iiro, Engell, Sebastian |
|---|---|
| Format: | Proceeding Journal |
| Terbitan: |
, 2018
|
| Subjects: | |
| Online Access: |
https://zenodo.org/record/1420941 |
Daftar Isi:
- There are many challenges facing the widespread industrial deployment of scheduling solutions. These include to find a generic scheduling model that can be applied to a broad variety of scenarios, and to design algorithms that can provide good quality solutions in industrially relevant time frames. The discrete-time Resource-Task Network (RTN) is a generic scheduling framework that has been successfully applied to many different problems. However, RTN models can quickly become intractable as problem size increases. In this work, an iterative neighbourhood-search based algorithm is developed in order to speed-up the solution of RTN scheduling models. The speedup is achieved by limiting the binary variables of a subproblem to a specific neighbourhood in a way that allows the algorithm to iteratively move towards better solutions. Results show that this approach is able to tackle problems that are intractable for a full-space model while still finding near-optimal solutions.