DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2025.5

Throughput Maximization in a Scheduling Environment with Machine-Dependent Due-Dates

Authors: Shaul Rosner and Tami Tamir

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract

We consider a scheduling environment in which jobs are associated with machine-dependent due-dates. This natural setting arises in systems where clients' tolerance depends on the service provider. The objective is to maximize throughput, defined as the number of non-tardy jobs. The problem exhibits significant differences from previously studied scheduling models. We analyze its computational complexity both in general and for the special case of unit-length jobs. In the unit-length setting, we provide an optimal algorithm that also extends to cases with machine-dependent release times and machine-dependent weights (i.e., rewards depending on the machine that completes the job). For jobs with different lengths, we show that even the unweighted problem without release times, with only two different lengths, specifically, for all j, p_j ∈ {1,2}, is APX-hard. To isolate the role of machine-dependent due-dates in this hardness result, we present an optimal algorithm for the case where all p_j ∈ {1,2} and due-dates are not machine-dependent. This algorithm further extends to instances with a constant number of integer processing times.

Cite as

Shaul Rosner and Tami Tamir. Throughput Maximization in a Scheduling Environment with Machine-Dependent Due-Dates. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rosner_et_al:OASIcs.ATMOS.2025.5,
  author =	{Rosner, Shaul and Tamir, Tami},
  title =	{{Throughput Maximization in a Scheduling Environment with Machine-Dependent Due-Dates}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{5:1--5:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.5},
  URN =		{urn:nbn:de:0030-drops-247616},
  doi =		{10.4230/OASIcs.ATMOS.2025.5},
  annote =	{Keywords: Scheduling, Throughput maximization, Machine-dependent due-dates, Computational Complexity}
}

Search Results

Documents authored by Rosner, Shaul

Throughput Maximization in a Scheduling Environment with Machine-Dependent Due-Dates

Abstract

Cite as

Thanks for your feedback!

Could not send message