Note—On Baluts Algorithm and NP-Completeness for a Chance-Constrained Scheduling Problem
指出Balut在1973年提出的解决单机随机加工时间调度问题的算法存在反例，并证明该问题是NP完全的，对调度算法研究者有参考价值。
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.