## The Car Sequencing Problem (clpe07)

```/***************************************************************/
/*                                                             */
/*          S A S   S A M P L E   L I B R A R Y                */
/*                                                             */
/*    NAME: clpe07                                             */
/*   TITLE: The Car Sequencing Problem (clpe07)                */
/* PRODUCT: OR                                                 */
/*  SYSTEM: ALL                                                */
/*    KEYS: OR                                                 */
/*   PROCS: CLP, GANTT, SQL                                    */
/*    DATA:                                                    */
/*                                                             */
/* SUPPORT:                             UPDATE:                */
/*     REF:                                                    */
/*    MISC: Example 7 from the CLP Procedure chapter of the    */
/*          Constraint Programming book.                       */
/*                                                             */
/***************************************************************/

/*

First line: number of cars; number of options; number of classes.

Second line: for each option, the maximum number of cars with that
option in a block.

Third line: for each option, the block size to which the maximum
number refers.

Then for each class: index no.; no. of cars in this class; for each
option, whether or not this class requires it (1 or 0).

*/

data input;
input col1 col2 col3 col4 col5 col6 col7;
datalines;
10 5 6 . . . .
1 2 1 2 1 . .
2 3 3 5 5 . .
0 1 1 0 1 1 0
1 1 0 0 0 1 0
2 2 0 1 0 0 1
3 2 0 1 0 1 0
4 2 1 0 1 0 0
5 2 1 1 0 0 0
;

%macro car_sequencing_data(indata);

%global
Ncars   /* number of cars     */
Nops    /* number of options  */
Nclss;  /* number of classes  */

/* Read input data set */
data _null_;
set &indata;
if _n_=1 then do;
call symput('Ncars', strip(put(col1,best.)));
call symput('Nops', strip(put(col2,best.)));
call symput('Nclss', strip(put(col3,best.)));
end;
run;

%do i = 1 %to &Nops;
%global
Max_&i        /* Maximum number of cars with option &i in a  */
/*   block of size BlSz_i                      */
BlSz_&i       /* For option &i, the block size corresponding */
/*   to Max_i                                  */
list_&i       /* class indicator list for option &i          */
cars_opts_&i; /* Number of cars requiring option &i          */
%end;

%do i = 1 %to &Nclss;
%global
class_&i      /* class index number of class &i */
cars_cls_&i;  /* number of cars in class &i     */
%end;

data _null_;
set &indata;
if _n_=2 then do;
%do i = 1 %to &Nops;
call symput("Max_&i", put(col&i,best.));
%end;
end;

if _n_=3 then do;
%do i = 1 %to &Nops;
call symput("BlSz_&i", put(col&i,best.));
%end;
end;

if _n_>=4 then do;
call symput("class_"||strip(put(_n_-3,best.)), put(col1+1,best.));
call symput("cars_cls_"||strip(put(_n_-3,best.)), put(col2,best.));
%do i = 1 %to &Nops;
call symput("cars_opts_&i", put(col2*col%eval(&i+2),best.) );
%end;
end;
run;

/* Create list of columns to generate option lists. */
data input1;
set &indata;
if _n_<=3 then delete;
run;

proc sql noprint;
%do i=1 %to &Nops;
select col%eval(&i+2) into :list_&i separated by "," from input1;
select sum( col2 * col%eval(&i+2) ) into: cars_opts_&i from input1;
%end;
quit;

%mend car_sequencing_data;
%car_sequencing_data(input);

%macro car_sequencing(outdata);

proc clp out=&outdata varselect=minrmaxc findall;

/* Declare Variables */
var
/* Slot variables: Si - class of car assigned to Slot i */
%do i = 1 %to &Ncars;
S_&i = [1, &Nclss]
%end;

/* Option variables: Oij
- indicates if class assigned to Sloti needs Option j */
%do i = 1 %to &Ncars;
%do j = 1 %to &Nops;
O_&i._&j = [0, 1]
%end;
%end;
;

/* Capacity Constraints: for each option j */
/* Installed in at most Max_j cars out of every sequence of BlSz_j cars */
%do j = 1 %to &Nops;
%do i = 0 %to %eval(&Ncars-&&BlSz_&j);
lincon 0
%do k=1 %to &&BlSz_&j;
+ O_%eval(&i+&k)_&j
%end;
<=&&Max_&j;
%end;
%end;

/* Demand Constraints: for each class i */
/* Exactly cars_cls_i cars */
gcc (S_1-S_&Ncars) = (
%do i = 1 %to &Nclss;
(&&class_&i, &&cars_cls_&i, &&cars_cls_&i)
%end;
);

/* Element Constraints: For each slot i and each option j */
/* relate the slot variable to the option variables.      */
/*  O_i_j is the S_i th element in list_j.                */
%do i = 1 %to &Ncars;
%do j = 1 %to &Nops;
element (S_&i, (&&list_&j), O_&i._&j);
%end;
%end;

/* Redundant Constraints to improve efficiency - for every  */
/*    option j.                                             */
/* At most &&Max_&j out of every sequence of &&BlSz_&j cars */
/*    requires option j.                                    */
/* All the other slots contain at least cars_opt_j - Max_j  */
/*    cars with option j                                    */
%do j = 1 %to &Nops;
%do i = 1 %to %eval(&Ncars/&&BlSz_&j);
lincon 0
%do k=1 %to %eval(&Ncars-&i*&&BlSz_&j);
+ O_&k._&j
%end;
>= %eval(&&cars_opts_&j-&i*&&Max_&j);
%end;
%end;
run;

%mend;
%car_sequencing(sequence_out);

%macro car_sequencing_gantt;

/* map classes to colors */
%let class1 = red;
%let class2 = blue;
%let class3 = gray;
%let class4 = blue;
%let class5 = cyan;
%let class6 = yellow;

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

proc sort data=sequence_out;
by
%do j = 1 %to 10;
S_&j
%end;
;
run;

data carseq_ds(keep=S_1-S_10);
set sequence_out;
run;

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

data schedule;
format _label \$8.;
format s_start stage.;
label solution='Solution';
set carseq_ds;
keep _pattern _label segmt_no solution s_start s_finish;
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 6;
if S_&i eq &j then do;
_label = "Class %eval(&j)";
_pattern = &j;
end;
if S_&i eq %eval(&j+1) then do;
nextpat = &j;
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=1.0;
_yoffset = -0.6;
_xoffset = 0.25;
run;
goptions htext=1.5;
title1 j=c h=5pct 'Car Sequencing Problem';
title2 j=c h=3pct 'Assembly Sequence for All Six Solutions';
proc gantt data=schedule labdata=labels;
chart /
pcompress
skip=3
nojobnum
nolegend
mindate=0.5
useformat
labsplit='/'
increment=1
barht=2
baroff=0.8
;
id solution;
run;

%mend car_sequencing_gantt;
%car_sequencing_gantt;

```