Salle 2, IMB
le 14 décembre 2023 à 11:00
In this presentation, we consider a new industrial problem, which occurs in the context of the automobile industry. This problem occurs during the testing phase of a new vehicle. It involves determining all the variants of the vehicle to be manufactured in order to carry out these tests, and scheduling these tests over time. We model this problem as a new scheduling scheduling problem. Given a set of machines, and a set of jobs, we seek a fixed configuration for each machine (i.e. a set of values for various parameters), and an assignment of jobs to machines along the time horizon that respects compatibility constraints between jobs and machine configurations. Two objectives are lexicographically optimized: the number of late jobs, and the number of machines used. This problem involves a notion of configuration that is not addressed in the literature. First we prove that even finding a feasible solution for the problem is NP-hard, and characterize the cases where compatibility constraints amount to ensuring that only pairwise compatible jobs are assigned to each machine. We then propose a mathematical model for this problem, and a reformulation into a path-flow formulation. To deal with the new notion of configuration, we propose a refined labelling algorithm embedded in a column-and-row generation algorithm to generate primal and dual bounds from this formulation. We conducted computational experiments on industrial data from Renault, and compared our results with those obtained by solving a constraint programming model provided by the company. Our approach finds better solutions than those obtained by the company, and proves the optimality for all instances of our benchmark for the first objective function. We also obtain small optimality gaps for the second objective function.