Decision Optimization

 View Only
  • 1.  reverse sequence in a scheduling problem

    Posted Tue June 30, 2020 04:34 AM
    Hi everyone,

    I have a scheduling problem in which each task processing sequence and its reverse sequence produce the same objective function value. In this problem, it is possible to eliminate some symmetries by arbitrarily setting one of the tasks to be performed in the first half of the task processing sequence. Would it be possible to make use of any feature of CP Optimizer to further explore this property of the problem?

    Best regards,
    M.

    ------------------------------
    Martin
    ------------------------------

    #DecisionOptimization


  • 2.  RE: reverse sequence in a scheduling problem
    Best Answer

    Posted Wed July 01, 2020 05:28 AM
    Hello,

    usually, symmetries like this could be broken by an additional precedence. For example, if there are two tasks A and B that cannot overlap (because they require the same resource for execution) then constraint endBeforeStart(A, B) breaks the symmetry. A similar technique could be also used if A and B can overlap, however the constraint is weaker in this case: startBeforeStart(A, B) (alternatively it is also possible to use endBeforeEnd instead).

    Best regards, Petr

    ------------------------------
    Petr Vilím
    IBM
    ------------------------------



  • 3.  RE: reverse sequence in a scheduling problem

    Posted Wed July 01, 2020 08:00 AM
    Hello,

    Thanks for your suggestion. It seems more effective than fixing an activity in the first half of the sequence.

    Best regards,
    Martin.

    ------------------------------
    Martin
    ------------------------------