Originally posted by: Adriano199

Hi,

I'm trying to do a schedule that as dependencies in terms of work orders and in the tasks. Each work order as a set of task that are dependent (sequential) but the work order can be dependent from each other or not or dependent from multiple others. 

The question is how to relate the multiple dependencies?

So far i have been using the job_shop_flex example but i don't see hot multiple relate the work orders. (mainly due to the size of the dataset...)

 

Thank you for the attention.

Best regards,

Adriano

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: ChrisBr

Hello Adriano,

I'm not sure I understand what you are trying to model?
What I understood (but might be wrong) is that you would have 2 kinds of activities:
- activities for tasks that have to be constrained following some dependencies
- activities for work orders that have to be constrained following some dependencies
Then, the work orders and the tasks can be linked to gather  by using a "span" constraint.

You might have a look to the distributed example sched_sequence.mod which implements something which looks like this idea.

In case this would be irrelevant, please don't hesitate to give us more details.

I hope this helps a little nevertheless.

Regards,

Chris.
 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Adriano199

Hi Chris, 

Thanks for the reply.

Each work order (e.g. wo5) is constituted by several tasks that are executed in sequence (task1, task2, task3,.....)  or (task1,task4,task5,....)

But the work orders can dependent e.g a group of work order can be dependent (wo23,wo45,wo4) meaning this that wo4 to be executed, wo23 and wo45 must be completed before. 

Another detail that i forgot to mention before is that, each task requires a given skill that only some workers have. Also each task has an execution time (different for each task)

And the main goal is to minimize the execution time of the tasks. 

Regards,

Adriano

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

Hello,

For dependency between working orders, you can use precedence and implication constraints. For instance in your example, if wo4 to be executed requires that wo23 and wo45 are executed before, then the model would define 3 optional interval variables wo23,wo45,wo4 and the following constraints:

// If wo4 is executed, then necessarily, wo23 and wo45 must also be executed
presenceOf(wo4)=>presenceOf(wo23);
presenceOf(wo4)=>presenceOf(wo45);

// When both wo23 and wo4 are executed, wo23 must be completed before wo4 (same for wo45)
endBeforeStart(wo23,wo4);
endBeforeStart(wo45,wo4);

For the modeling of skills you can have a look at the exemple sched_optional. This example illustrates a small project scheduling problem with skills (and also some form of resource dependency). The bottom line is that for a given task, thanks to the notion o required skills you will be able to compute a set of possible workers (the ones that meet the skill condition) and you will define a set of optional interval variables (one for each possible worker W, this interval variable represents the task executed by worker W) and post an alternative constraint between the interval variable representing the task and these optional interval variables. This constraint states that one worker (and only one) with the required skills needs to be selected for the task. If the execution time of the task depends on the worker then you can define each of these optional intervals with the corresponding execution time of the worker.

For the objective function (minimize the execution time of the tasks), I'm not sure what you mean exactly. If you mean the makespan (end time of the last task), then you should use something like min(t in Tasks) endOf(task[t]). 

Philippe

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Adriano199

Hi Philippe  thanks for the reply it was very helpful. 

One issue that I have is I'm not able to figure out how to relate the work orders with the tasks... Because each workorder is composed by a set of tasks. 

So I don't know how to model-it properly. 

The data i thought doing-it like this:

 

 

Tasks = {

// Work order, task, execution Time, skill

  <111000,111,100,G07>,

  <111000,112,112,S01>,

  <111000,182,2,S01>,

  <123100,172,35,G03>,

  <123100,114,48,G00>,

  <123200,125,55,T26>,

  <123200,216,1,T26>,

  };

  

  Workers = {

  //Name, skill

  <ab1,G07>,

  <ab1,G02>,

  <ab2,S01>,

  <ab2,G03>,

  <ab3,T26>,

  <ab4,G00>,  

  };

  

  WOdependencies={

    <111000,123100>,

    <123200,123100>,

    <123200,111000>,

  };

 

Best regards,
Adriano

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

Did you consider the span constraint suggested by ChrisBr in her previous answer?

Philippe

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Adriano199

Yes, I'm following also the sched_task example the problem is I'm a bit new on this :-/ that's why all this questions and the difficulty to get going.

P.S, Do you think that the data file could work like that?

Regards,
Adriano

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: PhilippeLaborie

> Do you think that the data file could work like that?

 

I'm not sure to get your question right as it is difficult to consider the data file independently from the model. But provided Tasks, Workers and WOdependencies are defined as tuple sets in the model, then yes your data file seems to be syntactically correct.

Philippe

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Adriano199

using CP;
 
tuple RequestDat{
  int woid;
  };
tuple TaskDat{
  int woid;
  int taskid;
  int ptime;
  };
  
tuple ResourceDat{
  string name;
  string skill;
  };
 tuple STResourceDat{
  string name;
  int quantity;
  };

  
{RequestDat} requests = ...; 
{TaskDat} tasks = ...;
{ResourceDat} hresources = ...;
{STResourceDat} sresources = ...;


tuple Dependency{
  int woida;
  int woidb;
  };

tuple Requirement{
  int woid;
  int taskid;
  string hresource;
  string sresource;
  int quantity;
  };

