[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Newbie scheduling problem question, contiguous time inte

From: Roland Roberts
Subject: Re: [Help-glpk] Newbie scheduling problem question, contiguous time interval constraints
Date: Tue, 28 May 2013 22:44:31 -0400
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130514 Thunderbird/17.0.6

On 05/28/2013 09:45 PM, Harley wrote:
Hi Roland,

Timetabling is a wonderfully complex problem to learn to use any modelling environment!

You can formulate constraints across the time periods ie. p, p-1, p-2 to ensure that the scheduled classes form blocks rather than allow splitting. Having done a number of timetabling and scheduling problems, there probably is another hard constraint or maybe a soft constraint with a substantial penalty to ensure that not more than one block per class can be scheduled on any one day. If that is a hard constraint for your problem, then you can simplify the formulation of the constraint to ensure that there are always contiguous class blocks.

There are examples out there for many formulations but if you define a start period, and end period variable for each class then the constraint could be that no of scheduled class modules = end_period for class c - start_period for class c + 1 for and given day d.

I understand this constraint in a general fashion. I'm having trouble converting it to code. I've probably tackled a harder problem than I should really be starting with :-(

If I think of the scheduling problem as this 4-dimensional array to fill in, X[c,g,p,d], then I have constraints like these

# All students have to be scheduled *something* for every period.
sum {c in classes, p in 1..26} X[c,g,d,p] = 26

# Math requires a minimum of 15 modules per week
sum {c in MATH, p in 1..26, d in 1..5} >= 15

Similar constraints apply for other classes, and the above is a bit abstract (there are actually multiple math classes and only certain student groups take certain ones).

I had though of formulating the problem as one of choosing starting periods for a particular (class,group,day) as p0[c,g,d] with a duration of n[c,g,d] then I get constraints like

p0[c,g,d] >= 1
# 6 hours in school 24 daily periods
p0[c,g,d] + n[c,g,d] <= 24

But I'm confused on how to connect the two sets of constraints. In the first formulation, p0 through p0+n are just indices in X.

I'm sure this is a matter of "you should read the manual about feature Q." It's also possible I'm trying to make the problem specification more compact than is really possible, but the set of classes is small (about 20), the number of student groups is small (about 12) and the periods and days are also small sets.

I'm also good with being told that I really need to work through some set of tutorial problems first (suggestions on which ones might be useful?). I know that I'm trying to jump straight to the problem I really want to solve and that I'm being impatient :-)


                       PGP Key ID: 66 BC 3B CD
Roland B. Roberts, PhD                             RL Enterprises
address@hidden                            6818 Madeline Court
address@hidden                           Brooklyn, NY 11220

reply via email to

[Prev in Thread] Current Thread [Next in Thread]