2
$\begingroup$

I have a set of tasks $I$ with processing times $p_i, \forall i \in I$. There exists a set of machines $M$ and each machine has availability time ranges in a given time horizon.

For instance, given a machine $m$ and a time horizon $100$ hours, $m$ might be available between $a_{m1} =[0,10]$, $a_{m2} =[20,40]$ and $a_{m3} =[75,95]$. Let $A_{m}$ represents the set of time slots for machine $m$. I'll use $+$ and $-$ for the upper and lower limit for each range. Note that another machine could have a completely different time slot availability.

The goal is to capture the precedence relationship for the tasks where no multiple task is processed on the same machine at the same time. Let us define three variables:

$t_i$ : the start time of processing part $i$

$\delta_{ij}$ : whether part $i$ precedes part $j$

$u_{ima}$ : whether part $i$ is processed on machine $m$ during shift $a$

Here are the constraints that I come up with so far.

$t_i \geq t_j + p_j - M (2-u_{ima} -u_{jma} + \delta_{ij})$

$t_j \geq t_i + p_i - M (2-u_{ima} -u_{jma} + 1- \delta_{ij})$

These constraints above state that if $i$ precedes $j$ on the same machine, then the start time of $j$ must be greater than the completion time of $i$. The confusing part is the availability range here. I don't think that it captures what I'd like. I was wondering if there's an easy fix or if I'm on the right track. Should I sum over $a$ each variable $u_{ima}$? Please note that I do not want to consider each time slot as an individual machine. Even though it would resolve the issue, I have other set of constraints that I do not share here.

To make sure that lower and upper bound of each availability time range is met, I have the following constraints.

$t_i + p_i \leq a^+ u_{ima} + M(1-u_{ima} ) \quad \forall i \in I, m \in M, a \in A_{m}$

$t_i \geq a^- u_{ima} + M(1-u_{ima} ) \quad \forall i \in I, m \in M, a \in A_{m}$

I can also add another constriant to ensure that each part is assigned to one machine.

$\sum_{m \in M} \sum_{a \in A{m}}u_{ima} =1, \quad \forall i \in I$

$\endgroup$

2 Answers 2

-1
$\begingroup$

It isn't abt not scheduling $i$ and $j$ in the same slit. It's more about preserving the precedence even when assigned on different slots. So
$u_{jma}\le \sum_m \sum_{a^{*+}\le a} u_{i,m,a^{*+}}+M(1-\delta_{i,j}) $
$u_{ima} \le \sum_m\sum_{a^{*+}\le a} u_{j,m,a^{*+}}+M\delta_{i,j} $

You may remove the $u_{ima}$ in the first 2 constraints.

$\endgroup$
8
  • $\begingroup$ This does not capture the start time of the parts tho. Also, parts can be processed on the same machine if there is enough time within the same slot. $\endgroup$
    – ball_jan
    Jan 30 at 22:22
  • $\begingroup$ This merely ensures $\delta_{j,i}$ is fixed with precedence. For start time your first two constraints should do the job $\endgroup$
    – Sutanu
    Jan 30 at 22:25
  • $\begingroup$ So, are you saying that my constraints are correct, but I should add those two constraints that you wrote up? $\endgroup$
    – ball_jan
    Jan 30 at 22:26
  • $\begingroup$ Check with those, if they work. And in your first two constraints don't think deltas are needed $\endgroup$
    – Sutanu
    Jan 30 at 22:35
  • $\begingroup$ In your post, you say that I should remove u, but in the comment section, you mention that I should remove $\delta$. Which one is correct? $\endgroup$
    – ball_jan
    Jan 31 at 15:28
-1
$\begingroup$

One possible way to assign tasks to the machines w.r.t the time slots is to redefine the sets and some constraints in addition to other models' constraints as follows:

  • $\text{Set} \ Tasks = \{1 \cdots \text{I} \}.$
  • $\text{Set} \ Machines = \{1 \cdots \text{M} \}.$
  • $\text{Set} \ TimeSlots= \{1 \cdots \text{T} \}.$
  • $\text{Set} \ Map_{(Tasks , Machines)}= \{1.(1, \cdots, T), \cdots, \text{M}.(1, \cdots, T) \}.$
  • $\text{P}_{tasks} = \text{The processing time of tasks i}.$
  • $\text{TimeSlotDuration}_{TimeSlots} = \text{The available time in each timeslot t}.$
  • $U_{tasks, machines, timeslots} = \text{whether part i is processed on machine m during timeslot t}$

Constraints:

$$ \sum_{m,t} u(i,m,t) = 1 \quad\forall i \in I \quad (1)$$ $$ \sum_{i,t} u(i,m,t) \leq | \ I \ | \quad\forall m \in M \quad (2)$$ $$ \sum_{i} u(i,m,t)*P(i) \leq TimeSlotDuration(t) \quad\forall m \in M, t \in T : map(m,t) \quad (3)$$

The first constraint implies that each task should be processed on one machine at one time slot. The second constraint ensures that each machine might process all of the tasks at one time slot. The third constraint implies that the processing time of the tasks at each time slot and in each machine would be less equal than the available time for each time slot. As the simple example:

set tasks =  {task1*task5};
set machines {m1*m3};
set timeslot {tm1*tm3};

parameter timeslotduration(t)
tm1 20
tm2 35
tm3 25
;

parameter p(i)
task1 15
task2 25
task3 25
task4 5
task5 10 
;

The results would be:

VARIABLE u.L  

                 tm1         tm2         tm3

task1.m1       1.000
task2.m1                   1.000
task3.m3                               1.000
task4.m1       1.000
task5.m2                   1.000

 
$\endgroup$
3
  • $\begingroup$ Thanks. Does this work when each machine has multiple time slots as explained in my post? Also, how do we keep track of the start time of each task? $\endgroup$
    – ball_jan
    Feb 1 at 15:40
  • $\begingroup$ @ball_jan, yeah. As you can see on the definition we have multiple time slots on the machines. Also, it would be worth to try adapting this w.r.t the rest of the model constraints. 😀 $\endgroup$
    – A.Omidi
    Feb 1 at 19:09
  • $\begingroup$ Yes, but the problem is that each machine could have different time slots and we need to see which job is processed on which machine at which time period. $\endgroup$
    – ball_jan
    Feb 1 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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