Minimizing Tardiness in a Scheduling Environment with Jobs' Hierarchy

In many scheduling environments, some jobs have higher priority than others. We consider a new model, motivated by real-life behavior, in which the priority among jobs is defined by a dominance hierarchy. Specifically, the jobs are arranged in hierarchy levels, and high ranking jobs are ready to accept only outcomes in which the service they receive is better than the service of subordinate jobs. We define the model and the set of feasible schedules formally, and provide algorithms and hardness proofs for two classical problems: minimizing the maximal tardiness and minimizing the number of tardy jobs. We provide optimal algorithms or hardness proofs for these problems, distinguishing between a global objective function and a multi-criteria objective.

---

1. Track 1: Artificial Intelligence in Applications

---

2. Session: 14th International Workshop on Computational Optimization