The CLP Procedure

Example 3.5 Car Painting Problem

The car painting process is an important part of the automobile manufacturing industry. Purging (the act of changing colors in the assembly process) is expensive due to the added cost of wasted paint and solvents involved with each color change in addition to the extra time required for the purging process. The objective in the car painting problem is to sequence the cars in the assembly in order to minimize paint changeover (Sokol; 2002; Trick; 2004).

There are 10 cars in a sequence. The order for assembly is 1, 2, ..., 10. A car must be painted within three positions of its assembly order. For example, car 5 can be painted in positions 2 through 8 inclusive. Cars 1, 5, and 9 are red; 2, 6, and 10 are blue; 3 and 7 green; and 4 and 8 are yellow. The initial sequence 1, 2, ..., 10 corresponds to the color pattern RBGYRBGYRB and has nine purgings. The objective is to find a solution that minimizes the number of purgings.

This problem can be formulated as a CSP as follows. The variables and represent the ID and color, respectively, of the car in slot . An element constraint relates the car ID to its color. An all-different constraint ensures that every slot is associated with a unique car ID. Two linear constraints represent the constraint that a car must be painted within three positions of its assembly order. The binary variable indicates whether a paint purge takes place after the car in slot is painted. Finally, a linear constraint is used to limit the total number of purgings to the required number.

The following %CAR_PAINTING macro determines all feasible solutions for a given number of purgings, which is specified as a parameter to the macro:

%macro car_painting(purgings);

    proc clp out=car_ds findall;

       %do i = 1 %to 10;
          var S&i = [1, 10]; /* which car is in slot &i.*/
          var C&i = [1, 4]; /* which color the car in slot &i is.*/
          /* Red=1; Blue=2; Green=3; Yellow=4 */
          element (S&i, (1, 2, 3, 4, 1, 2, 3, 4, 1, 2), C&i);
       %end;

       /* A car can be painted only once. */
       alldiff (S1-S10);

       /* A car must be painted within 3 positions of its assembly order. */
       %do i = 1 %to 10;
          lincon S&i-&i>=-3;
          lincon S&i-&i<=3;
       %end;

       %do i = 1 %to 9;
          var P&i = [0, 1]; /* Whether there is a purge after slot &i*/
          reify P&i: (C&i <> C%eval(&i+1));
       %end;

       /* Calculate the number of purgings. */
       lincon 0 
       %do i = 1 %to 9;
          + P&i 
       %end;
       <=&purgings ;
    run;

%mend;
%car_painting(5)

The problem is infeasible for four purgings. The CLP procedure finds 87 possible solutions for the five purgings problem. The solutions are sorted by the total distance all cars are moved in the sequencing, which ranges from 12 to 22 slots. The first 15 solutions are displayed in the Gantt chart in Output 3.5.1. Each row represents a solution, and each color transition represents a paint purge.

Output 3.5.1 Car Painting Schedule with Five Purgings