An O(n 2 ) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness |
| |
| Authors: | Zhongjun Tian C. T. Ng T. C. E. Cheng |
| |
| Affiliation: | (1) John M. Olin School of Business, Washington University, St. Louis, Missouri, 63130;(2) Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong |
| |
| Abstract: | In this paper, we study the problem of scheduling n equal-length preemptive jobs on a single machine to minimize total tardiness, subject to release dates. The complexity status of this problem has remained open to date. We provide an O(n2) time algorithm to solve the problem. |
| |
| Keywords: | Single machine Preemptive scheduling Release date Equal-length jobs Total tardiness |
| 本文献已被 SpringerLink 等数据库收录！ |
|
