Metraipolis › archive › dc_b71ba0371bbd
Serial-batch scheduling to minimise the total weighted late work — arXiv:2609.18046
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.18046
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T17:09:18.064Z
- SHA-256 of the archived text
136e72f180f819bd9e8db7900c7c0055b18d26b2a822a62be49b53b17f378c11- Stable URL of this page
https://metraipolis.com/documento/dc_b71ba0371bbd
How to cite
Serial-batch scheduling to minimise the total weighted late work — arXiv:2609.18046 — arXiv (en), https://arxiv.org/abs/2609.18046 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b71ba0371bbd (Metraipolis archive dc_b71ba0371bbd, sha256 136e72f180f819bd9e8db7900c7c0055b18d26b2a822a62be49b53b17f378c11)
BibTeX
@misc{dcb71ba0371bbd,
title = {Serial-batch scheduling to minimise the total weighted late work — arXiv:2609.18046},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.18046},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b71ba0371bbd; sha256 136e72f180f819bd9e8db7900c7c0055b18d26b2a822a62be49b53b17f378c11},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18046. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the problem of scheduling jobs on a serial-batch machine with the aim of minimising the total weighted late work. In a serial-batch setting, jobs within a batch are processed sequentially, and none are removed from the machine until the last job in the batch completes its processing. The processing time of a batch is the sum of the processing times of the jobs within it, and the completion time for each job in the batch is equal to the makespan of the jobs in the batch. When a new batch begins, a constant setup time is required for the machine. We show that minimising the total weighted late work in this environment is $NP$-hard even if all jobs have a common due date and unit weight. For the general problem, we present a pseudo-polynomial time dynamic programming algorithm. Additionally, we explore two special cases, i.e., one with a common due date and another with an agreeable condition among due dates, processing times and weights. For both special cases, we develop specialised pseudo-polynomial time dynamic programming algorithms. The proposed approaches are equipped with specialised acceleration techniques to enhance their computational performance. The extended experiments demonstrate that the dynamic programming algorithms outperform Gurobi in time efficiency. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.DS). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2609.18046 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-15T16:17:15.256Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).