Re: Help solving a scheduling optimisation problem

Hello Joaquim,

I guess the constraints are easier to write, if a binary is 1 if it matches the first occupied timeslot of a job and zero for all other timeslots.

Best regards

Heinrich

Am 12.07.18, 23:34, "Joaquim Leitão" <[email protected]> schrieb:

Hi All,

I am fairly new to glpk and linear programming. I am working on a
scheduling problem, and have been facing some problems in the
specification of one of its constraints.

The variables in my problem are binary, encoding the schedule for a
given series of jobs. In my problem I have a total of n time
slots that can be used to schedule certain jobs: If I was
considering a total of three jobs I would have three sets of
variables - xA, xB and xC, all of dimension n -, and for a
given index i (1 <= i <= n) if xA[i] = 1 then job A
would be scheduled for time slot i.

My problem is related to the fact that, while some jobs only require
one time slot to complete; others may require multiple, consecutive
time slots. Imagine that a given job - job B, for example - requires
2 time slots. I know that xB must only take the value "1" in 2
consecutive time slots, taking the value "0" in the remaining (n-2)
slots. But how can I write this as a problem constraint?

I have tried to make use of the exists keyword but as far as
I can understand I cannot use it in constraints in linear
problems... An obvious constraint that comes to mind is to make the
sum of xB for all i be equal to 2 (sum{i in 1..n} xB[i] =
2), but this only restricts the total number of assigned slots and
does not make them consecutive.

Any suggestions/comments are very welcome.

Best regards,

Joaquim

_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk

_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk