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

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.

MoreLess

Year of publication:	1983
Authors:	Kise, Hiroshi ; Ibaraki, Toshihide
Published in:	Management Science. - Institute for Operations Research and the Management Sciences - INFORMS, ISSN 0025-1909. - Vol. 29.1983, 3, p. 384-388
Publisher:	Institute for Operations Research and the Management Sciences - INFORMS
Subject:	production/scheduling: job shop \| stochastic

More details

Extent:	application/pdf
Type of publication:	Article
Other identifiers:	10.1287/mnsc.29.3.384 [DOI]
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10009208800