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.