Topic
8 replies Latest Post - ‏2012-04-06T18:53:23Z by SystemAdmin
SystemAdmin
SystemAdmin
378 Posts
ACCEPTED ANSWER

Pinned topic How can I synch the sizes of interval variables

‏2012-04-03T16:22:48Z |
I am modeling a simple scheduling problem, where each task needs a labor assignment. Labor has working calendar as: 10hrs work, 10hrs break, 10hrs work, which is defined by intensity function as below:


// a calendar with two shifts [0,10] and [20, 30], with 10 units break in between tuple Tshifts 
{ 

int startTime; 

int endTime; 
}; 
{Tshifts
} shiftIntensity = 
{<0, 0>, <100, 10>, <0, 20>, <100, 30> 
}; stepFunction Calendar = stepwise (s in shiftIntensity) 
{ s.startTime -> s.endTime; 0 
}; execute 
{writeln(Calendar);
}; 
// output of the calendar: stepwise{ 0 -> 0; 100 -> 10; 0 -> 20; 100 -> 30; 0 }

Task requires 11 hrs of work time. So expected results is labor start working at time 0 and end at time 21, resulting 11 hrs of working time (size(labor) = 11).

I am using alternate function to force picking a labor for each task, and synch the start and end times of the task and allocation variables, but this does not sync their sizes, resulting labor to start at time 0 and end at time 11, with net working time of 10 hrs ( size(labor) = 10).

Is there a way of synching the sizes of these interval variables (task and allocation)?

I attached the model, which you can directly run and get the results (no data file needed).

