Topic
  • 1 reply
  • Latest Post - ‏2013-05-10T10:59:45Z by rdumeur
Ran21
Ran21
1 Post

Pinned topic help with a schedule modling

‏2013-05-09T23:03:09Z |

I'm scheduling lessons in a class room. The students learn 5 days a week but a certain teacher works only 4 days a week. The day off is nto predefined - the optimizer should give him a day off.

I tried doing it with IloElement, where an int var day == ilodiv(start_of_interval,24) is used in the element into an array of ints with a constraint that enforces the var in the last array corresponding to the day to 1. The sum of the last array =4.

This seams to cause very slow optimizations.

is there a better way?

  • rdumeur
    rdumeur
    111 Posts

    Re: help with a schedule modling

    ‏2013-05-10T10:59:45Z  

    Dear Ran21,

    Are you using interval variables to model your scheduling problem?

    If so, the following (very simplified) model can give you an idea of how using "alternative" and "span" constraints on optional intervals may help you.

    The idea here is to consider days as optional intervals, and while allowing any course to happen during any day, impose the fact that the number of "present" days (days of work) must be equals to (<number of days> -1). Hi hope this helps!

     

    Cheers,

    --------------- model begins here --------------

     

    using CP;
    int nc = 10; // number of courses
    int nd = 5; // number of days
    dvar interval days[1..nd] optional size 8;
    dvar interval courses[1..nc] size 1;
    dvar interval day_course[1..nd][1..nc] optional;
    constraints {
      // one course happens on a certain day
      forall(c in 1..nc) {
        alternative(courses[c], all(d in 1..nd) day_course[d][c]);
      }
      // a course happens during a day
      forall(d in 1..nd) {
        if(d > 1) endBeforeStart(days[d-1],days[d]); // order days... for presentation
        span(days[d], all(c in 1..nc) day_course[d][c]);
      }
      // cannot teach two courses at the same time    
      noOverlap(courses);
      // days do not overlap either.
      noOverlap(days);
      // ensure that there is one day off.
      nd-1 == sum(d in 1..nd) presenceOf(days[d]);
    }