Single‐Machine Scheduling to Minimize the Size of Input Buffer
Naval Research Logistics (NRL) · 2025-09 · 72 (6) · 810-824
DOI: 10.1002/nav.22256 ↗Kurz gefasst
Fachartikel in der Zeitschrift Naval Research Logistics (NRL), online erschienen am 19.02.2025. Verfasst von Shunji Tanaka und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 18 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).
Abstract (Originalsprache)
This paper investigates a single‐machine scheduling problem with a finite‐capacity input buffer. In this problem, each job is assigned to the machine at its release date and started immediately or sent to the input buffer to wait for processing. The problem in this study is to find a schedule that minimizes the required size of the input buffer. Its strong NP‐hardness will be shown first, and next, a pseudo‐polynomial time dynamic program will be developed for another ordinary NP‐hard case. Three mixed integer linear programming models are presented using different formulation approaches. We also design four heuristic algorithms to produce approximate solutions in a reasonable time. Numerical experiments appraise the effectiveness of the formulations.
Zitieren
APA
Tanaka, S., & Lin, B. M. T. (2025). Single‐Machine Scheduling to Minimize the Size of Input Buffer. Naval Research Logistics (NRL), 72(6), 810-824. https://doi.org/10.1002/nav.22256
Vancouver
Tanaka S, Lin BMT. Single‐Machine Scheduling to Minimize the Size of Input Buffer. Naval Research Logistics (NRL). 2025;72(6):810-824. doi:10.1002/nav.22256
BibTeX
@article{Tanaka2025,
author = {Tanaka, Shunji and Lin, Bertrand M. T.},
title = {Single‐Machine Scheduling to Minimize the Size of Input Buffer},
journal = {Naval Research Logistics (NRL)},
year = {2025},
volume = {72},
number = {6},
pages = {810--824},
doi = {10.1002/nav.22256}
}
EUVIMED