Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
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(mn2) is obtained that is an improvement over the previous best running time of O(n3 log log n). The authors also present new NP completeness results for two closely related problems.
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
Marshall W. Bern, Howard J. Karloff, et al.
Theoretical Computer Science