2 citations · 5 across the 18 of their papers we have counts for
21 papers
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…
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…
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…
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…
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…
Faster Minimization of Total Weighted Completion Time on Parallel Machines
Danny Hermelin, Tomohiro Koana, Dvir Shabtay
We study the classical problem of minimizing the total weighted completion time on a fixed set of identical machines working in parallel, the problem in the s…
Fair Repetitive Interval Scheduling
Klaus Heeger, Danny Hermelin, Yuval Itzhaki +2
Fair resource allocation is undoubtedly a crucial factor in customer satisfaction in several scheduling scenarios. This is especially apparent in repetitive scheduling models where…
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…
No Polynomial Kernels for Knapsack
Klaus Heeger, Danny Hermelin, Matthias Mnich +1
This paper focuses on kernelization algorithms for the fundamental Knapsack problem. A kernelization algorithm (or kernel) is a polynomial-time reduction from a problem onto itself…
Hardness of Interval Scheduling on Unrelated Machines
Danny Hermelin, Yuval Itzhaki, Hendrik Molter +1
We provide new (parameterized) computational hardness results for Interval Scheduling on Unrelated Machines. It is a classical scheduling problem motivated from just-in-time or lea…
Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions
Danny Hermelin, Hendrik Molter, Dvir Shabtay
The problem asks to determine -- given jobs each with its own processing time, weight, and due date -- the minimum weighted number of tardy jobs in any s…
Fairness in Repetitive Scheduling
Danny Hermelin, Hendrik Molter, Rolf Niedermeier +2
Recent research found that fairness plays a key role in customer satisfaction. Therefore, many manufacturing and services industries have become aware of the need to treat customer…
Equitable Scheduling on a Single Machine
Klaus Heeger, Danny Hermelin, George B. Mertzios +3
We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalizati…
Scheduling Lower Bounds via AND Subset Sum
Amir Abboud, Karl Bringmann, Danny Hermelin +1
Given instances of Subset Sum, the AND Subset Sum problem asks to determine whether all of these instances are yes-instances; that is, whether each…
Faster Minimization of Tardy Processing Time on a Single Machine
Karl Bringmann, Nick Fischer, Danny Hermelin +2
This paper is concerned with the problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental sch…
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…
On The Parameterized Tractability of the Just-In-Time Flow-Shop Scheduling Problem
Danny Hermelin, Dvir Shabtay, Nimrod Talmon
Since its development in the early 90's, parameterized complexity has been widely used to analyze the tractability of many NP-hard combinatorial optimization problems with respect…
Scheduling Two Agents on a Single Machine: A Parameterized Analysis of NP-hard Problems
Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay +2
Scheduling theory is an old and well-established area in combinatorial optimization, whereas the much younger area of parameterized complexity has only recently gained the attentio…
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
Amir Abboud, Karl Bringmann, Danny Hermelin +1
Subset-Sum and k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexit…