Metraipolis › archive › dc_4e4b6c5ed294

An Exact Combinatorial Branch-and-Bound Algorithm for the Job Sequencing and Tool Switching Problem — arXiv:2609.03219

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.03219
License (as archived)
CC0-1.0
Archived
2026-10-17T02:26:43.140Z
SHA-256 of the archived text
0b8ed58f8cd142f6a7e267cf3ff503b4d1139cff25c1abd40f6c12fc09ba9cb4
Stable URL of this page
https://metraipolis.com/documento/dc_4e4b6c5ed294

How to cite

An Exact Combinatorial Branch-and-Bound Algorithm for the Job Sequencing and Tool Switching Problem — arXiv:2609.03219 — arXiv (en), https://arxiv.org/abs/2609.03219 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4e4b6c5ed294 (Metraipolis archive dc_4e4b6c5ed294, sha256 0b8ed58f8cd142f6a7e267cf3ff503b4d1139cff25c1abd40f6c12fc09ba9cb4)
BibTeX
@misc{dc4e4b6c5ed294,
  title = {An Exact Combinatorial Branch-and-Bound Algorithm for the Job Sequencing and Tool Switching Problem — arXiv:2609.03219},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.03219},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4e4b6c5ed294; sha256 0b8ed58f8cd142f6a7e267cf3ff503b4d1139cff25c1abd40f6c12fc09ba9cb4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.03219. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Job Sequencing and Tool Switching Problem (SSP) is a well-known combinatorial optimization problem arising in the context of flexible manufacturing. Since the seminal work of Tang and Denardo (1988), the SSP has received significant attention in the literature, leading to the development of numerous exact and heuristic approaches. Despite these efforts, several benchmark instances proposed decades ago and containing only 20 jobs have remained unsolved to proven optimality. In this work, we propose an exact algorithm for the SSP, namely the Combinatorial Branch-and-Bound (C-B\&B) algorithm, which combines two distinct branch-and-bound algorithms, each introducing novel features compared with the existing literature. The former relies on a new branching scheme designed to reduce the size of the implicit enumeration tree, together with a collection of new bounding functions. The latter builds on the branching scheme introduced by Laporte et al. (2004) and strengthens it with a new bounding function and two dominance rules. Within C-B\&B, these exact algorithms are complemented by a preprocessing phase that incorporates a new branch-and-bound-based heuristic capable of rapidly generating a high-quality initial incumbent solution. Extensive computational experiments show that C-B\&B represents a strong breakthrough over previously published approaches, proving optimality for more instances with significantly less computational effort and closing several benchmark instances that have remained open for decades.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-04 in math.OC).
Categorie arXiv: Optimization and Control (math.OC) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.03219 — 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-17T02:07:43.326Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).