8 papers
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…
Robust Permutation Flowshops Under Budgeted Uncertainty
Noam Goldberg, Danny Hermelin, Dvir Shabtay
We consider the robust permutation flowshop problem under the budgeted uncertainty model, where at most a given number of job processing times may deviate on each machine. We show…
Lawler-Moore Speedups via Additive Combinatorics
Karl Bringmann, Danny Hermelin, Tomohiro Koana +1
The Lawler-Moore dynamic programming framework is a classical tool in scheduling on parallel machines. It applies when the objective is regular, i.e. monotone in job completion tim…
Fast Makespan Minimization via Short ILPs
Danny Hermelin, Dvir Shabtay
Short integer linear programs are programs with a relatively small number of constraints. We show how recent improvements on the running-times of solvers for such programs can be u…
A Parametrized Complexity View on Robust Scheduling with Budgeted Uncertainty
Noam Goldberg, Dvir Shabtay
In this study, we investigate a robust single-machine scheduling problem under processing time uncertainty. The uncertainty is modeled using the budgeted approach, where each job h…
Approximation Algorithms for Fair Repetitive Scheduling
Danny Hermelin, Danny Segev, Dvir Shabtay
We consider a recently introduced fair repetitive scheduling problem involving a set of clients, each asking for their associated job to be daily scheduled on a single machine acro…