An O(n2.logn) algorithm for a nonpreemptive schedule on one machine

Trịnh Nhật Tiến


An O(n2) algorithm for problem 1| rj | ∑Uj in the case that release dates and due dates are similarly ordered (i.e., rj < rk => dj ≤ dk) is provided by authors H. Kise, T. Ibaraki and H. Mine in [4]. In this paper, we would describe an O(n2.logn) algorithm to determine a schedule of the same problem but furthermore in minimal processing time.


Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology