Re: [Help-glpk] Event Scheduling Question

[Andrew Makhorin]

> I am trying to construct a program of events for a little athletics
> centre.  Children in their respective agegroups/genders compete in
> selected events over a season of 16 weeks (i.e. COMPETITIONDAY = 16).
> 
> I have the following variables: 
> var eventstart{d in COMPETITIONDAY, (agegroup,eventid) in
> EVENTGROUPS}, >=competitondaystarttime[d],
> <=competitondayfinishtime[d];
> 
> var eventfinish{d in COMPETITIONDAY,(agegroup,eventid) in
> EVENTGROUPS}, <=competitondayfinishtime[d]; 
> var event{d in COMPETITIONDAY,(agegroup,eventid) in EVENTGROUPS},
> binary; 
> I need to ensure that events can't be scheduled simultaneously - i.e.
> an agegroup cannot be at 2 events at the same time.  There are no
> particular precedence constraints or due date requirements.  I am
> trying to maximize the number of events conducted for each agegroup
> across the season where each competition day is of a fixed duration.
> There are numerous other constraints regarding access to resources at
> the centre (i.e. the sprint track, the discus, etc.)
> 
> I am having a lot of trouble trying to work how to avoid conflicts.
> The following constraint is obviously incorrect for multiple reasons
> (i.e. strict inequality and invalid type due to trying to compare
> variables - as far as I understand).
> 
> s.t. ev{d in COMPETITIONDAY, (agegroup,eventid) in EVENTGROUPS}:
> eventstart[d,agegroup,eventid] > {agegroup1 in ATHLETES:
> agegroup1<>agegroup} eventstart[d,agegroup1,eventid];
> 
> What I am trying to say here is that there can only be one agegroup
> undertaking a specific event during the time of that event.
> 
> I would appreciate any assistance or pointers to general formulations
> for this type of problem. 
> I acknowledge that this help forum may not be the most appropriate
> place for such a question and if so, would be grateful for any
> suggestions.
> 

Your problem is similar to the job-shop scheduling problem, at least in
that part, where some disjunctive resources (agegroups) should be
assigned to some activities (events). 

There exist two main ways to model disjunctive resources depending on
parameterization used. One way is to use continuous variables to model
starting times of activities and binary variables to model a linear
order for every disjunctive resource consumed/used by activities. See
the example model jssp.mod included in the glpk distribution (in
subdirectory examples). Another way is to use time-indexed formulation,
where the planning horizon is divided into intervals
T = { 1, 2, ..., n }, and binary variables are used to model starting
times of activities (e.g. x[j,t] = 1 means that job j starts at time t).

Please note that problems of this class have combinatorial structure and
therefore are usually hard.


Andrew Makhorin