Resources

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;