[Top][All Lists]

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

[Help-glpk] Help solving a scheduling optimisation problem

From: Joaquim Leitão
Subject: [Help-glpk] Help solving a scheduling optimisation problem
Date: Thu, 12 Jul 2018 22:34:04 +0100
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0

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,

reply via email to

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