Lindo Systems
! The standard school day scheduling problem:
Given a set of rooms, a set of students/participants,
a set of periods, a set of courses/meetings/exams, and a set of teachers
with expertise in one or more courses, the single day
school time table model makes the assignments:
teacher to course to section to period to room, as well as assignments:
student to course to section to period to room,
so that among other considerations, each:
teacher teaches at most one course in a given period,
student takes at most one course in a given period,
room contains at most one course in a given period,
student is assigned, if possible, to every course s/he wants,
teacher teaches only courses s/he is qualifed to teach,
course section is assigned only to a room that is suited to that course,
no more students are assigned to a course section than
the associated room can hold,
course, e.g., lunch, is assigned only to a period in which it is allowed
to be assigned.
This simple model assumes each teacher can teach in any period and
each student can take a course in any period.
"Course conflicts" are automatically taken into account, i.e., if lots
of students want to take both course c1 and c2,
then c1 and c2 will be assigned to different periods.
With suitable modifications, this model can solve much larger
and realistic versions of the school scheduling problem;
! Keywords: School scheduling, Scheduling, Time tabling, Course scheduling, Education,
Room assignment, Meeting planning, Exam scheduling;
SETS:
! Primitive sets;
PERIODS;
COURSES:
minNoOfSections,
maxNoOfSections,
Slkc;
TEACHERS:
maxNoOfPeriodsPerDay;
STUDENTS;
ROOMS:
capacity; ! Capacity of this room;
! Derived sets;
TEACHER_PERIOD(TEACHERS, PERIODS):
tpPref;
COURSE_PERIOD(COURSES, PERIODS);
COURSE_ROOM(COURSES, ROOMS);
TEACHER_COURSE (TEACHERS, COURSES):
tcPref;
STUDENT_COURSE(STUDENTS, COURSES) :
scPref;
T_C_P(TEACHERS, COURSES, PERIODS)
| @IN(TEACHER_COURSE, &1, &2)
#AND#
@IN(COURSE_PERIOD, &2, &3):
X;
S_C_P( STUDENTS, COURSES, PERIODS)
| @IN(STUDENT_COURSE, &1, &2)
#AND#
@IN(COURSE_PERIOD, &2, &3) :
Y;
R_C_P( ROOMS, COURSES, PERIODS)
| @IN(COURSE_ROOM, &2, &1)
#AND#
@IN(COURSE_PERIOD, &2, &3) :
Z;
ENDSETS
DATA:
! Periods of the day;
PERIODS = P1 P2 P3 P4 P5 P6;
! Courses to be taught;
COURSES, minNoOfSections, maxNoOfSections=
Chem 1 2
Biol 1 2
Phys 1 1
PhEd 2 2
Lnch 2 2;
TEACHERS, maxNoOfPeriodsPerDay =
Pauling 3
DarwinC 3
Einstin 2
PhelpsM 2;
STUDENTS =
Tommy
Dicky
Harry
Emily
Lizzy
Ellie
Olive
Frank
Grace
Mitch ;
ROOMS, capacity=
Lab1 4
Lab2 5
Lab3 7
Hall 9
Cafe 7;
COURSE_PERIOD =
Chem P1
Chem P2
Biol P2
Biol P3
Phys P5
Phys P6
PhEd P4
PhEd P6
Lnch P3
Lnch P4 ;
COURSE_ROOM =
Chem Lab1
Chem Lab2
Biol Hall
Biol Lab3
Phys Lab1
Phys Lab3
PhEd Hall
Phed Lab2
Lnch Cafe ;
! Teachers, courses they can teach, & preferences;
TEACHER_COURSE, tcPref =
Pauling Chem 10
Pauling Biol 5
Pauling Lnch 1
DarwinC Biol 10
DarwinC Phys 1
DarwinC Lnch 1
Einstin Phys 10
Einstin Chem 4
Einstin Lnch 1
PhelpsM PhEd 9
PhelpsM Biol 2
PhelpsM Lnch 1;
! Students, courses need to take & preference;
STUDENT_COURSE, scPref =
Tommy PhEd 9
Tommy Chem 2
Tommy Biol 3
Tommy Lnch 10
Dicky Phys 10
Dicky Chem 9
Dicky Biol 8
Dicky Phed 1
Dicky Lnch 2
Harry Chem 10
Harry Biol 4
Harry PhEd 5
Harry Lnch 6
Emily Biol 10
Emily Phys 8
Emily Lnch 4
Lizzy PhEd 10
Lizzy Biol 9
Lizzy Lnch 8
Lizzy Chem 6
Ellie PhEd 10
Ellie Biol 9
Ellie Lnch 8
Olive Chem 4
Olive Biol 8
Olive Lnch 5
Frank Biol 8
Frank Chem 7
Frank Phys 6
Frank Lnch 4
Grace Biol 8
Grace Chem 7
Grace Phys 6
Mitch PhEd 10
Mitch Lnch 9
Mitch Biol 8;
WgtTch = 1; ! Wgt given to teacher course preferences;
WgtStu = 1; ! Wgt given to student course preferences;
ENDDATA
! Variables:
X(t,c,p) = # times teacher t is teaching course c in period p
Y(s,c,p) = # times student s is taking course c in period p
Z(r,c,p) = # times room type r is assigned to course c in period p;
! This model assigns the teachers, students, & rooms to course and period combinations.;
SUBMODEL Assignm:
! Assign teachers, students, and rooms to courses and periods;
MAX = TotVal;
TotVal = WgtTch* TchTot + WgtStu*StuTot;
TchTot =@SUM( T_C_P(t,c,p): X(t,c,p) * tcPref(t,c));
StuTot =@SUM( S_C_P(s,c,p): Y(s,c,p) * scPref(s,c));
! Teacher constraints;
! Teacher t can teach only one course c in period p;
@FOR( TEACHER_PERIOD(t,p):
[Tchp] @SUM( T_C_P(t,c,p): X(t,c,p)) <= 1;
);
@FOR( T_C_P(t,c,p): @BIN(X(t,c,p))); !Make 0 or 1;
! Teacher t can teach a limited number of sections per day;
@FOR( TEACHERS( t):
[Tchd] @SUM( T_C_P(t,c,p): X(t,c,p)) <= maxNoOfPeriodsPerDay(t);
);
! Student constraints;
! Each student s can take only one course c in period p;
@FOR( STUDENTS(s):
@FOR( PERIODS(p):
[Stup] @SUM( COURSES( c) | @IN( S_C_P, s, c, p): Y(s,c,p)) <= 1;
);
);
@FOR( S_C_P(s,c,p) : @BIN(Y(s,c,p)));
! Each student s can take course c at most once;
@FOR( STUDENT_COURSE(s,c):
[Stuc] @SUM( PERIODS( p) | @IN( S_C_P, s, c, p) : Y(s,c,p)) <= 1;
);
! Room constraints;
! Rooms r can do only one thing c in period p;
@FOR( ROOMS(r):
@FOR( PERIODS(p):
[Rmp] @SUM( COURSES( c) | @IN( R_C_P, r,c,p): Z(r,c,p)) <= 1;
);
);
! Course constraints;
@FOR(COURSES(c):
! Max number per day;
[maxSections]
@SUM( R_C_P(r,c,p): Z(r,c,p)) + SLKc(c) = maxNoOfSections(c);
[minSections]
SLKc(c) <= MaxNoOfSections(c) - minNoOfSections(c);
);
! Room to teacher constraints;
! # teachers teaching course c in period p = number rooms assigned to c in p;
@FOR( COURSE_PERIOD(c,p):
[RmTch] @SUM( T_C_P(t,c,p): X(t,c,p)) = @SUM( R_C_P(r,c,p): Z(r,c,p));
);
! Room to student constraints;
! # students taking course c in period p <= room capacity assigned to c in p;
@FOR( COURSE_PERIOD(c, p):
[RmStu] @SUM( STUDENTS( s) | @IN( S_C_P,s,c,p): Y(s,c,p)) <=
@SUM( ROOMS( r) | @IN( R_C_P,r,c,p): capacity(r)*Z(r,c,p));
);
ENDSUBMODEL
CALC:
@SET('TERSEO', 2); ! Output level (0:verbose, 1:terse, 2:errors only, 3:no output);
! Solve the model;
@SOLVE(Assignm);
! Output the teacher schedule;
@WRITE('School Schedule:', @NEWLINE(1));
@WRITE(' Teacher Period Course', @NEWLINE(1));
@FOR( T_C_P(t,c,p) | X(t,c,p) #GT# 0.5:
@WRITE(' ',TEACHERS(t),' ', PERIODS(p),' ', COURSES(c), @NEWLINE(1));
);
@WRITE( @NEWLINE(1));
! Output the room schedule;
@WRITE(' Room Period Course', @NEWLINE(1));
@FOR( R_C_P(r,c,p) | Z(r,c,p) #GT# 0.5:
@WRITE(' ',ROOMS(r),' ', PERIODS(p),' ', COURSES(c), @NEWLINE(1));
);
@WRITE( @NEWLINE(1));
! Output the student schedule;
@WRITE(' Student Period Course', @NEWLINE(1));
@FOR( S_C_P(S,c,p) | Y(s,c,p) #GT# 0.5:
@WRITE(' ',STUDENTS(s),' ', PERIODS(p),' ', COURSES(c), @NEWLINE(1));
);
@WRITE( @NEWLINE(1));
@WRITE(' Teacher pref value granted: ', TchTot, @NEWLINE(1));
@WRITE(' Student pref value granted: ', StuTot, @NEWLINE(1));
@WRITE(' Total Value : ', TotVal, @NEWLINE(1));
ENDCALC
END