The Car Sequencing Problem (oclpe07)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: oclpe07 */
/* TITLE: The Car Sequencing Problem (oclpe07) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: OPTMODEL, GANTT, SQL */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 7 from the CLP solver chapter of the */
/* Mathematical Programming book. */
/* */
/***************************************************************/
data class_data;
input class cars_cls;
datalines;
1 1
2 1
3 2
4 2
5 2
6 2
;
data option_data;
input option max blSz class1-class6;
datalines;
1 1 2 1 0 0 0 1 1
2 2 3 0 0 1 1 0 1
3 1 3 1 0 0 0 1 0
4 2 5 1 1 0 1 0 0
5 1 5 0 0 1 0 0 0
;
%macro car_sequencing(outdata);
proc optmodel;
set CLASSES;
num nClasses = card(CLASSES);
num cars_cls {CLASSES};
read data class_data into CLASSES=[class] cars_cls;
set OPTIONS;
num max {OPTIONS};
num blSz {OPTIONS};
num list {OPTIONS, CLASSES};
num cars_opt {i in OPTIONS} = sum {k in CLASSES} cars_cls[k] * list[i,k];
read data option_data into OPTIONS=[option] max blSz
{k in CLASSES} <list[option,k]=col('class'||k)>;
num nCars = sum {k in CLASSES} cars_cls[k];
set SLOTS = 1..nCars;
/* Declare Variables */
/* Slot variables: S[i] - class of car assigned to Slot i */
var S {SLOTS} integer >= 1 <= nClasses;
/* Option variables: O[i,j]
- indicates if class assigned to Slot i needs Option j */
var O {SLOTS, OPTIONS} binary;
/* Capacity Constraints: for each option j */
/* Install in at most max[j] out of every sequence of blSz[j] cars */
con CapacityCon {j in OPTIONS, i in 0..(nCars-blSz[j])}:
sum {k in 1..blSz[j]} O[i+k,j] <= max[j];
/* Demand Constraints: for each class k */
/* Exactly cars_cls[k] cars */
con MeetDemandCon:
gcc(S, setof{k in CLASSES} <k,cars_cls[k],cars_cls[k]>);
/* Element Constraints: For each slot i and each option j */
/* relate the slot variable to the option variables. */
/* O[i,j] = list[j,S[i]] */
con OptionsAtSlotCon {i in SLOTS, j in OPTIONS}:
element(S[i], {k in CLASSES} list[j,k], O[i,j]);
/* 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 */
con BoundRemainingCon {j in OPTIONS, i in 1..(nCars/blSz[j])}:
sum {k in 1..(nCars-i*blSz[j])} O[k,j] >= cars_opt[j] - i * max[j];
solve with CLP / varselect=minrmaxc findall;
/* Replicate typical PROC CLP output from PROC OPTMODEL arrays */
create data &outdata.(drop=sol) from [sol]=(1.._NSOL_)
{i in SLOTS} <col('S_'||i)=S[i].sol[sol]>
{i in SLOTS, j in OPTIONS} <col('O_'||i||'_'||j)=O[i,j].sol[sol]>;
quit;
%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;