# Formulate a constraint set to identify the number of overlapping operations

Let assume we have operation $$r \in R$$, machine $$n \in N$$ and day $$t \in T$$. $$S_{r}$$ is the service duration of operation $$r$$. Note that $$S_{r}$$ can be defined based on time slot (e.g., $$S_{1}$$ can be 2 time slots). In this problem, a machine can handle multiple operations at the same time.

$$y_{rnt}$$ is a binary variable indicating whether operation $$r$$ is allocated to machine $$n$$ on day $$t$$. $$a_{rt}$$ is a non-negative variable indicating the start time of serving operation $$r$$ on day $$t$$.

Given the above assumptions, how can I formulate a constraint set to restrict the number of overlapping operations on a machine to a predefined value of $$MR$$?

For more clarity, let us consider an example. For instance, we have 8 operations and one machine. If $$S_{1}=3$$, we should identify what operations overlap with operation $$r=1$$ during its service. Therefore, we should check three-time slots. The below example shows the overlapping operations with operation $$r=1$$, where each number represents an operation and each row represents overlapping operations at each time slot.

1, 2, 3, 4

1, 4, 5, 6

1, 5, 6, 7, 8

Let me know if you need further explanation. Thanks.

• You might find Erwin Kalvelagen's latest blog post useful: yetanothermathprogrammingconsultant.blogspot.com/2021/07/… Aug 2, 2021 at 20:52
• @RobPratt, thanks for the link. I looked at it. However, the author is using a time-slot-based binary decision variable, which is not usually ideal for scheduling problems. I can model this constraint with such a variable, but I would like to find a more efficient way. Aug 2, 2021 at 23:19
• "the author is using a time-slot-based binary decision variable, which is not usually ideal for scheduling problems" Quite the opposite. In many practical cases (but of course not all), a time-indexed formulation is the best performer. Aug 3, 2021 at 6:00
• Let $D$ be the set of time slots in a day. You can get what you want by adding $~2\cdot \vert R \vert \cdot \vert T \vert \cdot \vert D \vert$ binary variables, plus some continuous ones, but I don't see how that would be preferable to Erwin's approach.
– prubin
Aug 3, 2021 at 18:22