Open AccessNote—On Baluts Algorithm and NP-Completeness for a Chance-Constrained Scheduling Problem
Author(s) -
Hiroshi Kise,
Toshihide Ibaraki
Publication year - 1983
Publication title -
management science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 4.954
H-Index - 255
eISSN - 1526-5501
pISSN - 0025-1909
DOI - 10.1287/mnsc.29.3.384
Subject(s) - mathematical optimization , computer science , job shop scheduling , scheduling (production processes) , certainty , schedule , algorithm , mathematics , geometry , operating system
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.production/scheduling: job shop, stochastic