A novel priority rule heuristic: learning from justification

Frits De Nijs, Tomas Klos

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

The Resource Constrained Project Scheduling Problem consists of finding start times for precedence-constrained activities which compete over renewable resources, with the goal to produce the shortest schedule. The method of Justification is a very popular post-processing schedule optimization technique which, although it is not clear exactly why, has been shown to work very well, even improving randomly generated schedules over those produced by advanced heuristics. In this paper, we set out to investigate why Justification works so well, and, with this understanding, to bypass the need for Justification by computing a priori the priorities Justification implicitly employs. We perform an exploratory study to investigate the effectiveness of Justification on a novel test set which varies the RCPSP phase-transition parameters across a larger range than existing test sets. We propose several hypotheses to explain the behavior of Justification, which we test by deriving from them several predictions, and a new priority rule. We show that this rule matches the priorities used by Justification more closely than existing rules, making it outperform the most successful priority rule heuristic.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling
Subtitle of host publicationPortsmouth, New Hampshire USA, June 21–26, 2014
EditorsSteve Chien, Minh Do, Alan Fern, Wheeler Ruml
Place of PublicationPalo Alto California USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages92-100
Number of pages9
ISBN (Print)9781577356608
Publication statusPublished - 2014
Externally publishedYes
EventInternational Conference on Automated Planning and Scheduling 2014 - Sheraton Harborside Hotel, Portsmouth, United States of America
Duration: 21 Jun 201426 Jun 2014
Conference number: 24th
http://icaps14.icaps-conference.org/
https://dl.acm.org/doi/book/10.5555/2683899 (Proceedings)

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
PublisherAAAI Press
ISSN (Print)2334-0835

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2014
Abbreviated titleICAPS 2014
CountryUnited States of America
CityPortsmouth
Period21/06/1426/06/14
Internet address

Keywords

  • Resource constrained project scheduling problem (RCPSP)
  • Empirical evaluation of algorithms
  • Scheduling algorithms

Cite this