The Car Sequencing Problem (clp7)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: clp7 */
/* TITLE: The Car Sequencing Problem (clp7) */
/* 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
;
run;
%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;