Decision Optimization

 View Only
Expand all | Collapse all

how to schedule even/odd time tasks

  • 1.  how to schedule even/odd time tasks

    Posted Mon July 20, 2020 10:43 AM

    Hi,

    Let's assume we have 10 tasks t0, t1, ... t9 for sake of simplicity and let's ignore dependency between tasks for sake of simplicity.

    I have an OPL problem where I have to schedule the first task on an even time (0, 2, 4, 6, 8, ...). Second task must be after first task and odd time (1, 3, 5, ...). 3rd even, 4th odd, 5th even, and so on. First task won't necessarily be at 0 because there are actually other tasks.

    If I can grab task Intervals sorted and then say something like Mod(t[i+1]-t[i+0],2) == 1 in the subject to that should work. How would I do something like that?


    #DecisionOptimization


  • 2.  RE: how to schedule even/odd time tasks

    Posted Mon July 20, 2020 11:32 AM
    same question at https://stackoverflow.com/questions/62988632/cplex-opl-problem-how-to-schedule-even-odd-time-tasks/62990594#62990594

    ------------------------------
    ALEX FLEISCHER
    ------------------------------



  • 3.  RE: how to schedule even/odd time tasks

    Posted Tue July 21, 2020 04:25 AM
    Edited by System Fri January 20, 2023 04:37 PM
    If (as I understand) the sequence of tasks is not known a priori, I would consider a model like this one:
    using CP;
    
    int n=10;
    
    dvar interval x [i in 0..n] size 1;
    dvar sequence s in x;
    
    subject to {
      noOverlap(s);
      forall(i in 0..n-2) {
        (endOfPrev(s,x[i],0) == 0) => (startOf(x[i]) % 2==0); // First task starts at even time
        // Then the delay between consecutive tasks alternates between even and odd
        ( (startOf(x[i])-endOfPrev(s,x[i],0)) % 2) + ((startOfNext(s,x[i],0)-endOf(x[i])) % 2)  == 1;
      }
      last(s, x[n]); // x[n] is a technical interval variable at the end of the sequence
    }

    The first constraint in the loop ensures that the first interval (the only one such that endOfPrev(s,x[i],0) == 0 ) starts at even time.
    The second constraint ensures that the consecutive delays between tasks in the sequence alternates evens and odds.

    One solution looks like this:

     

     



    ------------------------------
    Philippe Laborie
    ------------------------------



  • 4.  RE: how to schedule even/odd time tasks

    Posted Fri July 24, 2020 09:38 PM
    0

    I got it working. The issue is that the constraints don't guarantee t0 is before t1. This means that I can get different position and declared position in the sequence which would make Prev or Next (which are based on position) output out of order.

    What I used is the isomorphism constraint. Basically, this constraint does a 1-to-1 correspondence between two sets. The first set is my task set. The second set is an ordered task set. CPLEX will then force the first set to follow the same pattern as the second set during optimization.

    {string} TaskNames = {t0,t1,t2,t3,t4,t5,t6,t7,t8,t9};
    
    
    dvar Interval taskIntervals [t in TaskNames] size 1;
    
    int n=10;
    range r=0..n-1;
    dvar interval itvs[r] size optional;
    
    subject to {
      // other constraints for taskIntervals
    
      forall(i in r : i!=0) {
          startBeforeStart(itvs[i-1],itvs[i]);
          (startOf(itvs[i])-startOf(itvs[i-1])) mod 2==1;
      }
      isomorphism(taskInverals, itvs);
    }
    


    ------------------------------
    Topa Topa
    ------------------------------



  • 5.  RE: how to schedule even/odd time tasks

    Posted Mon July 27, 2020 11:05 AM
    Edited by System Fri January 20, 2023 04:25 PM
    There is something I do not understand. The formulation with isomorphism also do not guarantee that t0 is before t1. It could be that, in the solution t1, is before t0, no ?

    If the sequence is known in advance (t0 before t1 before t2 ...), then you do not need sequence variables or isomorphism, you can directly post the constraint that the delay is odd on the delay of the precedence constraint. 

    And by the way, in my formulation I assumed that you had to alternate odd/even in the delays whereas your problem seems easier: only odd delays after the first task, so the formation could be simplified to:

    using CP;
    
    int n=10;
    
    dvar interval taskIntervals [i in 0..n] size 1;
    dvar sequence s in taskIntervals;
    
    subject to {
      noOverlap(s);
      forall(i in 0..n-2) {
        (endOfPrev(s, taskIntervals[i],0) == 0) => (startOf(taskIntervals[i]) % 2==0); // First task starts at even time
        // Then the delay between consecutive tasks should be odd
        ((startOfNext(s, taskIntervals[i],0)-startOf(taskIntervals[i])) % 2)  == 1;
      }
      last(s, taskIntervals[n]); // taskIntervals[n] is a technical interval variable at the end of the sequence
    }​​

    The advantage of this formulation (compared to the one with isomorphism) is that it do not introduce additional interval variables with a different semantics (the itvs[i]) which could have some impact on the performance of the resolution.




    ------------------------------
    Philippe Laborie
    ------------------------------



  • 6.  RE: how to schedule even/odd time tasks

    Posted Mon July 27, 2020 03:16 PM
    Yes, I don't care if t0 is before t1 or after t1. The only thing I care about is the start distance between consecutive tasks are odd (included in question) and my other conditions (not included in question). I can't post the code but the issue I had was basically that the order could be (t0, t1), (t2, t3) where the parenthesis means it could be any order. I was doing something like (startof(t[i]) - startofPrev(s, t[i],0) ) %2 == 1. It was ordering it t1, t0, t3, t2 but the distance between t1 and t0 was even.

    I might have messed up somewhere. However, my current solution with isomorphism works. You are probably right that there is an impact on performance. I will give it another attempt next month as what I currently have is working.


    >And by the way, in my formulation I assumed that you had to alternate odd/even in the delays whereas your problem seems easier: only odd delays after the first task, so the formation could be simplified to:

    It might have been understood that way but I meant in the question that t0 starts at even (I don't care anymore), then t1 starts at even and so on. So, distance is always odd.


    ------------------------------
    Topa Topa
    ------------------------------



  • 7.  RE: how to schedule even/odd time tasks

    Posted Tue July 28, 2020 02:16 AM
    Edited by System Fri January 20, 2023 04:24 PM
    "I was doing something like (startof(t[i]) - startofPrev(s, t[i],0) ) %2 == 1. It was ordering it t1, t0, t3, t2 but the distance between t1 and t0 was even."

    Really? Then it is a bug. The 
    Prev/Next are the ones of the sequence in the solution, so if the solution is t[1], t[0], t[3], t[2], the the constraint for i=0 says:
      (startOf(t[0]) - startOfPrev(s, t[0],0) ) %2 == 1, which means that the distance between the start of t[0] and the start of previous task t[1] should be odd.

    Do you have an instance showing the problem. Could you post how to reproduce this solution?

    [I slightly edited my last proposed formulation as the odd distance is between the consecutive 'start', not between 'end' of an interval and the 'start' of the next one.]




    ------------------------------
    Philippe Laborie
    ------------------------------



  • 8.  RE: how to schedule even/odd time tasks

    Posted Sat October 24, 2020 10:33 PM
    Edited by System Fri January 20, 2023 04:48 PM
    Hi Philippe,

    I finally got some free time to work on this project again. So, I am now using the python API because it would be easier for me to automate the work and I also didn't like the syntax of cplex. I am sorry for the inconvenience if you don't have experience with python but the coding is pretty similar.

    Below is a more realistic example of what I need and below it is the output. Now based on the way I understood your solution, what I need to do is create one dummy variable in the sequence. Make it last in the sequence. The set (start_of_next(sequence,interval) - start_of(interval)) %2 == 1 for every interval except dummy interval. This is exactly what this code does with (start_of_next(sequence,interval) - start_of(interval)) %2 == 1 disabled (the three commented lines). When I remove the comments, I will get solution unknown.

    The reason I kept them commented is because I want to show you that last interval is showing as last in the sequence but it is starting before test_intervals_2 and test_intervals_3. Please let me know what I am doing wrong.

    Edit: The code is refusing to be formatted for some reason when I do insert code. I'll have to put it unformatted.

    from docplex.cp.model import CpoModel

    timeout = 5
    delay = 50
    variables = ["t0", "t1", "t2", "t3", "t4"]
    precedences = [
    ["t0", "t2"],
    ["t1", "t2"],
    ["t1", "t3"],
    ["t2", "t3"],
    ]

    mdl = CpoModel()

    # Intervals
    test_intervals_start = mdl.interval_var_dict(variables,size=1, name="testIntervalsStart")
    test_intervals_end = mdl.interval_var_dict(variables,size=1, name="testIntervalsEnd")
    dummy_interval = mdl.interval_var(size=1,name="dummy")

    # Intervals in list
    all_interval_list = list(test_intervals_start.values()) + list(test_intervals_end.values()) + [dummy_interval]
    interval_start_list = list(test_intervals_start.values()) + [dummy_interval]

    # Sequence is start intervals + dummy interval
    start_sequence = mdl.sequence_var(interval_start_list, name="start_sequence")

    # No overlap
    mdl.add(mdl.no_overlap(all_interval_list))

    # precedences constraint
    for p in precedences:
    pre = p[0]
    post = p[1]
    mdl.add(mdl.end_before_start(test_intervals_end[pre],test_intervals_start[post]))

    # end delayed 50 cycles after start
    for v in variables:
    mdl.add(mdl.start_at_start(test_intervals_start[v],test_intervals_end[v],delay))

    # Dummy should be last in sequence
    mdl.add(mdl.last(start_sequence,dummy_interval))
    for v in variables:
    cur_start = mdl.start_of(test_intervals_start[v])
    next_start = mdl.start_of_next(start_sequence,test_intervals_start[v])
    # mdl.add(mdl.end_before_start(cur_start,next_start))
    dist = mdl.minus(next_start,cur_start)
    # dist_mod2 = mdl.mod(dist,2)
    # mdl.add(mdl.equal(dist_mod2,1))
    # mdl.add(mdl.equal(dist,100))

    #
    mdl.add(mdl.minimize(mdl.max([mdl.end_of(i) for i in all_interval_list])))

    msol = mdl.solve(TimeLimit=timeout)
    print("Solution status: " + msol.get_solve_status())
    print("Solve time: " + str(msol.get_objective_values()) + "s\n")
    msol.write()



    Solution status: Optimal
    Solve time: (154,)s

    -------------------------------------------------------------------------------
    Model constraints: 11, variables: integer: 0, interval: 11, sequence: 2
    Solve status: Optimal
    Search status: SearchCompleted, stop cause: SearchHasNotBeenStopped
    Solve time: 0.01 sec
    -------------------------------------------------------------------------------
    Objective values: (154,), bounds: (154,), gaps: (0,)
    dummy: (start=2, end=3, size=1, length=1)
    testIntervalsEnd_0: (start=51, end=52, size=1, length=1)
    testIntervalsEnd_1: (start=50, end=51, size=1, length=1)
    testIntervalsEnd_2: (start=102, end=103, size=1, length=1)
    testIntervalsEnd_3: (start=153, end=154, size=1, length=1)
    testIntervalsEnd_4: (start=53, end=54, size=1, length=1)
    testIntervalsStart_0: (start=1, end=2, size=1, length=1)
    testIntervalsStart_1: (start=0, end=1, size=1, length=1)
    testIntervalsStart_2: (start=52, end=53, size=1, length=1)
    testIntervalsStart_3: (start=103, end=104, size=1, length=1)
    testIntervalsStart_4: (start=3, end=4, size=1, length=1)
    start_sequence: (testIntervalsStart_1, testIntervalsStart_0, testIntervalsStart_4, testIntervalsStart_2, testIntervalsStart_3, dummy)

    ------------------------------
    Topa Topa
    ------------------------------



  • 9.  RE: how to schedule even/odd time tasks
    Best Answer

    Posted Mon October 26, 2020 01:00 PM
    I see. The problem occurs because you do not have any "no_overlap" constraint on the sequence variable 'start_sequence' and thus, the value of the sequence (the ordering of the interval variables in the sequence variable value) is not related with the start/end value of the interval variables.

    If you add:
    mdl.add(mdl.no_overlap(start_sequence))​

    You will see that it works as expected.



    ------------------------------
    Philippe Laborie
    ------------------------------



  • 10.  RE: how to schedule even/odd time tasks

    Posted Mon November 09, 2020 06:22 PM
    I tested it and you are right. It works now. Shouldn't this be a bug because I already said that all intervals in the sequence don't overlap or CPLEX attempts to work with the sequence without looking at the interval that they are not overlapping elsewhere?

    Anyway, thank you very much for the help!

    ------------------------------
    Topa Topa
    ------------------------------