tuple Operation{
  RequestDat request;
  TaskDat task;
  };
  
 tuple Allocation {
   Operation dmd;
   Requirement req;
   ResourceDat resource;
   STResourceDat stresource;
   };
   
// {Recipe}      recipes      = ...;   
 {Dependency} wodependencies = ...;
 {Requirement} requirements = ...;
 

{Operation} operations = {<r, m> | r in requests , m in tasks:
  r.woid == m.woid };
 
{Allocation} allocs = { < o, m ,r ,s> | o in operations, m in requirements, r in hresources, s in sresources : 
 o.task.woid == m.woid && r.skill == m.hresource && s.name == m.sresource};
 
dvar interval tirequests[requests];
dvar interval tiops[o in operations] size o.task.ptime;
dvar interval tiallocs[allocs] optional;
dvar interval ttask[tasks];
dvar sequence workers[r in hresources] in all(a in allocs: a.resource == r) tiallocs[a];

execute {
        cp.param.FailLimit = 10000;
}


minimize sum(t in tasks) endOf(ttask[t]); 
subject to {
  forall(r in requests) {
    span(tirequests[r], all(o in operations : o.request == r) tiops[o]);
    forall (o in operations : o.request == r) {  
      forall (rc in requirements : rc.woid == o.task.woid) {
        alternative(tiops[o], all(a in allocs : a.req == rc && a.dmd == o) tiallocs[a]);
      }        
      forall(tc in wodependencies: tc.woida == r.woid && r.woid == o.task.woid) {
        forall(o2 in operations : o2.request == r && tc.woidb == r.woid && r.woid == o.task.woid) {
          endBeforeStart(tiops[o], tiops[o2], 0);    
        }
      }
    }   
  }
  forall(r in hresources) {
    noOverlap(workers[r]);
  }    
  
};

And the data file:

/*********************************************
 * OPL 12.5.1.0 Data
 * Author: Adriano-PC
 * Creation Date: 28 de Jul de 2014 at 14:45:32
 *********************************************/
 
  hresources = {
 // Workname--skill
  <"ab1",G07>,
  <"ab2",G02>,
  <"ab3",S01>,
  <"ab4",G03>,
  <"ab5",T26>,
  <"ab6",G00>,  
  };
  
   sresources={
  // SresourceID (Station Ressource Shared Between tasks)----Quantity
  <R3,1>,
  <R2,1>,
  <O3,1>,
  <V4,1>,
  <S5,1>,
  <T2,1>,
  <AS7,1>,

  };
 
requests = {
// WOID
  <111001>,
  <111002>,
  <111003>,
  <123104>,
  <123105>,
  <123206>,
  };
   
  tasks = {
// WOID-- taskID--ptime
  <111001,111,100>,
  <111002,101,112>,
  <111003,102,182>,
  <111003,123,172>,
  <123104,131,114>,
  <123105,128,125>,
  <123206,122,216>,
  };
  
 
  
   requirements = {
 //WOID--- taskID--skill(Human)--Sresources-Quantity
  <111001,111,G07,R3,1>,
  <111001,111,G07,R2,1>,
  <111002,101,G02,R2,1>,
  <111002,101,G02,O2,1>,
  <111003,102,S01,V4,1>,
  <111003,102,S01,S5,1>,
  <111003,123,G03,S5,1>,
  <123104,131,T26,AS7,1>,
  <123104,131,T26,T2,1>,
  <123105,128,G00,S5,1>,  
  <123105,128,G00,T2,1>,  
  <123206,122,G00,R3,1>, 
  <123206,122,G00,R2,1>, 
  };
  
   
  wodependencies={
  // WOID--WOID
    <111001,123104>,
    <111002,123206>, 
    <123206,111003>,
  };

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: ChrisBr

Hello Adriano,

You have to give a name to your constraints in order to use the conflict refiner.
Therefore, the conflict refiner will tell you that the guilty constraint is the alternative constraint:
"alter: alternative(tiops[o], all(a in allocs : a.req == rc && a.dmd == o) tiallocs[a]);"

Indeed, the expression "all(a in allocs : a.req == rc && a.dmd == o)" gives an empty set for one of the tuples <r,o,rc>, consequently the constraint is violated.
This constraint states that
     "If interval tiops[o] is present then exactly one of intervals {all(...) tiallocs[a]} is present and a starts and ends together with this chosen one."
If there isn't any tiallocs interval which match the constraint, tiops[o] must be absent and this is not possible because tiops are not optional.

Having a quick look at your data file, I found something which could be the cause of the problem: there is a requirement (<111002,101,G02,O2,1>) with a Sresource (O2) which is not present in the available sresources set.

BTW, the intervals "ttask" are not constrained in your model! I guess it's because it is not completed.

I suggest you to try
        "minimize max(r in requests) endOf(tirequests[r]);"
as objective.

I hope this helps,

Chris.
 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Adriano199

Hi Chris ,

Thanks for the reply.

I have already changed some things since the the post. But my problem with the alternative constraints remains that I have posted in the new (alternative constraints post).

Best regards,

Adriano

#DecisionOptimization
#OPLusingCPOptimizer