Publications

You can also find my articles on my Google Scholar profile.

Journal Articles

Just-in-Time Scheduling in Two-Stage Flexible Flow Shops

Published in European Journal of Operational Research (EJOR), In Press., 2026

We study the two-stage flexible flow shop problem with a just-in-time objective, proving strong NP-hardness for the unweighted case and developing pseudo-polynomial, parameterized, and approximation algorithms for several structural settings.

Recommended citation: Heeger, K., Hermelin, D., Itzhaki, Y., Schieber, B., and Shabtay, D. (2026). Just-in-Time Scheduling in Two-Stage Flexible Flow Shops. European Journal of Operational Research.
Download Paper | Download Slides | Download Bibtex

Fair Repetitive Interval Scheduling

Published in Algorithmica, Volume 87, pages 1340–1368, 2025

We study fair repetitive interval scheduling, showing NP-hardness under natural restrictions and providing algorithmic and parameterized results for several tractable cases.

Recommended citation: Heeger, K., Hermelin, D., Itzhaki, Y., Molter, H. and Shabtay, D., 2025. Fair Repetitive Interval Scheduling. Algorithmica, 87, pp. 1340–1368.
Download Paper | Download Slides | Download Bibtex

On the parameterized complexity of interval scheduling with eligible machine sets

Published in Journal of Computer and System Sciences, Volume 144, p.103533., 2024

We show W[1]-hardness for the number of machines \(m\) in Interval Scheduling with Eligible Machines, prove NP-hardness for bounded \(p_{\max}\), and give an FPT algorithm for the combined parameter \(p_{\max} + m\).

Recommended citation: Hermelin, D., Itzhaki, Y., Molter, H. and Shabtay, D., 2024. On the parameterized complexity of interval scheduling with eligible machine sets. Journal of Computer and System Sciences, 144, p.103533.
Download Paper | Download Slides | Download Bibtex

Temporal interval cliques and independent sets

Published in Theoretical Computer Science, Volume 961, p.113885., 2023

We give hardness, approximation, and parameterized results for Temporal Clique and Temporal Independent Set on temporal interval graphs.

Recommended citation: Hermelin, D., Itzhaki, Y., Molter, H. and Niedermeier, R., 2023. Temporal interval cliques and independent sets. Theoretical Computer Science, 961, p.113885.
Download Paper | Download Bibtex

Conference Papers

Hardness of Interval Scheduling on Unrelated Machines

Published in 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), 2022

Hardness results for Interval Scheduling on Unrelated Machines, including W[1]-hardness in the machine parameter and NP-completeness of the unweighted case.

Recommended citation: Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Dvir Shabtay. Hardness of Interval Scheduling on Unrelated Machines. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Download Paper | Download Bibtex

Temporal Unit Interval Independent Sets

Published in 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), 2022

We study the complexity of finding large independent sets in temporal unit interval graphs, and obtain hardness, constant-factor approximation, and fixed-parameter tractability results.

Recommended citation: Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Rolf Niedermeier. Temporal Unit Interval Independent Sets. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Download Paper | Download Slides | Download Bibtex