# Decision Optimization

View Only

## Additional setup time due to secondary resource

• #### 1.  Additional setup time due to secondary resource

Posted Tue April 05, 2022 03:20 AM
Hi,

I'm currently working on a model with two sources of setup costs:
- when switching a secondary resource, which is a container that holds the parts to be processed

Here's a minimal working example:
``````from docplex.cp import model as cp
from random import randint, seed

jobs = [0, 1, 2, 3]
pod_capacity = 3
seed(1)

model = cp.CpoModel()

# Intervals: the jobs to be executed
its = [cp.interval_var(length=1, name=f'J{j}') for j in jobs]

# Ensure intervals do not overlap and add setup time between each interval
distance_matrix = [[randint(1, 5) for _ in range(len(jobs))] for _ in range(len(jobs))]
seq = cp.sequence_var(vars=its, name='Seq')

# Alternative intervals, one per available container
pod1_its = [cp.interval_var(optional=True, name=f'Pod1_J{j}') for j in jobs]
pod2_its = [cp.interval_var(optional=True, name=f'Pod2_J{j}') for j in jobs]

# Ensure one of the helper intervals is executed
for j in jobs:

# Ensure pods do not overlap
pod1_it = cp.interval_var(name='It_Pod1')
pod2_it = cp.interval_var(name='It_Pod2')

# Limit number of intervals per pod
model.add(cp.sum(cp.presence_of(it) for it in pod1_its) <= pod_capacity)
model.add(cp.sum(cp.presence_of(it) for it in pod2_its) <= pod_capacity)

solution = model.solve()
model.export_model()
solution.write()
``````

What I would like to achieve is having an additional constant setup time if the secondary resource (i.e. the pod) changes.

To give a specific example, this is the solution from the model above:

``````It_Pod1 = IntervalVarValue(start=11, end=12, size=1)
It_Pod2 = IntervalVarValue(start=0, end=7, size=7)
J0 = IntervalVarValue(start=0, end=1, size=1)
J1 = IntervalVarValue(start=6, end=7, size=1)
J2 = IntervalVarValue(start=2, end=3, size=1)
J3 = IntervalVarValue(start=11, end=12, size=1)
Pod1_J0 = ()
Pod1_J1 = ()
Pod1_J2 = ()
Pod1_J3 = IntervalVarValue(start=11, end=12, size=1)
Pod2_J0 = IntervalVarValue(start=0, end=1, size=1)
Pod2_J1 = IntervalVarValue(start=6, end=7, size=1)
Pod2_J2 = IntervalVarValue(start=2, end=3, size=1)
Pod2_J3 = ()
Seq = ['J0', 'J2', 'J1', 'J3']``````

Here, I would like to see that J3 starts at 12 instead of 11 because the pod changed between J1 and J3.

Any idea how to approach this?

Thanks
Sebastian

------------------------------
Sebastian Bayer
------------------------------

• #### 2.  RE: Additional setup time due to secondary resource

Posted Thu April 21, 2022 01:49 AM
Hello,

unfortunately I could not get anywhere with this topic. Does anyone in the community have any ideas on how to proceed here?

Thanks
Sebastian

------------------------------
Sebastian Bayer
------------------------------

• #### 3.  RE: Additional setup time due to secondary resource

Posted Thu April 21, 2022 04:06 AM
Dear Sebastian,

Maybe the solution would be to create a secondary sequence containing each pod interval from pod1_its and pod2_its and impose a transition time when type pod type changes:

`# create a sequence var for the containers`
`pods = [0, 1]`
`pod_seq = cp.sequence_var(vars=pod1_its + pod2_its, types=[0]*len(pod1_its) + [1]*len(pod2_its), name='PodSeq')`
`# transition time between different pods`
`pod_change_delay = 1`
`pod_distance_matrix = [ [0 if i == j else pod_change_delay for i in pods ] for j in pods ]`
`model.add(cp.no_overlap(sequence=pod_seq, distance_matrix=pod_distance_matrix))`

This way, the alternative constraints select appropriate intervals in the pod_seq sequence which obeys the transition times specified by the matrix (1 if pod changes else 0).

I hope this helps.
Cheers,

------------------------------
Renaud Dumeur
------------------------------

• #### 4.  RE: Additional setup time due to secondary resource

Posted Thu April 21, 2022 07:19 AM
Dear Renaud,

many thanks for taking time to reply!

Your suggestion does not work, unfortunately. The solution is still

``````Pod1_J0 = ()
Pod1_J1 = ()
Pod1_J2 = ()
Pod1_J3 = IntervalVarValue(start=11, end=12, size=1)
Pod2_J0 = IntervalVarValue(start=0, end=1, size=1)
Pod2_J1 = IntervalVarValue(start=6, end=7, size=1)
Pod2_J2 = IntervalVarValue(start=2, end=3, size=1)
Pod2_J3 = ()
PodSeq = ['Pod2_J0', 'Pod2_J2', 'Pod2_J1', 'Pod1_J3']
Seq = ['J0', 'J2', 'J1', 'J3']​``````

