FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Timetable for courses and teachers

Description
We want to establish the weekly timetable for two classes of a college. The two classes have the same teachers, except for mathematics and sport. All lessons have a duration of two hours. All students of the same class attend exactly the same courses. Every class may only have one two-hour lesson per subject on a single day. Some teachers are only available on certain days. Some time slots are reserved for certain subjects.

Further explanation of this example: 'Applications of optimization with Xpress-MP', Section 14.3 'Establishing a college timetable' (i3school.mos)

timetablegr.zip[download all files]

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.
timetable_graph.mos[download]

Data Files





timetable_graph.mos

(!******************************************************
   Mosel Example Problems
   ======================

   file timetable.mos
   ``````````````````
   TYPE:         Timetabling problem
   DIFFICULTY:   2
   FEATURES:     MIP problem, many specific constraints, tricky (pseudo-)
                 objective function, `finalize'
   DESCRIPTION:  We want to establish the weekly timetable for two classes of 
                 a college. The two classes have the same teachers, except 
                 for mathematics and sport. All lessons have a duration of 
                 two hours. All students of the same class attend exactly 
                 the same courses. Every class may only have one two-hour 
                 lesson per subject on a single day. Some teachers are only
                 available on certain days. Some time slots are reserved
                 for certain subjects.     
   FURTHER INFO: `Applications of optimization with Xpress-MP', 
                 Section 14.3 `Establishing a college timetable' 
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, 2002, rev. Sep. 2017
*******************************************************!)

model "School timetable"
 uses "mmxprs", "mmsvg"

 declarations
  TEACHERS: set of string         ! Set of teachers
  CLASS = 1..2                    ! Set of classes
  NP = 4                          ! Number of time periods for courses
  ND = 5                          ! Days per week
  SLOTS=1..NP*ND                  ! Set of time slots for the entire week
  
  COURSE: array(TEACHERS,CLASS) of integer ! Lessons per teacher and class
 end-declarations

 initializations from 'timetable.dat'
  COURSE
 end-initializations

 finalize(TEACHERS)

 declarations
  teach: array(TEACHERS,CLASS,SLOTS) of mpvar 
                                  ! teach(t,c,l) = 1 if teacher t gives a
                                  ! lesson to class c during time period l
 end-declarations

! Objective: number of "holes" in the class timetables
 Hole:= 
  sum(t in TEACHERS, c in CLASS, d in 0..ND-1) (teach(t,c,d*NP+1) + 
      teach(t,c,(d+1)*NP))

! Plan all courses
 forall(t in TEACHERS, c in CLASS) 
  PlanAll(t,c):= sum(l in SLOTS) teach(t,c,l) = COURSE(t,c)

! For every class, one course at a time
 forall(c in CLASS, l in SLOTS) 
  OneCourseClass(c,l):= sum(t in TEACHERS) teach(t,c,l) <= 1

! Teacher teaches one course at a time
 forall(t in TEACHERS, l in SLOTS) 
  OneCourseTeacher(t,l):= sum(c in CLASS) teach(t,c,l) <= 1

! Every subject only once per day
 forall(t in TEACHERS, c in CLASS, d in 0..ND-1) 
  OncePerDay(t,c,d):= sum(l in d*NP+1..(d+1)*NP) teach(t,c,l) <= 1
 
! Sport Thursday afternoon (slot 15)
 teach("Mr Muscle",1,15) = 1
 teach("Mrs Biceps",2,15) = 1
 
! No course during first period of Monday morning
 forall(t in TEACHERS, c in CLASS) teach(t,c,1) = 0

! No course by Mr Effofecks Monday morning
 forall(l in 1..2) teach("Mr Effofecks",2,l) = 0
 
! No Biology on Wednesday
 forall(c in CLASS, l in 2*NP+1..3*NP) teach("Mrs Insulin",c,l) = 0 

 forall(t in TEACHERS, c in CLASS, l in SLOTS) teach(t,c,l) is_binary
 
! Solve the problem
 minimize(Hole)
 
! Solution printing
 declarations
  DAYS=1..ND
  NAMES: array(DAYS) of string
 end-declarations
 
 initializations from 'timetable.dat'
  NAMES
 end-initializations

 writeln("Courses at begin or end of day: ", getobjval)
 forall(c in CLASS) do
  writeln("Class ",c)
  forall(d in DAYS) do
   write(NAMES(d), ":  ")
   forall(l in (d-1)*NP+1..d*NP)
    if (getsol(sum(t in TEACHERS) teach(t,c,l))>0) then
     forall(t in TEACHERS)
      write( if(getsol(teach(t,c,l))>0, strfmt(t,-14), ""))
    else
     write(strfmt("",14))
    end-if     
   writeln 
  end-do
 end-do 

! Solution drawing
 forall(t in TEACHERS) do
   svgaddgroup(t,t)
   svgsetstyle(SVG_FILL,SVG_CURRENT)
   svgsetstyle(SVG_STROKE,SVG_GREY)
 end-do
 svgaddgroup("msg","text",SVG_BLACK)

 pos:=CLASS.size*NP+5
 svgsetgraphviewbox(0,0,ND*2+2,pos+2)
 svgsetgraphscale(20)

 forall(c in CLASS) do
  svgaddtext("msg", 0, pos, "Class "+c)
  svgsetstyle(svggetlastobj, SVG_FONTWEIGHT, "bold")
  pos-=1
  forall(d in DAYS) do
   svgaddtext("msg", d*2+1,pos+0.2,NAMES(d))
   svgsetstyle(svggetlastobj,SVG_TEXTANCHOR,"middle")
   forall(l in (d-1)*NP+1..d*NP) do
    if d=1 then svgaddtext("msg", 0,pos+0.2-(l-(d-1)*NP),"Slot "+l); end-if
    if (getsol(sum(t in TEACHERS) teach(t,c,l))>0) then
     forall(t in TEACHERS | getsol(teach(t,c,l))>0)
       svgaddrectangle(t, d*2, pos-(l-(d-1)*NP), 2, 1)
    end-if
   end-do
  end-do
  pos-=(NP+1)
 end-do 

 svgsave("timetable.svg")
 svgrefresh
 svgwaitclose("Close browser window to terminate model execution.", 1)
end-model

Back to examples browserPrevious exampleNext example