The maximum length car sequencing problem

Lara Pontes, Carlos Neves, Anand Subramanian and Maria Battarra

European Journal of Operational Research, 2024, vol. 316, issue 2, 707-717

Abstract: This paper introduces the maximum length car sequencing problem to support the assembly operations of a multinational automotive company. We propose an integer linear programming (ILP) formulation to schedule the maximum number of cars without violating the so-called option constraints. In addition, we present valid combinatorial lower and upper bounds, which can be calculated in less than 0.01 s, as well as binary and iterative search algorithms to solve the problem when good primal bounds are not readily available. To quickly obtain high-quality solutions, we devise an effective iterated local search algorithm, and we use the heuristic solutions as warm start to further enhance the performance of the exact methods. Computational results demonstrate that relatively low gaps were achieved for benchmark instances within a time limit of ten minutes. We also conducted an instance space analysis to identify the features that make the problem more difficult to solve. Moreover, the instances reflecting the company’s needs could be solved to optimality in less than a second. Finally, simulations with real-world demands, divided into shifts, were conducted over 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 ILP model to sequence the unscheduled cars, adjusting the pace of the assembly line in an optimal fashion. The results pointed out that the latter was necessary in only one of the months.

Keywords: Scheduling; Assembly line; Car sequencing; Combinatorial optimization (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724001322
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:316:y:2024:i:2:p:707-717

DOI: 10.1016/j.ejor.2024.02.024

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().