constraint set for a scheduling problem with machine availability

Question

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$

Answer 1

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.

Answer 2

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