Topic
10 replies Latest Post - ‏2013-06-05T09:17:54Z by rdumeur
0372_Mintch_Zulitch
0372_Mintch_Zulitch
10 Posts
ACCEPTED ANSWER

Pinned topic Help modelling event-based setup time

‏2013-05-28T07:39:58Z |

We all know that it is possible to recall optimization information during MIP, but is it possible to use callback structure in CP using java API's ? It should be noted that I'm working on a paper declaring that if 50 job are scheduled on one machine then that machine should be marked as out-of-service for changing tools for 1 hour.

Thanks in advance.

  • rdumeur
    rdumeur
    82 Posts
    ACCEPTED ANSWER

    Re: Help modelling event-based setup time

    ‏2013-05-29T02:17:56Z  in response to 0372_Mintch_Zulitch

    Hi,

    In CP you don't need callbacks because you can access earch intermediate solution using startNewSearch(), next() and endSearch() on the CP object. If you need to express a constraint, you should be able to express it using the modeling language.  Especially for temporal constraints that can be, in CP optimizer, applied to interval variables.

    For instance, our experts say that the following model:

    using CP;

    int n=100;
    int Q = 100;
    int D = 10;
    // Generate random data
    int q[i in 1..n] = 1+rand(Q div 5);
    int d[i in 1..n] = 1+rand(D);

    int m = n;
    int horizon = 100000;

    execute {
      writeln("Quantities: ", q);
      writeln("Durations: ", d);
    }

    dvar interval production[i in 1..n] in 0..horizon size d[i];
    dvar interval maintenance[j in 1..m] optional in 0..horizon size 10;
    dvar sequence machine in
      append(all(i in 1..n) production[i],
              all(j in 1..m) maintenance[j]);

    cumulFunction level =
      sum(i in 1..n) stepAtStart(production[i], q[i]) -
      sum(j in 1..m) stepAtEnd (maintenance[j], 1, Q);

    execute {
      var f = cp.factory;
      cp.setSearchPhases(f.searchPhase(production));
    }

    minimize max(i in 1..n) endOf(production[i]);
    subject to {
      noOverlap(machine);
      level <= Q;
      forall(j in 1..m-1) {
        endBeforeStart(maintenance[j], maintenance[j+1]);
        presenceOf(maintenance[j+1]) => presenceOf(maintenance[j]);
      }
    }  

     

    show that by using scheduling cumul function on interval variables, propagation (if side constraints aren't too complex) is able to place interval so that the cumul function constraint is always honored.

    I hope this helps.

    Cheers,

     

     

  • 0372_Mintch_Zulitch
    0372_Mintch_Zulitch
    10 Posts
    ACCEPTED ANSWER

    Re: Help modelling event-based setup time

    ‏2013-05-29T18:46:03Z  in response to 0372_Mintch_Zulitch

     

    Thanks for your help. Can you verbally explain your concept? Is there any way to model the problem without deploying Cumulative function?

    • rdumeur
      rdumeur
      82 Posts
      ACCEPTED ANSWER

      Re: Help modelling event-based setup time

      ‏2013-05-30T10:12:46Z  in response to 0372_Mintch_Zulitch

      Hi,

       

      The concept of cumulative function is well described here:

      http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.ide.help%2FContent%2FOptimization%2FDocumentation%2FOptimization_Studio%2F_pubskel%2Fps_opl_Starting_kit327.html

      the presented model rely on the cumulative function to ensure maintenance interval presences.  the (level <= Q) express the fact production steps must be compensated by maintenance tasks. If you look at the definition of "level" you'll see that the positive term corresponds to production steps and that maintenance steps will contribute to reduce the "level" value, maintaining it below Q.

       

      • 0372_Mintch_Zulitch
        0372_Mintch_Zulitch
        10 Posts
        ACCEPTED ANSWER

        Re: Help modelling event-based setup time

        ‏2013-05-31T16:45:17Z  in response to rdumeur

         

        Hi,
        Some people suggest me to use "forbidstart" in combination of "Stepfunction". But I don't know how to use it.
        Also in your code you have used "rand" function. But there is no need to randomize,
        since the problem explicitly states that after processing 50 jobs on a machine, tool change is needed with duration of 1 hour.
        Also, I implemented your strategy using Cumulative function but it didn't return desired result. And this is my Code in Java syntax:


        IloIntervalVar tool_interval = CP_fms.intervalVar(1);
        IloCumulFunctionExpr[] tool = new IloCumulFunctionExpr[50];
        for (int i = 0; i < nbJobs; i++) {
         for (int j = 0; j < 50; j++) {
          tool[j] = CP_fms.sum(tool[j],
          CP_fms.stepAtEnd(job, 1));
          CP_fms.le(tool[j], 50);
          if (i == j) {
           CP_fms.add(CP_fms.endBeforeStart(job, tool_interval));
           tool[j] = CP_fms.sum(tool[j],
           CP_fms.stepAtStart(job, -51));
           machine.add(tool_interval);
           ends.add(CP_fms.endOf(tool_interval));
          }
         }

        }

        In other words, I didn't return following result:

        (Picture file in attachment)

        Attachments

        Updated on 2013-06-03T12:47:34Z at 2013-06-03T12:47:34Z by 0372_Mintch_Zulitch
        • rdumeur
          rdumeur
          82 Posts
          ACCEPTED ANSWER

          Re: Help modelling event-based setup time

          ‏2013-06-03T11:57:18Z  in response to 0372_Mintch_Zulitch

          Dear 0372_Mintch_Zulitch

          The rand() function was used in the model provided as an example to generate production activities with random durations and output quantities. It wasn't meant to solve exactly your problem, but as said, to illustrate how the cumul function could be used to control the presence of maintenance activities.

          Now, modifying the above model by setting a constant duration (1) for production and maintenance intervals and 50 for the level at which you want a maintenance interval, you get the following model:

          using CP;

          int n=100;
          int Q = 50;
          int m = n;
          int horizon = 100000;
          dvar interval production[i in 1..n] in 0..horizon size 1;
          dvar interval maintenance[j in 1..m] optional in 0..horizon size 1;
          dvar sequence machine in
            append(all(i in 1..n) production[i],
                    all(j in 1..m) maintenance[j]);

          cumulFunction level =
            sum(i in 1..n) stepAtStart(production[i], 1) -
            sum(j in 1..m) stepAtEnd (maintenance[j], 1, Q);

          execute {
            var f = cp.factory;
            cp.setSearchPhases(f.searchPhase(production));
          }

          minimize max(i in 1..n) endOf(production[i]);
          subject to {
            noOverlap(machine);
            level <= Q;
            forall(j in 1..m-1) {
                     endBeforeStart(maintenance[j], maintenance[j+1]);
                     presenceOf(maintenance[j+1]) => presenceOf(maintenance[j]);
             }
          }  
           

          That produce the level function, the image of which is attached. One can see very clearly the time at which the maintenance intervals are inserted, which correspond to the  "level == 0" state.

          Please feel free to adjust the maintenance & production interval duration to reflect your own problem data.

          I hope it helps.

          Cheers,

           

           

           

          Attachments

        • rdumeur
          rdumeur
          82 Posts
          ACCEPTED ANSWER

          Re: Help modelling event-based setup time

          ‏2013-06-03T12:11:32Z  in response to 0372_Mintch_Zulitch

          Hi,

          Some comments about your java code: as it doesn't correspond to the OPL model I provided, I guess it is normal to have different results.
          Please first replicate the OPL model in C++. You don't need to use an array of cumul function, but use the += and -= operators to model the cumul function you need. Please have a look at the documentation:

          http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.ide.help%2Frefcppopl%2Fhtml%2Fclasses%2FIloCumulFunctionExpr.html

          and at the sched_cumul.cpp example which illustrates how cumul functions are manipulated :

          http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cpo.help%2FCP_Optimizer%2FGetting_started%2Ftopics%2Fschedcumul_program.html

          Your final C++ model should be very similar to the OPL one.

          I hope this helps.

          Cheers,

           

          • 0372_Mintch_Zulitch
            0372_Mintch_Zulitch
            10 Posts
            ACCEPTED ANSWER

            Re: Help modelling event-based setup time

            ‏2013-06-03T17:59:17Z  in response to rdumeur

            Thanks for your help,
            I coded the problem according to your instruction in JAVA environment and it surprisingly returned desired sequence. But I think there exists a problem...
            You have mentioned neither any relationship between maintenance and production variables nor the relationship between production intervals in the Constraints set. And another problem is that when I removed the constraints "endBeforeStart" and "presenceOf", it returned the same result !!!
            Also, I want to know that whether it is possible to generalize the code to more than one machine. Should we declare more than one cumulFunction in the model ?

             

            • rdumeur
              rdumeur
              82 Posts
              ACCEPTED ANSWER

              Re: Help modelling event-based setup time

              ‏2013-06-04T07:03:52Z  in response to 0372_Mintch_Zulitch

              Dear Mitch,

               

              There is actually nothing to be  surprised of. There is indeed a relation between maintenance and production: the cumul expression precisely. The "level <= Q" constraints ensures that the cumul expr doesn't go above a given amount. It does so by propagating on the execution status of maintenance intervals.

              The endBeforeStart and PresenceOf constraints are there to order maintenance intervals so that the ones with lower indices are placed first.

              If you want to generalize to more than one machine, you indeed need to associate one cumul function to each machine.

              Cheers,

              • 0372_Mintch_Zulitch
                0372_Mintch_Zulitch
                10 Posts
                ACCEPTED ANSWER

                Re: Help modelling event-based setup time

                ‏2013-06-04T18:33:48Z  in response to rdumeur

                Thank you very much, your model is actually smart and intuitive.
                Conceptually, the constraints "PresenceOf" and "endBeforeStart" must be imposed on the model, but there is no obligation to consider them in run-time, since the result with or without them is the same. To be precise, since all maintenance intervals have equal duration of one hour, the interval (i) or (i+1) can be taken after 50 jobs.

                • rdumeur
                  rdumeur
                  82 Posts
                  ACCEPTED ANSWER

                  Re: Help modelling event-based setup time

                  ‏2013-06-05T09:17:54Z  in response to 0372_Mintch_Zulitch

                  Dear Mitch,

                  Indeed, but if you remove these constraints, because all the maintenance intervals are equivalent, the solver is left to decide which one of these interval must be actually used, which can lead to combinatorial explosion. So such symmetry-breaking constraints, removing the need for the solver to choose between maintenance intervals, greatly contribute to search efficiency!

                  Cheers,