The Car Resequencing Problem with Makespan Minimization
Abstract
Problem definition: The car resequencing problem involves rearranging the sequence of cars between two adjacent production shops via an intermediate buffer. This study explores a new variant that aims to minimize the resequencing makespan when the buffer features several forward lanes and a return lane (RL). Both types of lanes follow first-in-first-out rules, but operate in opposite directions. Through the RL, cars can circulate between forward lanes, thereby increasing resequencing flexibility and complexity. The goal is to position cars over time to complete the target sequence change in the shortest possible time. Methodology/results: We prove the problem is NP-complete and develop an exact two-stage branch-and-price approach integrated with constraint programming (BP-CP). Three versions of the master problem (MP) are proposed for the first stage, each paired with a subproblem defined on a specific graph. Using partial integer solutions from branching, a constraint-programming model built in the second stage yields either a feasible solution to the problem or a feasibility cut added to the MP. Experimental results indicate that BP-CP greatly increases the scale of solvable instances for a production batch, especially with a moderately relaxed MP. A comparative analysis shows that the RL markedly enhances resequencing flexibility, enabling smaller buffers to attain makespans comparable to those of larger buffers without the RL across varying resequencing complexities. Managerial implications: Expanding lane capacity alone yields limited gains in resequencing performance and may even reduce efficiency. The RL acts as several forward lanes, supporting a smaller and cost-effective buffer design while maintaining efficient just-in-time operations.
Related
- Constrained minimization problem and unbounded dynamics for the four-dimensional Klein-Gordon-Schrödinger System
- Nucleation and propagation of brittle fracture as a constrained energy minimization problem
- Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm
- A minimization problem for a cooperative system with a degenerate Bernoulli weight
- Minimizing the makespan in job shop scheduling under conflict graph constraints
BibTeX
@misc{guo2026resequencing,
title = {{The Car Resequencing Problem with Makespan Minimization}},
author = {Xinyi Guo and Jean-François Côté},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09602},
eprint = {2609.09602},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09602},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Car Resequencing Problem with Makespan Minimization
AU - Xinyi Guo
AU - Jean-François Côté
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.09602
UR - https://arxiv.org/abs/2609.09602
AB - Problem definition: The car resequencing problem involves rearranging the sequence of cars between two adjacent production shops via an intermediate buffer. This study explores a new variant that aims to minimize the resequencing makespan when the buffer features several forward lanes and a return lane (RL). Both types of lanes follow first-in-first-out rules, but operate in opposite directions. Through the RL, cars can circulate between forward lanes, thereby increasing resequencing flexibility and complexity. The goal is to position cars over time to complete the target sequence change in the shortest possible time. Methodology/results: We prove the problem is NP-complete and develop an exact two-stage branch-and-price approach integrated with constraint programming (BP-CP). Three versions of the master problem (MP) are proposed for the first stage, each paired with a subproblem defined on a specific graph. Using partial integer solutions from branching, a constraint-programming model built in the second stage yields either a feasible solution to the problem or a feasibility cut added to the MP. Experimental results indicate that BP-CP greatly increases the scale of solvable instances for a production batch, especially with a moderately relaxed MP. A comparative analysis shows that the RL markedly enhances resequencing flexibility, enabling smaller buffers to attain makespans comparable to those of larger buffers without the RL across varying resequencing complexities. Managerial implications: Expanding lane capacity alone yields limited gains in resequencing performance and may even reduce efficiency. The RL acts as several forward lanes, supporting a smaller and cost-effective buffer design while maintaining efficient just-in-time operations.
ER -