i.e., the start of Pod1_J3 is 11 and not 12.

I think the reason for this is that the setup time between the jobs is greater than the setup time between the pods. Thus, the additional constraint is always fulfilled.

Regards
Sebastian

------------------------------
Sebastian Bayer
------------------------------

• #### 5.  RE: Additional setup time due to secondary resource

Posted Thu April 21, 2022 09:27 AM
Dear Sebastian,

To check if this actually work, I suggest you try set the distance matrix for jobs to 0 and see the effect of the pods distance matrix.
Cheers,

------------------------------
Renaud Dumeur
------------------------------

• #### 6.  RE: Additional setup time due to secondary resource

Posted Thu April 21, 2022 09:33 AM
Dear Renaud,

it works perfectly the the distance between jobs is 0:

``````Pod1_J0 = IntervalVarValue(start=1, end=2, size=1)
Pod1_J1 = IntervalVarValue(start=2, end=3, size=1)
Pod1_J2 = IntervalVarValue(start=0, end=1, size=1)
Pod1_J3 = ()
Pod2_J0 = ()
Pod2_J1 = ()
Pod2_J2 = ()
Pod2_J3 = IntervalVarValue(start=4, end=5, size=1)
PodSeq = ['Pod1_J2', 'Pod1_J0', 'Pod1_J1', 'Pod2_J3']
Seq = ['J2', 'J0', 'J1', 'J3']​``````

In reality, however, the distance between jobs is unfortunately larger than the distance between secondary resources.

------------------------------
Sebastian Bayer
------------------------------

• #### 7.  RE: Additional setup time due to secondary resource

Posted Fri April 22, 2022 03:17 AM
Dear Sebastian,

So do you actually want both setups to be performed in sequence rather than in parallel?
Cheers,

------------------------------
Renaud Dumeur
------------------------------

• #### 8.  RE: Additional setup time due to secondary resource

Posted Fri April 22, 2022 03:44 AM
Dear Renaud,

yes exactly, this is a setup change that needs to run after the primary setups are performed, i.e. sequentially.

Best
Sebastian

------------------------------
Sebastian Bayer
------------------------------

• #### 9.  RE: Additional setup time due to secondary resource

Posted Fri April 22, 2022 05:56 AM
Edited by Hugues Juille Fri April 22, 2022 06:02 AM
Dear Sebastian,
After discussing with Renaud, we'd like to propose the following changes to your original model in order to take into account the additional setup times when changing pod:

```from docplex.cp import model as cp
from random import randint, seed
import numpy as np

jobs = [0, 1, 2, 3]
pod_capacity = 3
seed(1)

model = cp.CpoModel()

# Intervals: the jobs to be executed
its = [cp.interval_var(length=1, name=f'J{j}') for j in jobs]

# create a setup task for each job
setups = [cp.interval_var(length=1, optional=True, name=f'Setup{j}') for j in jobs]

#
for j in jobs:

# Ensure intervals do not overlap and add setup time between each interval
d_matrix = np.array([[randint(1, 5) for _ in range(len(jobs))] for _ in range(len(jobs))])
distance_matrix = np.vstack([np.hstack([d_matrix, d_matrix]), np.zeros((len(jobs), len(jobs)*2), dtype=np.int)])

print(distance_matrix)

seq = cp.sequence_var(vars=its + setups, name='Seq')

# Alternative intervals, one per available container
pod1_its = [cp.interval_var(optional=True, name=f'Pod1_J{j}') for j in jobs]
pod2_its = [cp.interval_var(optional=True, name=f'Pod2_J{j}') for j in jobs]

# Ensure one of the helper intervals is executed
for j in jobs:

# create a sequence var for the containers
pods = [0, 1]
pod_seq = cp.sequence_var(vars=pod1_its + pod2_its, types=[0]*len(pod1_its) + [1]*len(pod2_its), name='PodSeq')

for j in jobs:
model.add(cp.if_then(cp.logical_and(cp.presence_of(pod1_its[j]), cp.type_of_prev(pod_seq, pod1_its[j], 0) != 0), cp.presence_of(setups[j]) == 1))
model.add(cp.if_then(cp.logical_and(cp.presence_of(pod2_its[j]), cp.type_of_prev(pod_seq, pod2_its[j], 1) != 1), cp.presence_of(setups[j]) == 1))
model.add(cp.if_then(cp.logical_and(cp.presence_of(pod1_its[j]), cp.type_of_prev(pod_seq, pod1_its[j], 0) == 0), cp.presence_of(setups[j]) == 0))    model.add(cp.if_then(cp.logical_and(cp.presence_of(pod2_its[j]), cp.type_of_prev(pod_seq, pod2_its[j], 1) == 1), cp.presence_of(setups[j]) == 0))

# Ensure pods do not overlap
pod1_it = cp.interval_var(name='It_Pod1')
pod2_it = cp.interval_var(name='It_Pod2')

# Limit number of intervals per pod
model.add(cp.sum(cp.presence_of(it) for it in pod1_its) <= pod_capacity)
model.add(cp.sum(cp.presence_of(it) for it in pod2_its) <= pod_capacity)

solution = model.solve()
# model.export_model()
solution.write()```

