Exact and Heuristic Approaches for Weighted Throughput Maximization in Single-Machine Scheduling
Mathematics · 18.04.2026 · 14 (8) · 1366
DOI: 10.3390/math14081366 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 18.04.2026. Verfasst von Yi-Feng Hung und 3 weiteren Autor:innen. Die Arbeit nennt 50 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
This study investigates a single-machine throughput maximization problem (TMP), in which each job is characterized by a processing time, ready date, due date, and weight, and must be completed within its time window to yield profit. The objective is to select and schedule a subset of jobs to maximize the total weight of completed jobs. While existing studies primarily focus on special cases or heuristic approaches, this paper develops a unified exact solution framework for the general TMP. The main contribution is a job-sorting-based approach in which dominance rules are derived from structural properties induced by a partial ordering, while a complete ordering based on time-window midpoints is used to guide job sequencing. Based on this framework, several solution approaches are developed, including implicit enumeration (IE) methods, branch-and-bound (B&B) methods enhanced with linear programming (LP) relaxation, and a mixed-integer programming (MIP) model. A heuristic method is also proposed to generate high-quality initial solutions that accelerate exact methods. Computational experiments are conducted on a comprehensive set of instances. The results demonstrate that the proposed job sorting and dominance rules significantly improve computational efficiency, leading to substantial reductions in solution time compared with baseline methods.
Zitieren
APA
Hung, Y., Lin, J., Lai, C., & Chien, C. (2026). Exact and Heuristic Approaches for Weighted Throughput Maximization in Single-Machine Scheduling. Mathematics, 14(8), 1366. https://doi.org/10.3390/math14081366
Vancouver
Hung Y, Lin J, Lai C, Chien C. Exact and Heuristic Approaches for Weighted Throughput Maximization in Single-Machine Scheduling. Mathematics. 2026;14(8):1366. doi:10.3390/math14081366
BibTeX
@article{Hung2026,
author = {Hung, Yi-Feng and Lin, Jia-Shain and Lai, Chih-Hao and Chien, Chia-Hui},
title = {Exact and Heuristic Approaches for Weighted Throughput Maximization in Single-Machine Scheduling},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {8},
pages = {1366},
doi = {10.3390/math14081366}
}
EUVIMED