Decision Optimization

 View Only
Expand all | Collapse all

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


  • 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:
        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
    ------------------------------



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



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