Resources

Car Painting Problem (oclpe05)

/***************************************************************/
/*                                                             */
/*          S A S   S A M P L E   L I B R A R Y                */
/*                                                             */
/*    NAME: oclpe05                                            */
/*   TITLE: Car Painting Problem (oclpe05)                     */
/* PRODUCT: OR                                                 */
/*  SYSTEM: ALL                                                */
/*    KEYS: OR                                                 */
/*   PROCS: OPTMODEL, GANTT                                    */
/*    DATA:                                                    */
/*                                                             */
/* SUPPORT:                             UPDATE:                */
/*     REF:                                                    */
/*    MISC: Example 5 from the CLP solver chapter of the       */
/*          Mathematical Programming book.                     */
/*                                                             */
/***************************************************************/

%macro car_painting(purgings);
   proc optmodel;
      num nCars = 10;
      /* a car is identified by its original slots */
      set SLOTS = 1..nCars;

      /* maximum reshuffling of any car on the line*/
      num maxMove init 3;
      /* which car is in slot i. */
      var S {si in SLOTS} integer >= max(1, si - maxMove)
                                  <= min(nCars, si + maxMove) ;

      /* which color the car in slot i is. */
      /* Red=1; Blue=2; Green=3; Yellow=4 */
      num nColors=4;
      num colorOf{SLOTS} = [ 1 2 3 4 1 2 3 4 1 2 ];
      var C {SLOTS} integer >= 1 <= nColors;

      con ElementCon {i in SLOTS}:
         element(S[i], colorOf, C[i]);

      /* A car can be painted only once. */
      con PaintOnlyOnce:
         alldiff(S);

      /* Whether there is a purge after slot i.
        You can ignore any purging that would happen at the end of the shift. */
      var P {SLOTS diff {nCars}} binary;

      con ReifyCon {i in SLOTS diff {nCars}}:
         reify(P[i], C[i] ne C[i+1]);

      /* Calculate the number of purgings. */
      con PurgingsCon:
         sum {i in SLOTS diff {nCars}} P[i] <= &purgings;

      solve with CLP / findall;
      /* Replicate typical PROC CLP output from PROC OPTMODEL arrays */
      create data car_ds(drop=k) from [k]=(1.._NSOL_)
         {i in SLOTS} <col('S'||i)=S[i].sol[k]>
         {i in SLOTS} <col('C'||i)=C[i].sol[k]>;
   quit;
%mend;
%car_painting(5);


/* Produce Gantt Chart */

%macro car_painting_gantt;

/* map colors to patterns */
%let color1 = red;
%let color5 = &color1;
%let color9 = &color5;
%let color2 = blue;
%let color6 = &color2;
%let color10 = &color6;
%let color3 = green;
%let color7 = &color3;
%let color4 = yellow;
%let color8 = &color4;

/* set patterns */
%do i=1 %to 10;
   pattern&i. v=s color=&&color&i. repeat=1;
%end;


data card_ds(keep=S1-S10 dist);
   set car_ds;
   dist = 0;
   %do i = 1 %to 10;
      dist = dist + abs(S&i-&i);
   %end;
run;

proc sort data=card_ds;
  by dist;
run;

proc format;
   value stage
      0.5 = '1'
      9.5 = '10'
      10.5 = ' '
      ;
run;

data schedule;
   format _label $13.;
   format s_start stage.;
   label solution='Solution';
   label dist='Distance';
   set card_ds;
   keep _pattern _label segmt_no solution s_start s_finish dist;
   retain solution 1;
   %do i = 1 %to 10;
      s_start=%eval(&i-1)+0.5;
      s_finish=&i+0.5;
      segmt_no = &i;
      nextpat = 0; /* ensure no match */
      %do j = 1 %to 10;
         if S&i. eq &j then do;
            _label = "Car &j: &&color&j";
            _pattern = &j;
         end;
         %if %eval(&i.+1) lt 10 %then %do;
            if S%eval(&i+1) eq &j then do;
               nextpat = &j;
            end;
         %end;
      %end;
      if mod(nextpat - _pattern,4) ne 0 then do;
         s_finish = s_finish - 0.05;
      end;
      output;
   %end;
   solution = solution + 1;
run;

data labels;
   _y=-1;
   _lvar="_label";
   _xvar="s_start";
   _hlabel=0.67;
   _yoffset = -0.2;
   _xoffset = 0;
run;

proc format;
   value stage
      0.5 = '1'
      9.5 = '10'
      10.5 = ' '
      ;
run;

goptions htext=1.0;
title1 j=c h=3.3pct 'Car Painting Problem';
title2 j=c h=2.3pct 'Solutions with Five Purgings';

proc gantt data=schedule labdata=labels;
   chart /
      hpages=1 pcompress
      scale=5
      njobs=15
      chartwidth=84
      nojobnum
      nolegend
      mindate=0.5
      useformat
      labsplit='/'
      ;
   id solution dist;
run;

%mend car_painting_gantt;

%car_painting_gantt;