1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ You might find Erwin Kalvelagen's latest blog post useful: yetanothermathprogrammingconsultant.blogspot.com/2021/07/… $\endgroup$
    – RobPratt
    Aug 2 at 20:52
  • $\begingroup$ @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. $\endgroup$
    – mdslt
    Aug 2 at 23:19
  • 3
    $\begingroup$ "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. $\endgroup$ Aug 3 at 6:00
  • $\begingroup$ 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. $\endgroup$
    – prubin
    Aug 3 at 18:22
2
$\begingroup$

This seems to be a job shop scheduling problem. I am not expert in this problem, but in the job shop scheduling problem, the preventions of overlapping operations is one of the main constraints. You may use such a constraint and instead of setting the RHS of the inequality to zero (which states that overlapping is not allowed), you set your upper bound to the number of allowable overlapping operations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.