A heuristic neighbourhood search-based algorithm for the solution of resource-task network scheduling problems

Giancarlo Dalle Ave, Xing Wang, Iiro Harjunkoski, Sebastian Engell

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication28th European Symposium on Computer Aided Process Engineering
PublisherElsevier
Pages907-912
Number of pages6
ISBN (Print)9780444642356
DOIs
Publication statusPublished - 2 Jul 2018
MoE publication typeA3 Part of a book or another research book

Publication series

NameComputer Aided Chemical Engineering
Volume43
ISSN (Print)1570-7946

Keywords

  • Heuristic
  • Iterative scheduling algorithm
  • Neighbourhood search
  • Resource-task network (RTN)

Fingerprint Dive into the research topics of 'A heuristic neighbourhood search-based algorithm for the solution of resource-task network scheduling problems'. Together they form a unique fingerprint.

Cite this