.png){kind=icon}
.png){kind=icon}
Return
Models and algorithms for configuring and testing prototype cars
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2024.106834.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we consider a new industrial problem that occurs in the automobile industry's context during the testing phase of a new vehicle model. A vehicle model is sold in different configurations, , corresponding with different associations of options, and a test can only be performed on a vehicle if all its options are compatible with this test. Our problem consists of determining the number of vehicles (called prototypes) to manufacture, their configurations, and the order in which tests are realized on each prototype. We formally cast this problem into a scheduling problem where jobs are tests, machines are prototypes, and two objectives are lexicographically optimized: the number of late jobs and the number of machines used. First, we prove that even finding a feasible solution for the problem is NP-hard and characterize cases where it is equivalent to a scheduling problem with pairwise job incompatibilities. Then, we propose two integer linear programming models: a compact formulation and a path-flow formulation. We solve the latter formulation using a column generation algorithm and a diving heuristic based on a labeling algorithm that includes machine configuration. We validate our approaches against real-life data sets provided by Renault and provide additional experiments to study the sensitivity of our different methods to key instance properties. Our path-flow model allows us to find better solutions than those obtained by a CP solver used by the company. It proves the optimality for all instances of our benchmark for the first objective function and obtains small optimality gaps for the second objective function.
Keywords:
Scheduling
Mixed integer linear programming
Column and row generation
Diving heuristic
Automobile industry
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W