Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only
Back to discussions
Expand all | Collapse all

Additional setup time due to secondary resource

  • 1.  Additional setup time due to secondary resource

    Posted 04/05/22 03:20 AM
    Hi,

    I'm currently working on a model with two sources of setup costs:
    - when switching the task
    - 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')
model.add(cp.no_overlap(sequence=seq, distance_matrix=distance_matrix))

# 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:
    model.add(cp.alternative(its[j], [pod1_its[j], pod2_its[j]]))

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

model.add(cp.span(pod1_it, pod1_its))
model.add(cp.span(pod2_it, pod2_its))
model.add(cp.no_overlap([pod1_it, pod2_it]))

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

    #DecisionOptimization


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

    Posted 04/21/22 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 04/21/22 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
    ------------------------------

    Original Message


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

    Posted 04/21/22 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
    ------------------------------

    Original Message


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

    Posted 04/21/22 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
    ------------------------------

    Original Message


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

    Posted 04/21/22 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
    ------------------------------

    Original Message


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

    Posted 04/22/22 03:17 AM
    Dear Sebastian,

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

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

    Original Message


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

    Posted 04/22/22 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
    ------------------------------

    Original Message


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

    Posted 04/22/22 05:56 AM
    Edited by System Admin 01/20/23 04:30 PM
    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:
    model.add(cp.end_at_start(setups[j], its[j]))

# 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')
model.add(cp.no_overlap(sequence=seq, distance_matrix=distance_matrix))

# 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:
    model.add(cp.alternative(its[j], [pod1_its[j], pod2_its[j]]))

# 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')
model.add(cp.no_overlap(sequence=pod_seq))

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

model.add(cp.span(pod1_it, pod1_its))
model.add(cp.span(pod2_it, pod2_its))
model.add(cp.no_overlap([pod1_it, pod2_it]))

# 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...
    Does this answer your modelling question ?
    Best regards,
    Hugues



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

    Original Message


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

    Posted 04/22/22 06:04 AM
    Edited by System Admin 01/20/23 04:20 PM
    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')
#model.add(cp.no_overlap(sequence=seq, distance_matrix=distance_matrix))
model.add(cp.no_overlap(sequence=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:
    model.add(cp.alternative(its[j], [pod1_its[j], pod2_its[j]]))

# 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 ]
#model.add(cp.no_overlap(sequence=pod_seq, distance_matrix=pod_distance_matrix))
model.add(cp.no_overlap(sequence=pod_seq))

# 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))
    model.add(cp.if_then(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.
    model.add(cp.if_then(cp.presence_of(ps),
                         (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
model.add(cp.no_overlap(sequence=global_seq))

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

model.add(cp.span(pod1_it, pod1_its))
model.add(cp.span(pod2_it, pod2_its))
model.add(cp.no_overlap([pod1_it, pod2_it]))

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


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

    Original Message


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

    Posted 04/26/22 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
    ------------------------------

    Original Message


Related Content