Shreyas Ghildiyal

Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation

In classical fixed-interval scheduling, each job of a given set must be processed during a prescribed time interval. The goal is to assign each job to exactly one machine such that no two jobs assigned to the same machine overlap in their interiors, and the number of machines used is minimized. Without further constrai...