Phase transitions in project scheduling

• Main Authors: HERROELEN, Willy, DE REYCK, Bert
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 1999
• Subjects: phase transitions; project management; scheduling; Business Administration, Management, and Operations; Operations and Supply Chain Management
• Online Access: https://ink.library.smu.edu.sg/lkcsb_research/6744; https://ink.library.smu.edu.sg/context/lkcsb_research/article/7761/viewcontent/Phase_transitions_in_project_scheduling.pdf
• Institution: Singapore Management University

Researchers in the area of artificial intelligence have recently shown that many NP-complete problems exhibit phase transitions. Often, problem instances change from being easy to being hard to solve to again being easy to solve when certain of their characteristics are modified. Most often the transitions are sharp, but sometimes they are rather continuous in the order parameters that are characteristic of the system as a whole. To the best of our knowledge, no evidence has been provided so far that similar phase transitions occur in NP-hard scheduling problems. In this paper we report on the existence of phase transitions in various resource-constrained project scheduling problems. We discuss the use of network complexity measures and resource parameters as potential order parameters. We show that while the network complexity measures seem to reveal continuous easy-ha