EUVIMEDEUVIMED entdecken
Crossref

Single Machine Scheduling of Coupled Task with Resource Consumption

Mingyu Ma, Junyi Zhang, Juan Zou

International Journal of Foundations of Computer Science · 14.05.2026 · 1-16

DOI: 10.1142/s0129054126490067 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Journal of Foundations of Computer Science, online erschienen am 14.05.2026. Verfasst von Mingyu Ma und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Gefördert von: Natural Science Foundation of Shandong Province.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We investigate coupled task scheduling problems under constrained resource availability on a single machine, which are of fundamental interest and already NP-hard even in this basic setting. In this model, every job [Formula: see text] comprises two tasks. Their processing times are distinct, and they are separated by a fixed time interval. For the second task, the job-specific processing time depends on the amount of resource allocated to it. The aim is to minimize the makespan or the total completion time, under the resource constraints. For the goal of minimizing the makespan, we develop a [Formula: see text]-approximation algorithm for the general case. Then we propose a 3-approximation algorithm for the special case where the time intervals are all equal. For the goal of minimizing the total completion time, we propose a 3-approximation algorithm when all time intervals are equal. Finally, we propose a 2-approximation algorithm when the processing time of the first task is equal to the time interval.

Förderung

  • Natural Science Foundation of Shandong Province

Zitieren

APA

Ma, M., Zhang, J., & Zou, J. (2026). Single Machine Scheduling of Coupled Task with Resource Consumption. International Journal of Foundations of Computer Science, 1-16. https://doi.org/10.1142/s0129054126490067

Vancouver

Ma M, Zhang J, Zou J. Single Machine Scheduling of Coupled Task with Resource Consumption. International Journal of Foundations of Computer Science. 2026:1-16. doi:10.1142/s0129054126490067

BibTeX
@article{Ma2026,
  author = {Ma, Mingyu and Zhang, Junyi and Zou, Juan},
  title = {Single Machine Scheduling of Coupled Task with Resource Consumption},
  journal = {International Journal of Foundations of Computer Science},
  year = {2026},
  pages = {1--16},
  doi = {10.1142/s0129054126490067}
}
Kostenlos starten →