Publication Type

Journal Article

Version

publishedVersion

Publication Date

1-1999

Abstract

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

Keywords

phase transitions, project management, scheduling

Discipline

Business Administration, Management, and Operations | Operations and Supply Chain Management

Research Areas

Operations Management

Publication

Journal of the Operational Research Society

Volume

50

Issue

2

First Page

148

Last Page

156

ISSN

0160-5682

Identifier

10.1057/palgrave.jors.2600680

Publisher

Taylor & Francis: STM, Behavioural Science and Public Health Titles

Embargo Period

8-31-2021

External URL

https://doi.org/10.1057/palgrave.jors.2600680

Download

Share

COinS