Note that:
• the additional setup time is fixed in this example,
• the proposed approach requires the definition of an optional interval variable for each job,
• increase the size of the distance matrix (doubling along each dimension)

I'm not sure how this would scale when applied to the full problem...
Best regards,
Hugues

------------------------------
Hugues Juille
------------------------------

• #### 10.  RE: Additional setup time due to secondary resource

Posted Fri April 22, 2022 06:04 AM
Edited by Renaud Dumeur Fri April 22, 2022 07:57 AM
Dear Sebastian,
Here is a model that no longer relies on the distance matrix in the no overlap constrainst but explicitely creates job and pod setups.
It relies on the sequence type_of_prev for pods or jobs to determine if a setup interval is present.
It then use the distance matrix to configure the length of the setup intervals.
I hope it helps.
Cheers,
Edit: simplified the pod setup  presence status propagation
``````from docplex.cp import model as cp
from random import randint, seed

jobs = [0, 1, 2, 3]
pod_capacity = 3
seed(1)

model = cp.CpoModel()

# Intervals: the jobs to be executed
its = [cp.interval_var(length=1, name=f'J{j}') for j in jobs]

# Ensure intervals do not overlap and add setup time between each interval
distance_matrix = [[randint(1, 5) for _ in range(len(jobs))] for _ in range(len(jobs))]
seq = cp.sequence_var(vars=its, types=jobs, name='Seq')

# Alternative intervals, one per available container
pod1_its = [cp.interval_var(optional=True, name=f'Pod1_J{j}') for j in jobs]
pod2_its = [cp.interval_var(optional=True, name=f'Pod2_J{j}') for j in jobs]

# Ensure one of the helper intervals is executed
for j in jobs:

# create a sequence var for the containers
pods = [0, 1]
pod_its = pod1_its + pod2_its
pod_types = [0]*len(pod1_its) + [1]*len(pod2_its)
pod_seq = cp.sequence_var(vars=pod_its, types=pod_types, name='PodSeq')
# transition time between different pods
pod_change_delay = 1
pod_distance_matrix = [ [0 if i == j else pod_change_delay for i in pods ] for j in pods ]

# materialize the job setup as intervals
job_setups = [cp.interval_var(name=f'JobSetup_{j}', optional=True) for j in jobs]
for js, itv, j in zip(job_setups, its, jobs):
distance_to_j = [distance_matrix[i][j] for i in jobs]
# if the job type changes, then instantiate the job setup
model.add((cp.type_of_prev(seq, itv, -1, -1) != -1) == cp.presence_of(js))
(cp.length_of(js) == cp.element(distance_to_j, cp.type_of_prev(seq, itv))) &
(cp.end_of(js) == cp.start_of(itv))))

# materialize the pod setups as intervals
pod_setups = [cp.interval_var(name=f'PodSetup_{j}', optional=True) for j in jobs]
for pod_type, pod_itv, j in zip(pod_types, pod_its, jobs + jobs):
ps = pod_setups[j]
js = job_setups[j]
# if the used pod type changes, then a pod setup must be present
model.add(cp.if_then(cp.presence_of(pod_itv), (cp.type_of_prev(pod_seq, pod_itv, pod_type, pod_type) != pod_type) == cp.presence_of(ps)))
# if present a pod setup duration is taken from the matrix and must end before the start.
(cp.length_of(ps) == pod_change_delay) &
(cp.end_of(ps) == cp.min(cp.start_of(its[j]), cp.start_of(js, cp.INT_MAX)))))

# put setup and job itvs in a sequence
global_seq = cp.sequence_var(vars = job_setups + pod_setups + its, name="global")
# ensure they don't overlap

# Ensure pods do not overlap
# user constraints
pod1_it = cp.interval_var(name='It_Pod1')
pod2_it = cp.interval_var(name='It_Pod2')

solution = model.solve(LogPeriod=1000000)
if not solution:
res=model.refine_conflict()
print(res)
model.export_model()
solution.write()
``````

------------------------------
Renaud Dumeur
------------------------------

• #### 11.  RE: Additional setup time due to secondary resource

Posted Tue April 26, 2022 01:40 AM
Dear Hugues and dear Renaud,many thanks for the suggestions! I will explore them in detail and will make tests regarding the scalability. Best regardsSebastian

------------------------------
Sebastian Bayer
------------------------------