Titre :  Exact and Solution Methods for a Car Sequencing Problem

Conférencier :  ZUFFEREY, Nicolas (GERAD, Université de Genève, Suisse)

Résumé :
Nowadays, new constraints, known as smoothing constraints, are attracting a growing attention in the area of job scheduling, and in particular for car sequencing problems, where cars must be scheduled before production in an order respecting various constraints (colors, optional equipment, due dates, etc.), while avoiding overloading some important resources. The first objective of the car industry is to assign a production day to each customer-ordered car and the second one consists of scheduling the order of cars to be put on the line for each production day, while satisfying as many requirements as possible of the plant shops (e.g., paint shop, assembly line).

In 2005, the car manufacturer Renault proposes a car sequencing problem through the ROADEF 2005 Challenge, with real instances involving hundreds of cars. Car families are defined so that two cars of the same family contain the same optional equipment. Each optional equipment i is associated with a N/P ratio constraint, meaning that at most N cars with option i can be scheduled in any subsequence of P cars, otherwise a penalty occurs. The objective is to minimize a weighted function involving ratio constraint violations and the number of color changes.

A variation of the Renault problem is studied here, where non-identical parallel machines (or production lines) and eligibility constraints are considered (i.e. a job or a car can only be performed on some specific machines). The objective function involves three components (namely makespan, smoothing costs and setup costs) which are tackled hierarchically.
A mixed integer linear programming (MILP) formulation is first presented, and then several solution methods are proposed, ranging from greedy procedures to a tabu search and an adaptive memory algorithm. For small instances (with up to 40 jobs) whose MILP formulation can be solved to optimality, tabu search provides remarkably good solutions. The adaptive memory algorithm, using tabu search as an intensification procedure, turns out to yield the best results on large instances, with up to 500 jobs and 8 machines.