Thanks a lot,
Updated on 2012-04-06T18:53:23Z at 2012-04-06T18:53:23Z by SystemAdmin
  • GGR
    GGR
    34 Posts
    ACCEPTED ANSWER

    Re: How can I synch the sizes of interval variables

    ‏2012-04-03T17:27:07Z  in response to SystemAdmin
    Hi

    The intensity declaration induces a constraint between the size, the length (end - start) and the intensity function of an interval variable.

    In your model:
    
    dvar interval V_task[t in tasks] optional size 11;
    


    You tell that a V_task element has a size of 11 without intensity function. So you implicitly tell that length == size = 11 for the interval variable.

    
    dvar interval V_allocation[a in allocations] optional intensity Calendar;
    


    A V_allocation has an intensity function but a free size in [0, intervalMax]. Then the alternative constraint fixes its length to 11 and the intensity constraint adapts the size of the V_allocation element to a compatible one (for sure not 11).

    You must declare the size in the interval variables that have the intensity function. That is the right model is:

    
    dvar interval V_task[t in tasks] optional;   dvar interval V_allocation[a in allocations] optional size 11; intensity Calendar
    


    A good practice when you deal with alternative is to not set any parameter (apart the optionality) in the slaves interval variables declaration.

    A last detail, the value of a numerical expression on an interval variables in case of absence in a solution should be given in the absence value argument of the expression. Your objective becomes:

    
    maximize - sum(t in tasks) endOf(V_task[t], 100); 
    // or minimize sum(t in tasks) endOf(V_task[t], 100);
    


    For full information about all these points, I suggest you consult the conceot part of the reference manual:

    Go to
    CP Optimizer > CP Optimizer C++ API Reference Manual
    then select
    Concepts

    Hope that helps
    • SystemAdmin
      SystemAdmin
      378 Posts
      ACCEPTED ANSWER

      Re: How can I synch the sizes of interval variables

      ‏2012-04-03T17:46:45Z  in response to GGR
      Thanks GGR, but your suggestion really does not work for this problem.

      Because of the nature of the problem, sizes of the tasks are known and are part of the requirement. But the size of the labors (workers) are not known, and should be made by decisions. In the attached problem, it is over simplified, with one labor and task. But in reality, there are many tasks and labors, so size of the labor will depend on the tasks it is assigned to.

      On the other hand, labors have working calendar but tasks do not have a calendar.

      Putting these together, I have to define V_task with task duration, and V_task with calendar and no duration.

      Still need to tie their sizes to make sure that labor really work at its assigned duration (so sleeping time is not counted as work :) ).
      • SystemAdmin
        SystemAdmin
        378 Posts
        ACCEPTED ANSWER

        Re: How can I synch the sizes of interval variables

        ‏2012-04-03T17:48:55Z  in response to SystemAdmin
        Fixed the name of the variable ---

        Thanks GGR, but your suggestion really does not work for this problem.

        Because of the nature of the problem, sizes of the tasks are known and are part of the requirement. But the size of the labors (workers) are not known, and should be made by decisions. In the attached problem, it is over simplified, with one labor and task. But in reality, there are many tasks and labors, so size of the labor will depend on the tasks it is assigned to.

        On the other hand, labors have working calendar but tasks do not have a calendar.

        Putting these together, I have to define V_task with task duration, and V_allocation with calendar and no duration.

        Still need to tie their sizes to make sure that labor really work at its assigned duration (so sleeping time is not counted as work :) ).
        • SystemAdmin
          SystemAdmin
          378 Posts
          ACCEPTED ANSWER

          Re: How can I synch the sizes of interval variables

          ‏2012-04-03T21:29:25Z  in response to SystemAdmin
          Found a solution!

          As GGR suggested, I can not fix the size of the task variables, because the final size will be driven by the allocations and labor availability, this was step one.
          Next, added a conditional constraint on the size of the allocation, such that, if allocation exist, then the size should be greater than or equal to the size of the task it is assigned to.

          These both together solved my problem.

          below is the updated code :
          
          using CP;   
          {string
          } labors = 
          {
          "labor1", 
          "labor2"
          }; 
          {string
          } tasks = 
          {
          "task1", 
          "task2"
          };   
          // a calendar with two shifts [0,10] and [20, 30], with 10 units break in between tuple Tshifts 
          { 
          
          int startTime; 
          
          int endTime; 
          }; 
          {Tshifts
          } shiftIntensity = 
          {<0, 0>, <100, 10>, <0, 20>, <100, 30> 
          }; stepFunction Calendar = stepwise (s in shiftIntensity) 
          { s.startTime -> s.endTime; 0 
          }; execute 
          {writeln(Calendar);
          }; 
          // output of the calendar: stepwise{ 0 -> 0; 100 -> 10; 0 -> 20; 100 -> 30; 0 }   tuple Tallocation 
          { string t; string l; 
          }; 
          {Tallocation
          } allocations = 
          {<t, l> | t in tasks, l in labors
          };   
          // VARIABLES ====================================================================================== dvar interval V_task[t in tasks] optional 
          // size 11 ;   dvar interval V_allocation[a in allocations] optional intensity Calendar; dvar sequence V_labor[l in labors] in all(a in allocations: a.l == l) V_allocation[a]; 
          // OBJECTIVE ======================================================================================  maximize 100*sum(t in tasks) presenceOf(V_task[t]) - sum(t in tasks) endOf(V_task[t], 100); 
          // ================================================================================================     
          // CONSTRAINTS ==================================================================================== subject to 
          { 
          // C_No_Overlap:  forall(l in labors) noOverlap(V_labor[l]); 
          // C_Alternative:  forall(t in tasks) alternative(V_task[t], all(a in allocations: a.t==t) V_allocation[a], 1); forall(a in allocations) presenceOf(V_allocation[a]) => sizeOf(V_allocation[a]) >= 11; 
          }
          


          Final note: this may not be the most efficient formulation, since it is using conditional constraints. I still would like to hear, if anyone knows a better / direct way of doing this.

          My second question is about assigning one task to the multiple labors during the time horizon (labor1 will do the work today, and labor2 will continue tomorrow). I will prepare an example code and post the question here.
  • GGR
    GGR
    34 Posts
    ACCEPTED ANSWER

    Re: How can I synch the sizes of interval variables

    ‏2012-04-04T11:50:27Z  in response to SystemAdmin
    Hi

    Two remarks

    Your model

    
    
    /**/ dvar interval V_allocation[a in allocations] optional intensity Calendar; 
    /**/ subject to 
    { 
    /**/ forall(a in allocations) presenceOf(V_allocation[a]) => sizeOf(V_allocation[a]) >= 11; 
    /**/ 
    };
    


    Is equivalent with the declaration

    
    
    /**/ 
    
    int horizon = intMax/2-1 
    // a very big number dvar interval V_allocation[a in allocations] optional size 11..horizon intensity Calendar; 
    /**/ 
    };
    


    Another point, it is useless to add an implication between the presence of an interval variable and any numerical expression on this interval variable. The dependence is more efficiently enforced in the declaration of the interval variable.

    That is
    
    forall(a in allocations) presenceOf(V_allocation[a]) => sizeOf(V_allocation[a]) >= 11;
    

    Should be replaced by
    
    forall(a in allocations) sizeOf(V_allocation[a], 11) >= 11;
    


    In general, before using a interval variable based construct in a meta-constraint (and, or, => constraints), you should verify if the condition on presence is not covered by the model constructs on the interval variables.

    Hope that helps
    • SystemAdmin
      SystemAdmin
      378 Posts
      ACCEPTED ANSWER

      Re: How can I synch the sizes of interval variables

      ‏2012-04-04T16:07:27Z  in response to GGR
      Thank you very much GGR. I was confused between the concepts of size and length. I Realized that, actually your first suggestion was perfectly correct. I can put size requirement to the V_Allocation variables directly, since those are task dependent (so sizes are known).
      
      dvar interval V_allocation[a in allocations] optional size taskSize[a.task] intensity Calendar[a.labor];
      


      Now, second part of my question is, how to handle assigning multiple labors to single task during the horizon, i.e., if task size is 15 and labor1 calendar allows working in 0,10] and labor2 calendar allows working in (10,20, then labor1 should work 10hrs and labor2 should work remaining 5 hrs. (see calendar definition as below):
      
      
      {Tshifts
      } shiftIntensity = 
      {<labor1, 0, 0>, <labor1, 100, 10>, <labor1,   0, 20>, <labor2, 0, 0>, <labor2,   0, 10>, <labor2, 100, 20>
      }; stepFunction Calendar[l in labors] = stepwise (s in shiftIntensity: s.labor==l) 
      { s.startTime -> s.endTime; 0 
      }; execute 
      {writeln(Calendar);
      }; 
      // output of the calendar:  [stepwise{ 0 -> 0; 100 -> 10; 0 } stepwise{ 0 -> 0; 0 -> 10; 100 -> 20; 0 }]
      


      I also attached the full example model, if you would like to try.
  • GGR
    GGR
    34 Posts
    ACCEPTED ANSWER

    Re: How can I synch the sizes of interval variables

    ‏2012-04-05T13:43:25Z  in response to SystemAdmin
    Hi

    Basically, you want to cut a task in several operations that will be executed on different <<labors>>. In practice that means that you want having interruptible task.

    The best way to write such a model heavily depends upon the exact problems. That is what are actual operational constraints that conditions allowing/forbidding interruption and the conditions that allows restoring execution.

    Nevertheless, the foundations of such model is to create a logico temporal chain of interval variables.

    
    
    
    int N = ...; 
    //number of task 
    
    int NSlices[1..N] = ...; 
    // number of execution intervals for a task tuple Slice 
    { 
    
    int task, 
    
    int rank
    };   
    {Slice
    } Slices = 
    {<t, r> | t in 1..N, r in 1..NSlices[i]
    };   dvar interval tasks[i in 1..N] = ...; dvar interval slices[s in Slices] = ...;   constraints 
    { forall(t in tasks) 
    { span(tasks[t], all(s in Slices, s.t == t) slices[s]); forall(r in 1..NSlices[i]-1) 
    { <<precedence>>(NSlices[<t, r>], NSlices[<t, r+1>)]; 
    // choose the right precedence type presenceOf(NSlices[<t, r>]) >= presenceOf(NSlices[<t, r+1>]); 
    } 
    }
    


    Then, define on the slices the model for their conditions and requirement of execution.

    You will find a model containing interruptible activities in: (third problem in the paper)

    Philippe Laborie, IBM ILOG CP Optimizer for Detailed Scheduling Illustrated on Three Problems, Proc. CPAIOR 2009, 2009

    Hope that helps
    • SystemAdmin
      SystemAdmin
      378 Posts
      ACCEPTED ANSWER

      Re: How can I synch the sizes of interval variables

      ‏2012-04-06T18:53:23Z  in response to GGR
      Thanks again GGR, for your response.
      I saw Philippe's suggestion for interruptible previously, but in my case I think (and hope) that we can model the problem without slices. Because, my case, we don't really need to divide the tasks, they are continuous, single piece. Just need to have flexibility of assigning multiple resources. I am not sure if it is possible, but I was thinking that a modified alternative constraint with some other size constraint may solve the problem, something like:

      
      
      // instead of assigning 1, lets say will assign 2 resources  forall(t in tasks) alternative(V_task[t], all(a in allocations: a.task==t) V_allocation[a], 2);   forall(t in tasks) sum(a in allocations: a.task=t) sizeOf(V_allocation[a]) == t.size
      

      Above code, will only work when we know that 2 resources will be allocated to each task. So is not really correct. Maybe, can create a dummy resource, which can be allocated to any task but not preferred. So in the case of single allocation, model can pick a real resource with full size and a dummy resource with 0 size.

      Again, I am not sure if this is a correct approach, but just trying to avoid implementing full interruption, since I believe this problem is one step simpler.