EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3192. The maximum length car sequencing problem

Invited abstract in session WA-52: Models and algorithms for real-life combinatorial optimization problems, stream Combinatorial Optimization.

Wednesday, 8:30-10:00
Room: 8003 (building: 202)

Authors (first author is the speaker)

1. Lara Pontes
Centro de Informática, Universidade Federal da Paraíba
2. Carlos Neves
Universidade Federal da Paraíba
3. Anand Subramanian
Universidade Federal da Paraíba
4. Maria Battarra

Abstract

This study introduces a new variant of the car sequencing problem to support the operations of a Brazilian automotive assembly plant. We propose an integer linear programming (ILP) formulation to schedule the maximum number of cars without violating the spacing constraints associated with car options, such as air-conditioning or sunroof. In the studied plant, these violations lead to a complete stop of the assembly line, which is the least desirable outcome for the company. We also present valid combinatorial lower and upper bounds, as well as binary and iterative search algorithms to solve the problem when good primal bounds are not readily available. In addition, we develop an effective iterated local search algorithm to quickly obtain high-quality solutions, then used as a warm start to the exact methods. Computational results demonstrate that relatively low gaps are achieved for benchmark instances within a time limit of ten minutes, and we conduct an instance space analysis to identify the features that make the problem more difficult to solve. Moreover, the instances reflecting the company's needs are solved to optimality in less than a second. Finally, simulations with real-world demands, divided into shifts, are performed for a period of four months. In this case, we use the proposed ILP model in all shifts except the last one of each month, for which we employ an alternative model to sequence the unscheduled cars, adjusting the pace of the assembly line.

Keywords

Status: accepted

Back to the list of papers