Decision Optimization

 View Only
  • 1.  Setup time before interval

    Posted Tue November 23, 2021 02:16 AM
    Edited by Sebastian Bayer Tue November 23, 2021 02:18 AM

    Hi all,

    I'm working on a parallel machine scheduling model which I approach with the usual (optional) interval variables, alternative and noOverlap constraints. In this problem, we're having machine- and sequence dependent setup times which we incorporate via the noOverlap constraint.

    For one of my objectives, I need to know the setup time directly before an interval variable. I came up with this formulation:

    startOf(o_j) - max_{i in M_j}(endOfPrev(m_i, a_ij))

    where o_j is an interval and a_ij are optional intervals linked to o_j via the alternative constraint. M_j is is the subset of machines able to do o_j and m_i is a sequence variable holding all a_ij.

    Is there a better approach than searching all sequence variables for a non-null value? Is it e.g. possible to determine in which sequence variable m_i the operation o_j is located?


    Sebastian Bayer

  • 2.  RE: Setup time before interval

    Posted Tue November 23, 2021 11:16 AM
    What about using an interval variable for each setup and using the difference between startOf() and endOf() for that variable in the objective?

    Paul Rubin
    Professor Emeritus
    Michigan State University

  • 3.  RE: Setup time before interval

    Posted Tue November 23, 2021 12:05 PM
    Edited by Olivier Lhomme Tue November 23, 2021 12:07 PM
    In the text you say you want the setup cost, but your constraint looks like you want to compute the distance between two consecutive intervals on a machine, which can be greater than the setup cost.
    If you want to have the setup cost before o_j, first you need the type of the previous interval on the same machine. You can use the typeOfPrev function.
    Let type_j be the type associated with the interval o_j,
    let myTransitionCost[m] be the transition matrix associated with the machine m,
    and let s[m] the sequence associated with the machine m,
    then the idea is to get the setup cost with myTransitionCost[m][typeOfPrev(s[m],o_j)][type_j].
    1. The interval o_j is not exactly what you want, you want the interval o_j_i, the member of the alternative, if is present.
    2.  the case where the interval o_j_i is the first in the sequence must be handled.
    3.  The case where the intervals are absent must be handled too.
      This can be done simply.
      The function typeOfPrev(m,o_j) has two additional parameters to specify a value for the cases 2) and 3).
      You can extend the possible types, for an absent or a first interval in the sequence.
      And you need to extend the transition matrix in order to give the result you want for these cases.
      For example if you want to sum all these costs, you may want 0.
      See a complete example with this idea in the opl/examples/opl/sched_tcost directory. It uses typeOfNext instead of typeOfPrev as it is more convenient to extend the matrix as you will see.

      Olivier Lhomme

    1. 4.  RE: Setup time before interval

      Posted Wed November 24, 2021 02:07 AM
      Hi all,

      @Paul: thanks for taking the time to reply! I'm not sure how I would work with your suggestion but I think I think I can work with what Olivier suggested.

      @Olivier: thanks for replying! You are totally right, what I wrote down can be longer than the setup time. I actually want the setup time so your suggestion helps. Thanks for pointing me in this direction!



      Sebastian Bayer