Decision Optimization

Expand all | Collapse all

Scheduling: How to count number of transitions

  • 1.  Scheduling: How to count number of transitions

    Posted Fri July 30, 2021 08:40 AM
    Hi everyone,

    I am facing a scheduling problem for building the academic schedule of a university.

    I would like to model professor transitions from one building to another, ensuring that there is at least one hour to make the transition possible.
    I modeled this requirement through a transition matrix, which tells me the time it takes to move from one building to another.

    self.transition_matrix = [[0, 0, 0, 0, 0, 0],
                              [0, 0, 0, 0, 0, 0],
                              [0, 0, 0, 1, 1, 1],
                              [0, 0, 1, 0, 1, 1],
                              [0, 0, 1, 1, 0, 1],
                              [0, 0, 1, 1, 1, 0]]​

    Then, for each professor I created its sequence by providing both the list of intervals (vars input) and an array containing the building of each interval (types), relative to the transition matrix.

    self.professor_seq_d[professor] = sequence_var(
                        vars=professor_all_intv,
                        types=professor_all_intv_transition_indices,
                        name='seq_professor_{professor_code}'.format(professor_code=professor))​

    Finally, to make sure that transition times will be respected, I added a no_overlap constraint specifying the transition matrix as distance matrix. 

    self.mdl.add(
        no_overlap(
            sequence=self.professor_seq_d[professor],
            distance_matrix=self.transition_matrix,
            is_direct=1))​

    The methodology followed is inspired by this example from the official documentation, and everything works just fine. 


    At this point the new requirement is to limit the number of daily transitions from one building to another, for example, at most 2 transitions.

    What I'd like to be able to do is count the sum of the distances that the model, based on the transition matrix, is forced to enter.
    Do you think this is possible? Is there any other alternative? What could be the best way to do it in this "configuration"?

    Thank you in advance for any suggestions.

    Best regards, 
    Matteo

    ------------------------------
    Matteo Zantedeschi
    ------------------------------


  • 2.  RE: Scheduling: How to count number of transitions

    Posted Mon August 02, 2021 04:10 AM

    Hello Matteo,

    Here are some lines that you can add to the example you cite to do what you want.  The idea is to use the type_of_next expression to tell when the type changes:

    setups_m1 = mdl.sum(mdl.type_of_next(s1, t, TASK_TYPE[i], TASK_TYPE[i]) != TASK_TYPE[i] for i, t in enumerate(tasks_m1))
    setups_m2 = mdl.sum(mdl.type_of_next(s2, t, TASK_TYPE[i], TASK_TYPE[i]) != TASK_TYPE[i] for i, t in enumerate(tasks_m2))
    
    mdl.add(setups_m1 <= 2)
    mdl.add(setups_m2 <= 2)
    
    mdl.add_kpi(setups_m1, "M1_SETUPS")
    mdl.add_kpi(setups_m2, "M2_SETUPS")
    


    You can add these lines just before the solve.  The idea is that you count the number of times that the next interval has a different type from the current one.  The two arguments TASK_TYPE[i] to type_of_next tell CP Optimizer that if the interval is either the last in the sequence or absent, then TASK_TYPE[i] will be the value of the type_of_next expression, which means that for that interval, no change will be counted since the != expression will evaluate false.  I've added these two expressions as KPIs to the model too, so that you can see their values in the log.

    Regards,



    ------------------------------
    Paul Shaw
    ------------------------------



  • 3.  RE: Scheduling: How to count number of transitions

    Posted Tue August 31, 2021 06:59 AM
    Edited by Matteo Zantedeschi Tue August 31, 2021 07:13 AM
    Hello @Paul Shaw

    First of all thank you for your support.
    I answer a little late because first I wanted to implement and test the solution you suggested. 

    Your solution meets my need, but I still have some doubts, which I will try to explain.

    In my sequence there are both optional and non-optional interval variables, i.e. not all the interval variables will be present in the solution.
    I would like to calculate the sum of the transitions considering only the interval variables present.

    Therefore my code currently looks as follows:

    self.mdl.add(sum(logical_and([
        # The intv is present in the solution
        (presence_of(intv) == 1), 
        # The next intv is present in the solution
        (start_of_next(sequence=self.professor_seq_d[professor], interval=intv, lastValue=0, absentValue=0) != 0),
        # The next intv is placed in a different site, i.e. transition happens
        (type_of_next(sequence=self.professor_seq_d[professor], interval=intv, lastValue=intv_type, absentValue=intv_type) != intv_type),
        ]) for intv in professor_intvs) <= 2
    )​

    I used start_of_next() method to check if the next interval of the sequence is also present in the solution, based on the fact that, like start_of(), the method will return 0 when the next interval is absent. 

    Since this is not specified in the documentation here, I would like to ask if my approach is correct or is there a better way to do it?
    Specifically, is there a way to directly access the next interval variable in the sequence, instead of its type, start, end and so on?


    Thank you and best regards,
    Matteo​

    ------------------------------
    Matteo Zantedeschi
    ------------------------------



  • 4.  RE: Scheduling: How to count number of transitions

    Posted Tue August 31, 2021 11:23 AM

    Hello Matteo,

    In CP Optimizer, when you use constructs such as type_of_next(seq, itv, lastValue, absentValue) , the "next" means the next PRESENT interval in the sequence.  If itv is absent, then the value returned is 'absentValue' and if it is the last present interval in the sequence, you get 'lastValue'.  So, you don't need to complicate things any more than in the code snippet that I sent before.  To be more concrete, assume that each task has a BUILDING associated with it (which you specify to the sequence variable as the types) and you want to limit the number of building changes to 2.  You would write something like:

    num_building_changes = mdl.sum(
       mdl.type_of_next(seq, itv[i], BUILDING[i], BUILDING[i]) != BUILDING[i] for i in range(len(itv))
    )
    mdl.add(num_building_changes <= 2)

    Now consider a particular index j, and so we are considering itv[j] and (potentially) the next interval in the sequence after itv[j].  Now there are three cases:

    1/ itv[j] is absent.  Here, type_of_next evaluates to BUILDING[i] meaning the != comparison will be false, and this contributes 0 to num_building_changes

    2/ itv[j] is present and last in the sequence.  Again type_of_next evaluates to BUILDING[i] meaning the != comparison will be false, and this contributes 0 to num_building_changes

    3/ itv[j] is present and not last in the sequence.  Here type_of_next will be the building of the next interval in the sequence.  So, if that building is the same as the current building the != will be false as before and nothing will be contributed to num_building_changes.  However, if the next building is different, then the != comparison will be true and 1 will be contributed to num_building_changes.

    As you can see we only count +1 to the number of building changes if (a) the interval is present, (b) not last and (c) the next interval has a different building.

    Regards,



    ------------------------------
    Paul Shaw
    ------------------------------



  • 5.  RE: Scheduling: How to count number of transitions

    Posted Tue September 07, 2021 07:58 AM

    Hello @Paul Shaw,

    Thank you again for your answer!
    Your explanation is completely clear to me and my problem is now solved.

    I would like to share my solution because I added an element to make it more general, i.e. applicable ​when transition costs are different from one. In this case, computing the number of transitions is different from computing the total cost of transitions. 

    To adress the second need (compute the total cost of transitions) I used both type_of_next() and element() method, and my constraint is now:

    self.mdl.add(sum(
        element(
            array=self.transition_matrix[intv_type],
            index=type_of_next(
                sequence=self.professor_seq_d[professor],
                interval=intv,
                lastValue=intv_type,
                absentValue=intv_type
            )
        ) for intv in professor_intvs) <= 2
    )​


    I used element() method to access the cost associated with the transition from the current interval to the next one, which type is identified by type_of_next() method. 

    I'm sharing this solution hoping it will be useful to someone else and to know in case you can find a better one.

    Thank you again for the help!

    Best regards,
    Matteo



    ------------------------------
    Matteo Zantedeschi
    ------------------------------