10X10 Job Shop Scheduling Problem (clp11)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: clp11 */
/* TITLE: 10X10 Job Shop Scheduling Problem (clp11) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: CLP, GANTT, SQL */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 11 from the CLP Procedure chapter of the */
/* Constraint Programming book. */
/* */
/***************************************************************/
/* jobs specification */
data raw (drop=i mid);
do i=1 to 10;
input mid _DURATION_ @;
_RESOURCE_=compress('M'||put(mid,best.));
output;
end;
datalines;
2 44 3 5 5 58 4 97 0 9 7 84 8 77 9 96 1 58 6 89
4 15 7 31 1 87 8 57 0 77 3 85 2 81 5 39 9 73 6 21
9 82 6 22 4 10 3 70 1 49 0 40 8 34 2 48 7 80 5 71
1 91 2 17 7 62 5 75 8 47 4 11 3 7 6 72 9 35 0 55
6 71 1 90 3 75 0 64 2 94 8 15 4 12 7 67 9 20 5 50
7 70 5 93 8 77 2 29 4 58 6 93 3 68 1 57 9 7 0 52
6 87 1 63 4 26 5 6 2 82 3 27 7 56 8 48 9 36 0 95
0 36 5 15 8 41 9 78 3 76 6 84 4 30 7 76 2 36 1 8
5 88 2 81 3 13 6 82 4 54 7 13 8 29 9 40 1 78 0 75
9 88 4 54 6 64 7 32 0 52 2 6 8 54 5 82 3 6 1 26
;
/* create the Activity data set */
data actdata (drop= i j);
format _ACTIVITY_ $8. _SUCCESSOR_ $8.;
set raw;
_QTY_ = 1;
i=mod(_n_-1,10)+1;
j=int((_n_-1)/10)+1;
_ACTIVITY_ = compress('J'||put(j,best.)||'P'||put(i,best.));
JOB=j;
TASK=i;
if i LT 10 then
_SUCCESSOR_ = compress('J'||put(j,best.)||'P'||put((i+1),best.));
else
_SUCCESSOR_ = ' ';
output;
run;
/* invoke PROC CLP to find a resource unconstrained schedule */
proc clp domain=[0,842]
actdata=actdata (drop=_resource_ _qty_)
schedout=sched_jobshop_un
showprogress;
schedule finish=842;
run;
/***************************************************************/
/* Define Utility Macros for Graphical Output */
/***************************************************************/
/* %colorIdex creates resource-pattern-color mapping */
/* %fnLegend uses footnote to add legends according to the mapping */
/* %setPatterns executes pattern statements according to the mapping */
%macro colorIdex(res_var=, proj=, palette=, out=);
proc sql;
create table &out as
select distinct(&res_var) from &proj;
quit;
data &out;
set &out;
drop name_tr color_ct;
format color $10.;
retain _pattern 1;
retain color_ct 1;
name_tr=lowcase(strip(&res_var));
if name_tr eq 'n/a' or name_tr eq '' then color='red';
else do;
color=scan(&palette, color_ct);
color_ct=color_ct+1;
end;
output;
_pattern=_pattern+1;
run;
%mend colorIdex;
/* macro %fnLegend uses footnote to add legends */
/* Title */
/* */
/* color bar 11 text ... color bar 1n text */
/* color bar m1 text ... color bar mn text */
%macro fnLegend(tfact=1.75,h=10,xStart=5,rhs=100,nCol=,nRow=,
title='Resource Used',map=,font='Albany AMT',var=_RESOURCE_);
%let rH = %sysevalf(&h/(&nRow+2)); /* row height */
%let cW = %sysevalf((&rhs-2*&xStart)/&nCol); /* column width */
%let rowsH = %sysevalf(&rH*&nRow); /* height of all legend rows */
%let barH = %sysevalf(&rH*0.35); /* height of legend (colored bars) */
%let rTextH = %sysevalf(&barH*&tfact); /* height of text in legend rows */
%let tiTextH = %sysevalf(&rTextH*1.2); /* height of text in title row */
footnote;
data _null_;
call execute('footnote1 f='||"&font"||' j=c h='||put(&tiTextH,best.)||
'pct '||'"'||&title||'";');
call execute('footnote2 f='||"&font"||' h='||put(&rH,best.)||'pct " ";');
run;
data _null_;
set &map end=finish;
retain count 0;
idxRow = int(count/&nCol);
idxCol = count - idxRow*&nCol;
x = &xStart + idxCol*&cW;
y = &rowsH - idxRow*&rH;
_fnlStr_=strip(&var);
if _fnlStr_ eq '' then _fnlStr_='N/A';
if count eq 0 then
call execute('footnote3 h='||put(&rowsH,best.)||'pct " "');
if lowcase(strip(color)) eq 'red' then
call execute(catx(' ','f=',"&font",'h=',&barH,'pct', 'm=(',x,',',y,
') pct','c=',color,
'box=1 bs=0 pct " "'));
else
call execute(catx(' ','f=',"&font",'h=',&barH,'pct', 'm=(',x,',',y,
') pct','c=',color,'bc=',color,
'box=1 bs=0 pct " "'));
call execute(catx(' ','f=',"&font",'h=',&rTextH,'pct', 'm=(+0.5,',y,
') pct','c=black')||' " '||_fnlStr_||'"');
count=count+1;
if finish then call execute(';');
run;
%mend fnLegend;
%macro setPatterns(map);
data _null_;
set ↦
cstr=lowcase(strip(color));
if cstr eq 'red' then
call execute('pattern'||strip(put(_pattern,best.))||' v=e color='||
cstr||' repeat=1;');
else
call execute('pattern'||strip(put(_pattern,best.))||' v=s color='||
cstr||' repeat=1;');
run;
%mend setPatterns;
/***************************************************************/
/* End Macro Definitions */
/***************************************************************/
/* add machine, pattern and segment */
%let _palette='magenta blue yellow orange cyan brown black gray green purple';
%colorIdex(res_var=_resource_,proj=actdata,palette=&_palette,
out=res_col_patn);
proc sql;
create table sched_gantt_jobshop_un as
select a.*, b._resource_, b._pattern, c.job, c.task as segmt_no
from sched_jobshop_un a, res_col_patn b, actdata c
where a.activity=c._activity_ and b._resource_=c._resource_;
quit;
/* draw the Gantt chart */
%setPatterns(res_col_patn);
title1 j=c h=5pct '10X10 Job Shop Scheduling Problem';
title2 j=c h=3pct 'Unconstrained Schedule';
%fnLegend(xStart=10,rhs=108,h=16,map=res_col_patn,title='Machine Required',
nCol=5,nRow=2,var=_resource_);
goptions vpos=30;
proc gantt data=sched_gantt_jobshop_un;
chart /
pcompress
nojobnum
nolegend
idpages
increment=60
scale=0.2
between=4
height=1.8
ref=20 617
reflabel
s_start=start
s_finish=finish;
id JOB;
run;
/* invoke PROC CLP to find a resource-constrained schedule */
proc clp domain=[0,842]
actdata=actdata
schedout=sched_jobshop
dpr=50
restarts=150
showprogress;
schedule finish=842 edgefinder nf=1 nl=1;
run;
/* add machine, pattern and segment */
proc sql;
create table sched_gantt_jobshop as
select a.*, b._resource_, b._pattern, c.job, c.task as segmt_no
from sched_jobshop a, res_col_patn b, actdata c
where a.activity=c._activity_ and b._resource_=c._resource_;
quit;
/* draw the Gantt chart */
title1 j=c h=5pct '10X10 Job Shop Scheduling Problem';
title2 j=c h=3pct 'Constrained Schedule';
%fnLegend(xStart=10,rhs=108,h=16,map=res_col_patn,title='Machine Required',
nCol=5,nRow=2,var=_resource_);
goptions vpos=30;
proc gantt data=sched_gantt_jobshop(obs=100);
chart /
pcompress
nojobnum
nolegend
idpages
increment=60
scale=0.15
between=4
height=1.8
ref=842
reflabel
s_start=start
s_finish=finish;
id JOB;
run;
goptions reset=all;