Phase transitions in project scheduling
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 tran...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
1999
|
| Subjects: | |
| 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 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | 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 |
|---|