An efficient polynomial time algorithm for the problem of scheduling n unit length jobs with rational release times and deadlines on m identical parallel machines is presented. By using preprocessing, a running time of O(mn² ) is obtained that is an improvement over the previous best running time of O(n³ log log n). The authors also present new NP-completeness results for two closely related problems.
No takes yet. Share an insight, caveat, or question.
Sımons et al. (1989) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: