Constraint for a max, number of overlapping tasks
Ongoing
I'm trying to write a constraint (for a task scheduling problem) where I want to say "a maximum of n tasks can overlap". I have the following variables,
x(i, j): Task j follows task i (variable)
T(i): Starting time of task i (parameter)
C(i): Duration of task i (variable)
Can someone from the community advise me on how to write a non-overlapping constraint to limit the number of simultaneous tasks to n (a parameter)?
Thank you.
-
Hi Charitha,
Given it is possible to process tasks in parallel in your model, one idea is to use a time-indexed formulation where the time is discretized and the binary decision variable \(x_{it}\) equals 1 if task \(i\) starts at time \(t\) and 0, otherwise.
Assuming task \(i\) is in processing at time \(t\), let us define the set \(S_{it}= \{t^{\prime}| t - p_i \leq t^{\prime} \leq t\}\) to include the set of possible discrete start times for task \(i\) with \(p_i\) being the processing time of task \(i\). To enforce the constraint that at most \(n\) tasks can be run in parallel, we can then implement the constraint as below:
\[\sum_i \sum_{t^{\prime} \in S_{it}} x_{it^{\prime}} \leq n, ~~\forall t\]
Best regards,
Maliheh
0 -
Dear Maliheh, I thought about it, but the challenge is I have a large time horizon, and with other decision variables, the model becomes very expensive to run. Therefore, I'm looking for a strategy where I do not have to index each timestep but only model the start times and durations. So, in this case, (I think) depending on the value of n, I have to generate all possible combinations of tasks and check whether they overlap based on the start times and durations. Unfortunately, I'm struggling to put it into Gurobi syntax.
0 -
Hi Charitha,
As far as I know, the time-index formulation is the standard formulation to model the cumulative scheduling problem as a MIP.
So, in this case, (I think) depending on the value of n, I have to generate all possible combinations of tasks and check whether they overlap based on the start times and durations. Unfortunately, I'm struggling to put it into Gurobi syntax.
Generating all possible combinations of choosing \(n\) tasks from \(m\) tasks with \(m\) being the total number of tasks has a complexity of \(\mathcal{O}(m^n)\) and it might take so much time to enumerate all the combinations upfront. To address this issue, you can use callbacks to add these constraints lazily (see the article on How do I implement lazy constraints in Gurobi?). However, there is still one important issue: I am not sure how you can define a constraint using only the start time decision variables to limit the number of tasks running in parallel. You would need additional variables to determine whether two tasks overlap or not.
You might want to check the logic-based benders decomposition literature on cumulative scheduling problems that combine MIP and constraint programming (CP) for better performance.
Best regards,
Maliheh
0 -
Thanks a lot (also for the reference paper). I will study the problem a bit more with the paper you linked to as well and if I find a good, working solution I will post it here.
0 -
I think primary question is how many tasks is possible to model with time-indexed formulation and considered horizon in Gurobi. For me a few thousands tasks is a must.
Years ago I experimented with very large data and with constraint solver I was able to work with around 50 thousands tasks. But I was on a limit of algorithms used for cumulative constraint.
Is it possible to use Gurobi for large scheduling problems (with a lot of overlapping constraints) or Gurobi (and other LP/MIP solvers) simply cannot compete with constraint solvers or hybrid solvers (like cp-sat from ortools) in this area ?
0
Please sign in to leave a comment.
Comments
5 comments