Note---On Baluts Algorithm and NP-Completeness for a Chance-Constrained Scheduling Problem

Hiroshi Kise and Toshihide Ibaraki
Additional contact information
Hiroshi Kise: Kyoto Institute of Technology
Toshihide Ibaraki: Kyoto University

Management Science, 1983, vol. 29, issue 3, 384-388

Abstract: In 1973, Balut gave an algorithm to solve an n-job one machine scheduling problem in which processing times are random variables and the objective is to minimize the number of tardy jobs with a specified certainty level. This note, however, presents an example for which his algorithm fails to give an optimal schedule. Furthermore, there does not seem to exist any such efficient algorithm because the problem can be shown to be NP-complete.

Keywords: production/scheduling: job shop; stochastic (search for similar items in EconPapers)
Date: 1983
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.29.3.384 (application/pdf)

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:inm:ormnsc:v:29:y:1983:i:3:p:384-388

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().