Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.20611 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913986212003840 |
|---|---|
| author | Leib, Dominik Heller, Till Kühn, Raphael |
| author_facet | Leib, Dominik Heller, Till Kühn, Raphael |
| contents | We study a single-machine scheduling problem with sequence dependent setup times, motivated by applications in manufacturing and service industries - in particular, the calendering stage in rubber flooring production. In this phase, setup times are primarily driven by temperature and color transitions between consecutive jobs, with significant impact on throughput and energy efficiency. We present a novel solution framework that transforms the scheduling problem into a path-finding problem on a specially constructed layered graph. By encoding sequence-dependent effects directly into the graph's structure, we enable the use of classical shortest-path algorithms to compute optimal job sequences. The resulting method is polynomial-time solvable for the two-color case and reveals key structural properties of optimal schedules. Our approach thus provides both a theoretically grounded and practically applicable optimization technique. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20611 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computing an optimal single machine schedule with sequence dependent setup times using shortest path computations Leib, Dominik Heller, Till Kühn, Raphael Optimization and Control We study a single-machine scheduling problem with sequence dependent setup times, motivated by applications in manufacturing and service industries - in particular, the calendering stage in rubber flooring production. In this phase, setup times are primarily driven by temperature and color transitions between consecutive jobs, with significant impact on throughput and energy efficiency. We present a novel solution framework that transforms the scheduling problem into a path-finding problem on a specially constructed layered graph. By encoding sequence-dependent effects directly into the graph's structure, we enable the use of classical shortest-path algorithms to compute optimal job sequences. The resulting method is polynomial-time solvable for the two-color case and reveals key structural properties of optimal schedules. Our approach thus provides both a theoretically grounded and practically applicable optimization technique. |
| title | Computing an optimal single machine schedule with sequence dependent setup times using shortest path computations |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2507.20611 |