A Scheduling Problem (lp13)
/****************************************************************/
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: LP13 */
/* TITLE: A Scheduling Problem (lp13) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: LP */
/* PROCS: LP */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: */
/* */
/****************************************************************/
data raw;
input name $ hour slot mon tue wed thu fri;
datalines;
marc 20 1 10 10 10 10 10
marc 20 2 9 9 9 9 9
marc 20 3 8 8 8 8 8
marc 20 4 1 1 1 1 1
marc 20 5 1 1 1 1 1
marc 20 6 1 1 1 1 1
marc 20 7 1 1 1 1 1
marc 20 8 1 1 1 1 1
mike 20 1 10 9 8 7 6
mike 20 2 10 9 8 7 6
mike 20 3 10 9 8 7 6
mike 20 4 10 3 3 3 3
mike 20 5 1 1 1 1 1
mike 20 6 1 2 3 4 5
mike 20 7 1 2 3 4 5
mike 20 8 1 2 3 4 5
bill 20 1 10 10 10 10 10
bill 20 2 9 9 9 9 9
bill 20 3 8 8 8 8 8
bill 20 4 0 0 0 0 0
bill 20 5 1 1 1 1 1
bill 20 6 1 1 1 1 1
bill 20 7 1 1 1 1 1
bill 20 8 1 1 1 1 1
bob 20 1 10 9 8 7 6
bob 20 2 10 9 8 7 6
bob 20 3 10 9 8 7 6
bob 20 4 10 3 3 3 3
bob 20 5 1 1 1 1 1
bob 20 6 1 2 3 4 5
bob 20 7 1 2 3 4 5
bob 20 8 1 2 3 4 5
;
data model;
array workweek{5} mon tue wed thu fri;
array hours{4} hours1 hours2 hours3 hours4;
retain hours1-hours4;
set raw end=eof;
length _row_ $ 8 _col_ $ 8 _type_ $ 8;
keep _type_ _col_ _row_ _coef_;
if name='marc' then i=1;
else if name='mike' then i=2;
else if name='bill' then i=3;
else if name='bob' then i=4;
hours{i}=hour;
/* build the objective function */
do k=1 to 5;
_col_='x'||put(i,1.)||put(slot,1.)||put(k,1.);
_row_='object';
_coef_=workweek{k} * 1000;
output;
_row_='upper';
if workweek{k}^=0 then _coef_=1;
output;
_row_='integer';
_coef_=1;
output;
end;
/* build the rest of the model */
if eof then do;
_coef_=.;
_col_=' ';
_type_='upper';
_row_='upper';
output;
_type_='max';
_row_='object';
output;
_type_='int';
_row_='integer';
output;
/* every hour 1 person working */
do j=1 to 8;
do k=1 to 5;
_row_='work'||put(j,1.)||put(k,1.);
_type_='eq';
_col_='_RHS_';
_coef_=1;
output;
_coef_=1;
_type_=' ';
do i=1 to 4;
_col_='x'||put(i,1.)||put(j,1.)||put(k,1.);
output;
end;
end;
end;
/* each person has a lunch */
do i=1 to 4;
do k=1 to 5;
_row_='lunch'||put(i,1.)||put(k,1.);
_type_='le';
_col_='_RHS_';
_coef_=1;
output;
_coef_=1;
_type_=' ';
_col_='x'||put(i,1.)||'4'||put(k,1.);
output;
_col_='x'||put(i,1.)||'5'||put(k,1.);
output;
end;
end;
/* work at most 2 slots in a row */
do i=1 to 4;
do k=1 to 5;
do l=1 to 6;
_row_='seq'||put(i,1.)||put(k,1.)||put(l,1.);
_type_='le';
_col_='_RHS_';
_coef_=2;
output;
_coef_=1;
_type_=' ';
do j=0 to 2;
_col_='x'||put(i,1.)||put(l+j,1.)||put(k,1.);
output;
end;
end;
end;
end;
/* work at most n hours in a week */
do i=1 to 4;
_row_='capacit'||put(i,1.);
_type_='le';
_col_='_RHS_';
_coef_=hours{i};
output;
_coef_=1;
_type_=' ';
do j=1 to 8;
do k=1 to 5;
_col_='x'||put(i,1.)||put(j,1.)||put(k,1.);
output;
end;
end;
end;
end;
run;
/* solve the linear program */
proc lp sparsedata noprint primalout=solution
time=1000 maxit1=1000 maxit2=1000;
run;
/* report the solution */
title 'Reported Solution';
data report;
set solution;
keep name slot mon tue wed thu fri;
if substr(_var_,1,1)='x' then do;
if _value_>0 then do;
n=substr(_var_,2,1);
slot=substr(_var_,3,1);
d=substr(_var_,4,1);
if n='1' then name='marc';
else if n='2' then name='mike';
else if n='3' then name='bill';
else name='bob';
if d='1' then mon=1;
else if d='2' then tue=1;
else if d='3' then wed=1;
else if d='4' then thu=1;
else fri=1;
output;
end;
end;
run;
proc format;
value xfmt 1=' xxx ';
run;
proc tabulate data=report;
class name slot;
var mon--fri;
table (slot * name), (mon tue wed thu fri)*sum=' '*f=xfmt.
/misstext=' ';
run;
%put &_orlp_;