3 papers
cs.DS2026
New Complexity Results for Fair Repetitive Scheduling
Moran Koren, Michael L. Pinedo, Dvir Shabtay
We revisit the problem of finding fair solutions to repetitive scheduling problems with a single machine. In this problem, we are given a set of clients and a planning horizon…
cs.DS2024
Minimizing the Number of Tardy Jobs and Maximal Tardiness on a Single Machine is NP-hard
Klaus Heeger, Danny Hermelin, Michael L. Pinedo +1
This paper resolves a long-standing open question in bicriteria scheduling regarding the complexity of a single machine scheduling problem which combines the number of tardy jobs a…
cs.DS2017
New Algorithms for Minimizing the Weighted Number of Tardy Jobs On a Single Machine
Danny Hermelin, Shlomo Karhi, Mike Pinedo +1
In this paper we study the classical single machine scheduling problem where the objective is to minimize the total weight of tardy jobs. Our analysis focuses on the case where one…