3 papers
cs.DS2026
Approximate Total Weighted Completion Time with Convex Controllable Processing Times
Klaus Heeger, Danny Hermelin, Dvir Shabtay
We study the single-machine scheduling problem with controllable processing times to minimize the total weighted completion time, focusing on the setting where a job's processing t…
cs.DM2026
Scheduling Tasks towards Energy Autarky: Benefits and Computational Costs of Flexibility
Robert Bredereck, Till Fluschnik, Klaus Heeger
We study the autarky problem: given an energy forecast, a battery, and a set of energy-consuming jobs with time windows, decide whether all jobs can be scheduled without requiring…
cs.DS2025
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…