CODEWITHSUNDEEP
pythonmathematical-optimizationpulp
or-math
or-math

Reputation: 3

How to add PuLP constraints over time ranges which aren't modeled as variables

I'm currently working on a complex scheduling problem involving a large number of parameters and decision variables. In short, I'm trying to schedule resources to tasks based on capacity, complexity, available time, and potential completion time.

I have a matrix, Av,j,t which determines how many resources are assigned to job j on project v at time t, as well as variables Sv,j and Ev,j which determine the start and end times of each job by project. Mathematically, the constraints all make sense, but I'm having a lot of trouble modeling a few in particular.

To ensure that job allocations only occur between start and end periods for the job, I've enforced the constraints:

pulp.lpSum([A[t][v][j] for t in [t0 for t0 in T if t0 >= S[v][j]]]) == P[v][j]
pulp.lpSum([A[t][v][j] for t in [t0 for t0 in T if t0 <= S[v][j] - 1]]) == 0
pulp.lpSum([A[t][v][j] for t in [t0 for t0 in T if t0 >= E[v][j] + 1]]) == 0

where Pv,j is the total time a task takes with a single resource. My primary issue with constraints of this kind are that the start and end times are model variables, while T (the set of times), is not. Trying to enforce this constraint in the model proves problematic, because Sv,j isn't really "initialized" at the time the constraints are set, so this constraint isn't actually doing anything as the set

[t0 for t0 in T if t0 >= S[v][j]]

doesn't change with the model. I've also got an indicator set to track job completion, Xv,j,t, which is 1 for t > Ev,j and 0 otherwise. I've tried to enforce this in a number of ways, but all of them rely on sums of sets of t in T, which don't adjust when the model adjusts.

Does anyone have any ideas on how I can force these sets to adjust with the model itself?

Upvotes: 0

Views: 284

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

All constraints need to be linear. What you try to specify is non-linear so not allowed.

Instead, you need to model something like:

                       t   1 2 3 4 5 6 7 8 9 10 11
   job is executing  x(t)  0 0 0 0 1 1 1 1 0 0 0 
   job is starting   s(t)  0 0 0 0 1 0 0 0 0 0 0

This can be modeled as:

   s(t) >= x(t)-x(t-1)
   sum(t, s(t)) <= 1      (one start allowed)
   sum(t, x(t)) = joblen

To get the start and end time:

   S = sum(t, t*s(t));
   E = S + joblen - 1

This is a fairly standard approach. It may be mentioned in your textbook.

Upvotes: 2

Related Questions