8. Tabu Search Approaches for Two Car Sequencing Problems with Smoothing Constraints

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 equipments, 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). The goal of this chapter is to propose Tabu search approaches for two car sequencing problems involving smoothing constraints. The first one is denoted (P1) and was the subject of the ROADEF 2005 international Challenge proposed by the automobile manufacturer Renault, whereas the second one is denoted (P2) and extends some important features of (P1).