I have a project that that have the problem of generating a weekly table table for a university course ,I would like to model it as an binary Linear programming problem.
Problem description: we have a set of sessions, a set of teachers, a set of students, a set of rooms and a set of time slots(for the whole week as an example 7 slots per day * 5 days = 35 slots), so that we must assign a session, a room, a teacher and a subset of students to a time slot satisfying certain constraints such that idle time for the students and the teacher is minimized (idle time is empty time between two sessions example there is a session in time slot 1 and 3 slot 2 is idle time) These constraints can be summed up as
- A teacher cannot be assigned to two different sessions at the same time.
- A room cannot accommodate two different sessions at the same time.
- A student (or group) cannot be assigned to two different sessions at the same time.
- all sessions must be taught to all the groups
- The daily workload of a teacher must not be exceeded.
for simplicity sake I have omitted some constraints(specific rooms and specific teachers for specific sessions) in hope that it will be easy to add after getting the general model
here is what i came up with
Sets of sessions $$S={s_1,s_2,\ldots ,s_n}$$ Sets of teachers $$E={e_1,e_2,\ldots ,e_m}$$ Sets of rooms $$R={r_1,r_2,\ldots ,r_k}$$ Sets of Time Slots $$H={h_1,h_2,\ldots ,h_l}$$ Sets of Student Groups $$G={g_1,g_2,\ldots ,g_o}$$
decision variable $$X_{i,j,x,y,z}= \begin{cases} 1 & If\ session\ i\ is\ taught\ by\ teacher\ j\ in\ room\ x\ in\ Time\ slots\ y\ with\ group\ z \\ 0 & otherwise \\ \end{cases} $$
$$ Min\ Z=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x=1}^{k}\sum_{y=1}^{l}\sum_{z=1}^{o}X_{i,j,x,y,z} $$ $$S.t$$ $$ \sum_{i=1}^{n}\sum_{x=1}^{k}\sum_{y=1}^{l}\sum_{z=1}^{o}{X_{i,j,x,y,z}\le1\ \ \ \ pour\ j=1..m}\leftrightarrow\ contraint\ 1 $$ $$ \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{y=1}^{l}\sum_{z=1}^{o}{X_{i,j,x,y,z}\le1\ pour\ x=1..k}\leftrightarrow\ contraint\ 2 $$ $$ \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x=1}^{k}\sum_{y=1}^{l}{X_{i,j,x,y,z}\le1\ pour\ z=1..o}\leftrightarrow\ contraint\ 3 $$
the objective function above is just a place holder how do I go about writing an objective function that calculates idle time from the decision variables ?
how do I go about writing the remaining constraints?
also references or books about this genre of problems would be appreciated.