Example 4.22 Scheduling Course - Teacher Combinations

This example demonstrates the use of PROC CPM for a typical scheduling problem that may not necessarily fit into a conventional project management scenario. Such problems abound in practice and can usually be solved using a mathematical programming model. Here, the problem is modeled as a resource-allocation problem using PROC CPM, illustrating the richness of the modeling environment that is available with the SAS System. (Refer also to Kulkarni (1991) and SAS/OR Software: Project Management Examples for another example of course scheduling using PROC CPM.)

A committee for academically gifted children wishes to conduct some special classes on weekends. There are four subjects that are to be taught and a number of teachers available to teach them. Only certain course-teacher combinations are allowed. There is a constraint on the number of rooms that are available and some teachers may not be able to teach at certain times. Possible class times are one-hour periods between 9 a.m. and 12 noon on Saturdays and Sundays. The goal is to determine a feasible schedule of classes specifying the teacher that is to teach each class.

Suppose that there are four courses, c1, c2, c3, and c4, and three teachers, t1, t2, and t3. There are several ways of modeling this problem; one possible way is to form distinct classes for each possible course-teacher combination and treat each of these as a distinct activity that needs to be scheduled. For example, if course c1 can be taught by teachers t1, t2, and t3, define three activities, 'c1t1', 'c1t2', and 'c1t3'. The resources for this problem are the courses, the teachers, and the number of rooms. In particular, the resources needed for a particular activity, say, 'c1t3', are c1 and t3.

The following constraints are imposed:

• Course 1 can be taught by Teachers 1, 2, and 3; Course 2 can be taught by Teachers 1 and 3; Course 3 can be taught by Teachers 1, 2, and 3; and Course 4 can be taught by Teachers 1 and 2.

• The total number of classes taught at any time cannot exceed NROOMS.

• Class 'citj' (if such a course-teacher combination is allowed) can be taught only at times when teacher tj is available.

• At any given time, a teacher can teach only one class.

• At any given time, only one class is to be taught for any given course.

The following program uses PROC CPM to schedule the classes. The schedule is obtained in terms of unformatted numeric values; the times 1, 2, 3, 4, 5, and 6 are interpreted as the six different time slots that are possible, namely, Saturday 9, 10, and 11 a.m. and Sunday 9, 10, and 11 a.m.

The data set CLASSES is the Activity data set, and it indicates the possible course-teacher combinations and identifies the specific room, teacher, and course as the resources required. For each activity, the duration is 1 unit. Note that, in this example, there are no precedence constraints between the activities; the resource availability dictates the schedule entirely. However, there may be situations (such as prerequisite courses) that impose precedence constraints.

The Resource data set, RESOURCE, specifies resource availabilities. The period variable, per, indicates the time period from which resources are available. Since only one class corresponding to a given course is to be taught at a given time, the availability for c1 – c4 is specified as '1'. Teacher 2 is available only on Sunday; thus, specify the availability of t2 to be 1 from time period 4. The total number of rooms available at a given time is three. Thus, no more than three classes can be scheduled at a given time.

In the invocation of PROC CPM, the STOPDATE= option is used in the RESOURCE statement, thus restricting resource constrained scheduling to the first six time periods. Not all of the specified activities may be scheduled within the time available, in which case the unscheduled activities represent course-teacher combinations that are not feasible under the given conditions. The schedule obtained by PROC CPM is saved in a data set that is displayed, in Output 4.22.1, after formatting the activity names and the schedule times appropriately. Note that, in this example, all the course-teacher combinations are scheduled within the two-day time period.

title 'Scheduling Course / Teacher Combinations';
data classes;
   input class $  succ $ dur  c1-c4  t1-t3  nrooms;
   datalines;
c1t1  .   1   1  .  .  .  1  .  .   1
c1t2  .   1   1  .  .  .  .  1  .   1
c1t3  .   1   1  .  .  .  .  .  1   1
c2t1  .   1   .  1  .  .  1  .  .   1
c2t3  .   1   .  1  .  .  .  .  1   1
c3t1  .   1   .  .  1  .  1  .  .   1
c3t2  .   1   .  .  1  .  .  1  .   1
c3t3  .   1   .  .  1  .  .  .  1   1
c4t1  .   1   .  .  .  1  1  .  .   1
c4t2  .   1   .  .  .  1  .  1  .   1
;

data resource;
   input per c1-c4  t1-t3  nrooms;
   datalines;
1       1   1  1  1  1  .  1   3
4       .   .  .  .  .  1  .   .
;
   

proc cpm data=classes out=sched
     resin=resource;
   activity   class;
   duration   dur;
   successor  succ;
   resource   c1-c4 t1-t3 nrooms / period=per stopdate=6;
   run;

proc format;
   value classtim
      1 = 'Saturday  9:00-10:00'
      2 = 'Saturday 10:00-11:00'
      3 = 'Saturday 11:00-12:00'
      4 = 'Sunday    9:00-10:00'
      5 = 'Sunday   10:00-11:00'
      6 = 'Sunday   11:00-12:00'
      7 = 'Not Scheduled'
      ;
   value $classt
      c1t1 = 'Class 1, Teacher 1'
      c1t2 = 'Class 1, Teacher 2'
      c1t3 = 'Class 1, Teacher 3'
      c2t1 = 'Class 2, Teacher 1'
      c2t2 = 'Class 2, Teacher 2'
      c2t3 = 'Class 2, Teacher 3'
      c3t1 = 'Class 3, Teacher 1'
      c3t2 = 'Class 3, Teacher 2'
      c3t3 = 'Class 3, Teacher 3'
      c4t1 = 'Class 4, Teacher 1'
      c4t2 = 'Class 4, Teacher 2'
      c4t3 = 'Class 4, Teacher 3'
      ;

data schedtim;
set sched;
format classtim classtim.;
format class    $classt.;
if (s_start <= 6) then classtim = s_start;
else                   classtim = 7;
run;

title2 'Schedule of Classes';
proc print;
   id class;
   var classtim;
   run;

data resourc2;
   input per c1-c4  t1-t3  nrooms;
   datalines;
1       1   1  1  1  1  .  1   1
2       .   .  .  .  .  .  .   3
3       .   .  .  .  .  .  .   2
4       .   .  .  .  .  1  .   1
5       .   .  .  .  .  .  .   3
;

proc cpm data=classes out=sched2
     resin=resourc2;
   activity   class;
   duration   dur;
   successor  succ;
   resource   c1-c4 t1-t3 nrooms / period=per stopdate=6;
   run;

data schedtim;
set sched2;
format classtim classtim.;
format class    $classt.;
if (s_start <= 6) then classtim = s_start;
else                   classtim = 7;
run;

title2 'Alternate Schedule with Additional Constraints';
proc print;
   id class;
   var classtim;
   run;