Dmitriy Katz-Rogozhnikov, Baruch Schieber, et al.
Algorithmica
We study the scheduling situation where n tasks, subjected to release dates and due dates, have to be scheduled on m parallel processors. We show that, when tasks have unit processing times and either require 1 or m processors simultaneously, the minimum maximal tardiness can be computed in polynomial time. Two algorithms are described. The first one is based on a linear programming formulation of the problem while the second one is a combinatorial algorithm. The complexity status of this "tall/small" task scheduling problem P|r i,p i = 1, size i ∈ {1, m}|T max was unknown before, even for two processors.
Dmitriy Katz-Rogozhnikov, Baruch Schieber, et al.
Algorithmica
Bing Zhang, Mikio Takeuchi, et al.
NAACL 2025
Aditya Malik, Nalini Ratha, et al.
CAI 2024
Joseph Y. Halpern
aaai 1996