Scheduling and the problem of computational complexity

King, JR

Omega, 1979, vol. 7, issue 3, 233-240

Abstract: Why is it that the problem of scheduling is so computationally difficult to solve? At last recent developments in modern mathematical complexity theory are providing some insights. The paper describes in essentially non-mathematical terms the computational technique known as the 'Branch and Bound Method'. This, the best general optimising technique available for scheduling, is also shown to have its limitations. It now appears that efficient computational and optimising algorithms are unlikely ever to be found for all except special cases of the general industrial scheduling problem. It seems that heuristic (rule-of-thumb) methods leading to approximate solutions are likely to offer the only real promise for the future.

Date: 1979
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/0305-0483(79)90058-6
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:7:y:1979:i:3:p:233-240

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().