constraint set for a scheduling problem with machine availability

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$$

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.

• 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. Jan 30 at 22:22
• This merely ensures $\delta_{j,i}$ is fixed with precedence. For start time your first two constraints should do the job Jan 30 at 22:25
• So, are you saying that my constraints are correct, but I should add those two constraints that you wrote up? Jan 30 at 22:26
• Check with those, if they work. And in your first two constraints don't think deltas are needed Jan 30 at 22:35
• 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? Jan 31 at 15:28

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)
;


The results would be:

VARIABLE u.L

tm1         tm2         tm3