The car sequencing problem

Describes the problem.

Consider the following problem. A car assembly line is set up to build cars on a production line divided into cells. Five cells that install options on cars require more than one task time to perform the operation. Their limitation is defined by the number of cars they can process in a period of time. There are seven different car configurations (or types), and the number of cars to build is derived from the demand for each configuration. The objective of the model is to compute a sequence of cars that the cells can process while minimizing the number of empty cars to insert to respect the load of the cells.

The initial model includes the following elements:

  • The demand

  • The production capacity

  • The decision variables

  • The constraints

  • The data

The demand

In the following code extract: 


int nbCars = sum (c in Confs) demand[c];
int nbSlots = ftoi(floor(nbCars * 1.1 + 5)); // 10% slack + 5 slots
int nbBlanks = nbSlots - nbCars;
range Slots = 1..nbSlots;
int option[Options,Confs] = ...;

The demand element represents the number of cars to build for each type.

The nbSlots element is the total number of cars to sequence. This number is multiplied by ten percent to make sure that it is possible to insert enough null cars to make the problem feasible.

The option array of Boolean values defines the options required for each car type. See Instance data for the car sequencing problem (carseq.dat)

The production capacity

In the following code extract, the array defines the number of cars that can be processed for an option in a period of time: 


tuple CapacitatedWindow {
  int l;
  int u;
};
CapacitatedWindow capacity[Options] = ...;

The decision variables

The first decision variable defines the sequence of cars.

The second decision variable defines the length of the sequence; that is, the last non-null car.


dvar int slot[Slots] in AllConfs;
dvar int lastSlot in nbCars..nbSlots;

The objective

The objective function of the car sequencing model is to compute a sequence of cars that the cells can process while minimizing the number of empty cars to insert to respect the load of the cells.


minimize lastSlot - nbCars;

The constraints

The mode defines four constraints written as forall statements:

  • to satisfy the demand:

  • to define the options that are used for each car in the sequence.

  • to define the length of the sequence


subject to {
  // Cardinality of configurations
  count(slot, 0) == nbBlanks;
  forall (c in Confs)
    count(slot, c) == demand[c];

  // Capacity of gliding windows
  forall(o in Options, s in Slots : s + capacity[o].u - 1 <= nbSlots)
    sum(j in s .. s + capacity[o].u - 1) allOptions[o][slot[j]] <= capacity[o].l;

  // Last slot
  forall (s in nbCars + 1 .. nbSlots)
    (s > lastSlot) => slot[s] == 0;
};

The data

The data for the car sequencing problem is initialized externally in the following data file example, carseq.dat.

Instance data for the car sequencing problem (carseq.dat)

nbConfs = 7;
nbOptions = 5;
demand = [5, 5, 10, 10, 10, 10, 5];

option = [
           [ 1, 0, 0, 0, 1, 1, 0],
           [ 0, 0, 1, 1, 0, 1, 0],
           [ 1, 0, 0, 0, 1, 0, 0],
           [ 1, 1, 0, 1, 0, 0, 0],
           [ 0, 0, 1, 0, 0, 0, 0]
        ];

capacity = [
      <1,2>,
      <2,3>,
      <1,3>,
      <2,5>,
      <1,5>
   ];