Originally posted by: SystemAdmin

[elham said:]

Hello,
I have a question and appreciate your help.
I have a scheduling program that is like this:


[i]{string} TaskNames= ...;
int AgentNo = ...;
range aa = 1..AgentNo;

dvar interval task [t in TaskNames]  optional size Duration[t];

dvar interval task [t in TaskNames]  optional size Duration[t];

dvar sequence Agents[a in aa ] in
all (t in TaskNames: Agent[t]==a) task[t];

minimize max(t in TaskNames) endOf(task[t]);
subject to
{
forall (a in aa)
  noOverlap(Agents[a]);

[color=red][font=Verdana]forall (a in aa, t1,t2 in TaskNames: Agent[t1]==Agent[t2]==a)
prev(Agents[a], task[t1], task[t2]) => endAtStart(task[t1],task[t2]);[/font][/color]
}[/i]


I get this error:

CP cannot extract expression: forall(a in 1..4, t1 in TaskNames, t2 in TaskNames) next(Agents[a],task[t1],task[t2]) => endAtStart(task[t1], task[t2], 0)
.

Please help.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[Didier Vidal said:]

Elham,

endAtStart can't be used in an imply statement. The way it is specified in the documentation is "This constraint cannot be used in a meta-constraint" (meta constraints are 'or', 'not', and other constraints built on that such as imply).

If you added these constraints to try to pack the activities as much as possible on each sequence, a way to do this is to add a term on the objective that minimizes the duration of each sequence (for instance, create an interval that spans all the activities on a sequence, and minimize its size).

If you added these constraints because you really need a continuous process, then you will need a stronger constraint. (For instance, create the interval that spans the activities on a sequence, and constraint its size to be the sum of the size of sub activities).

Hope this helps.

Didier.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[elham said:]

Thanks  Didier,

[i]"For instance, create the interval that spans the activities on a sequence" [/i]
can you kindly give me an example on how to do this?

Thanks


#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[Didier Vidal said:]

Here is an example. Note that if all your task activities are optional, the optimal solution to your problem is to perform zero task.

Didier.


using CP;

{string} TaskNames= {"a","b","c", "d", "e", "f", "g", "h", "i", "j", "k", "l",
                    "m", "n", "o", "p", "q", "r", "s", "t" ,"u" ,"v" ,"w", "x",
                    "y", "z"};
int AgentNo = 10;
range aa = 1..AgentNo;

int agent[t in TaskNames] = rand(10) + 1;

dvar interval task [t in TaskNames]  optional size rand(8) + 1;


dvar sequence Agents[a in aa ] in all (t in TaskNames: agent[t]==a) task[t];

// declare the interval (declared as optional in case an agent has no task assigned)
dvar interval agentWork[aa] optional;


minimize max(t in TaskNames) endOf(task[t]);
subject to
{
forall (a in aa) {
      noOverlap(Agents[a]);
      //declare the spanning relation
      span(agentWork[a], all(t in TaskNames : agent[t] == a) task[t]);
      }
     

}

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[elham said:]

Didier,

Thanks for your quick response, unfortunately I am still struggling with modeling my problem. let me explain my problem to you:

I have a set of tasks which are assigned to different agents, however not all of these tasks are executed each time, some of them are mutually exclusive and only one of the tasks in a certain group of tasks can be executed each time. ( I named these tasks ctasks in my code). Tasks also may have precedence relation with each other. now my objective is to find the lower bound and upper bound for completion time of all tasks. I could model the lower bound (minimize problem) but I have trouble to find the upper bound (maximize problem), my problem is exactly this:

Find out which tasks should be executed in order to have the maximum completion time:

subject to the following constraints:

1-tasks may have precedence relation
2- exactly one task from the tasks with mutual exclusive relation can be executed at each time
3- The interval of tasks executed in one agent should not overlap
4- the ordering of the tasks should be optimal which means once it was determined which tasks should be executed, they should be executed in an order to minimize the completion time. ( I have impelemented the first three constraints, but my problem is with this 4th constraint, it seems that I have both min and the max problem at the same time)

Here is my  code ( which is not working)


{string} TaskNames= ...;
int AgentNo = ...;
range aa = 1..AgentNo;
int cgroupNo=...;
{string} ctasks[1..cgroupNo]=...; //mutually exclusive tasks
int  Duration [t in TaskNames] = ...;
int Agent[t in TaskNames] = ...;

tuple Precedence {
  string before;
  string after;
  int communicationTime;
};
{Precedence} Precedences = ...;

dvar interval s[aa] optional;
dvar interval task [t in TaskNames]  optional size Duration[t];
dvar sequence Agents[a in aa ] in
all (t in TaskNames: Agent[t]==a) task[t];

maximize max(a in aa) endOf(s[a]);
subject to
{
forall (a in aa)
{
startOf(s[a])==0;
sizeOf(s[a])== sum(t in  TaskNames: Agent[t]==a) sizeOf(task[t]); /* This is not quite correct, because for the tasks that                   
                                                                                                              have precedence relation the agent may be idle for
                                                                                                              a while and wait till the communication be complete
                                                                                                                */
}

     
      //only one task out of the mutual exclusive group is executed
          forall( i in 1..cgroupNo)
  sum ( c in ctasks[i]) presenceOf(task[c])==1;
     
      //The tasks that are not in mutually exclusive groups are always executed
        forall (t in TaskNames: t not in conditionalTasks && t not in afters)
        presenceOf(task[t]);
           
        forall( p in Precedences)
        {
      presenceOf(task[p.after]) => presenceOf(task[p.before]);
      if (p.after not in conditionalTasks)
    presenceOf(task[p.before])=>presenceOf(task[p.after]);
            endBeforeStart(task[p.before],task[p.after],p.communicationTime);
          }
  forall (a in aa)
  noOverlap(Agents[a]);

}
execute {

  for (var t in TaskNames)
  {
  if (task[t].end != 0)
  writeln("task: " + t " " task[t].start + "..." +task[t].end );
 
  }

  }
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[Didier Vidal said:]

The points 1, 2, 3 could be modeled with an alternative statement.

In our optimization newsletter (The right hand side : http://www.ilog.fr/optimization/the-right-hand-side/ - registration required), there is an article titled "Modeling with ILOG CP Optimizer" that illustrates the use of the 'alternative' statement to model mutual exclusive relations that you might find interesting (however, in the commented model, there is no precendence relation - if there were, they would have been set on the intervals named 'task', not on the intervals named 'alt'.

You can also look at the example called 'sched_optional' in the OPL distribution. It has both mutual exclusive tasks, and precedence constraints.
This example is fully commented in the getting started, in section

Starting Kit / Getting Started with Scheduling in ILOG OPL Development Studio / Using alternative resources in the house building problem

Let me know if these two articles help you moving forward with your model.

Didier.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[elham said:]

I read the article but I could not figure out how to solve my problem, please help me I am new to ILOG.

I  do not know how I can find the maximum of all minimal schedules. I mean I want to figure out what tasks from the set of alternative tasks give me the maximum value of the optimal schedule. the optimal schedule is the one that has the minimum completion time of the tasks.

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[Didier Vidal said:]

Maybe the best is to start from your code then.
I will not be able to help you in the next two weeks. So maybe today if time zones allow us to exchange a few messages.

In the code you sent, two statements are not accepted by OPL:

        forall (t in TaskNames: t not in conditionalTasks && t not in afters)
        presenceOf(task[t]);


Because afters is not defined as a data.


      presenceOf(task[p.after]) => presenceOf(task[p.before]);
      if (p.after not in conditionalTasks)
    presenceOf(task[p.before])=>presenceOf(task[p.after]);


Because conditionalTasks is not defined in the data.

Is it the parts you are struggling with ? If yes, I tried to guess a definition for these sets.. At least, the code runs.



{string} afters = {p.after | p in Precedences};
{string} conditionalTasks = union(i in 1..cgroupNo) ctasks[i];



I'm not sure it is the information you are looking for... If not, maybe a way to move forward would be if you posted
  - a model with sample data
  - and explain what you don't like in the solution that it provides.


Didier.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[elham said:]

Thank you so much Didier for helping me.

Sorry I forgot to copy the part that I initialized "conditional tasks" and "afters" variables . Actually the(minimization= lower bound) code does not have a problem and works properly. My biggest problem is that I don't know how to change the model to get the upper bound.

To explain it, you can take a look at the image file that I attached to this mail. here each agent is in charge of executing some tasks as shown in the picture.tasks are shown as circles and the arrows shows the precedence relation between tasks. tasks {c,e} in agent 1 and {g, i} in agent 2 are mutually exclusive.

for the lower bound problem I would like to know:
(1) which tasks in each set {g,i} and {c,e} should be executed , and (2) each agent in what order should execute its tasks in order to have the minimum completion of all tasks as an objective. The code that I attached here works perfect for this problem.

However the main problem is that I am also interested to know as part of my research the worst completion time of all tasks (upper bound), in other words I would like to know:
(1) which tasks in each set of {g,i} and {c,e} should be executed , such that if each agent execute its tasks[b] in an optimal order[/b], we get the maximum completion time (upper bound) for completion of all tasks.
The problem is that my objective at an upper level is to maximize the whole completion time based on the deciding wich tasks from {c,e} and {g, i} to execute. but in the lower level and once the decision was made about this, I want these tasks to be executed in an optimal order by optimal I mean the order that gives the minimum completion time.

I hope I could explain my problem. I attached both the image and my lower bound problem which works properly . I really really appreciate your help to model the upper bound problem. Thanks a lot.



using CP;

{string} TaskNames= ...;
int cgroupNo=...;
{string} ctasks[1..cgroupNo]=...;
int AgentNo = ...;
range aa = 1..AgentNo;
int   Duration [t in TaskNames] = ...;
int Agent[t in TaskNames] = ...;
tuple Precedence {
   string before;
   string after;
   int communicationTime;
};
{Precedence} Precedences = ...;


{string} afters = {p.after | p in Precedences};
{string} conditionalTasks = union(i in 1..cgroupNo) ctasks[i];


dvar interval s[aa];
dvar interval task [t in TaskNames]  optional size Duration[t];
dvar sequence Agents[a in aa ] in
all (t in TaskNames: Agent[t]==a) task[t];

minimize max (t in TaskNames) endOf(task[t]);
subject to
{

forall( i in 1..cgroupNo)
sum ( c in ctasks[i]) presenceOf(task[c])==1;
   
forall (t in TaskNames: t not in conditionalTasks && t not in afters)
    presenceOf(task[t]);
   
forall( p in Precedences)
    {
    presenceOf(task[p.after]) => presenceOf(task[p.before]);
    if (p.after not in conditionalTasks)
    presenceOf(task[p.before])=>presenceOf(task[p.after]);
        endBeforeStart(task[p.before],task[p.after],p.communicationTime);
   }
  forall (a in aa)
  noOverlap(Agents[a]);   
     
}
execute {


  for (var t in TaskNames)
  {
  if (task[t].end != 0)
  writeln("task: " + t " " task[t].start + "..." +task[t].end );
 
  }
  cp.param.FailLimit = 1000;
 
  }



And here is my Data file:



TaskNames = {
"send-13","send-12","send-14","in-21","taur-21","in-31","taur-31","in-41", "taur-41",
"send-21","send-23","send-24","in-12","taur-12","in-32","taur-32","in-42","taur-42",
"send-31","send-32","send-34","in-13","taur-13","in-23","taur-23","in-43","taur-43",
"send-41","send-42","send-43","in-14","taur-14","in-24","taur-24","in-34","taur-34"
};
Agent= [
1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,
3,3,3,3,3,3,3,3,3,
4,4,4,4,4,4,4,4,4];

Duration=[
38, 55, 65, 7, 67, 5, 45, 6, 50
71, 36, 54, 4, 40, 3, 38, 8, 68,
42, 31, 35, 5, 49, 3, 35, 7, 63,
59, 70, 60, 7, 63, 5, 59, 4, 42];

Precedences =
{
<", "taur-21", 0>,
<", "taur-31", 0>,
<", "taur-41", 0>,
<", "taur-12", 0>,
<", "taur-32", 0>,
<", "taur-42", 0>,
<", "taur-13", 0>,
<", "taur-23", 0>,
<", "taur-43", 0>,
<", "taur-14", 0>,
<", "taur-24", 0>,
<", "taur-34", 0>,

<", "in-12", 80>,
<", "in-13", 100>,
<", "in-14", 120>,
<", "in-21", 140>,
<", "in-23", 75>,
<", "in-24", 85>,
<", "in-31", 84>,
<", "in-32", 70>,
<", "in-34", 75>,
<", "in-41", 110>,
<", "in-42", 138>,
<", "in-43", 125>
};
AgentNo = 4;
cgroupNo= 4;
ctasks= [
{"send-12", "send-14"},
{"send-21", "send-24"},
{"send-31", "send-34"},
{"send-41", "send-43"}];


#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[elham said:]

unfortunately it does not let me to upload my image. the image size is only 18k but it says that the upload folder is full.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[Didier Vidal said:]

OK.

Then to compute the worst completion time (the selection of optional tasks for which the minimal makespan is the largest) with OPL, I don't see any other solution, at the moment, than solving the minimization problem for each selection of optional tasks.
That could be automated in OPL (using a main function in javascript), but that would not scale to large datasets, since the number of problems to run would potentially grow exponentially with the size of the data.

Didier.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[elham said:]

Thank you Didier,

But since tasks have precedence relation, I am not sure how to write the script that solve the minimization problem for each selection of optional tasks. I appreciate if you show me how to write this script. I read the tutorial on "using ILOg script for opl" but I am still not clear how to write this script.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[Didier Vidal said:]

Here is a quick an dirty example. The idea is to generate all the possibilities with a CP program (cp engine in depth First mode), and then set a constraint to the model.
Note that this can lead to very long runs if the total number of combination is high.


Here is the CP model that generates all the possibilities as well as its main script


using CP;


main {
  thisOplModel.generate();
  cp.param.searchType="depthFirst";
  cp.startNewSearch();
  var  worstCase = 0;
  while (cp.next()) { 
      thisOplModel.postProcess();
      writeln("trying configuration " + thisOplModel.present);
      var dummy = new IloOplRunConfiguration("dummy.mod");
      dummy.oplModel.addDataSource(new IloOplDataSource("forcedResult.dat"));
      dummy.oplModel.generate();
      for (var c in thisOplModel.conditionalTasks) {
        dummy.oplModel.forcedResult.add(c, thisOplModel.present[c]);
      }   
      var solver = new IloOplRunConfiguration("draftcp.mod");
      solver.oplModel.addDataSource(thisOplModel.dataElements); 
      solver.oplModel.addDataSource(dummy.oplModel.dataElements); 
      solver.oplModel.generate();
      if (solver.cp.solve()) {     
        var  result = solver.cp.getObjValue();
        if (result > worstCase) {
          worstCase = result;
        }
      } else {
          writeln("Couldn't solve " + forcedResult);
      }
      writeln("End loop");
      solver.end();
      dummy.end();
  }
  cp.endSearch();
  writeln("The worst case is " + worstCase);

};


{string} TaskNames= ...;
int cgroupNo=...;
{string} ctasks[1..cgroupNo]=...;
int AgentNo = ...;
int  Duration [t in TaskNames] = ...;
int Agent[t in TaskNames] = ...;
tuple Precedence {
  string doBefore;
  string doAfter;
  int communicationTime;
};
{Precedence} Precedences = ...;


{string} conditionalTasks = union(i in 1..cgroupNo) ctasks[i];



dvar boolean present[conditionalTasks];

constraints {
  forall( i in 1..cgroupNo)
      sum ( c in ctasks[i]) present[c]==1;
};




draft.mod is the name of your main model, draft.dat of your data.

For the purpose of transfering data, I used two files, dummy.mod and forcedResult.dat

dummy.mod

tuple forcedResultT {
  string taskName;
  int presence;
};

{forcedResultT} forcedResult = ...;


forcedResult.data

forcedResult = {};


And then, in your CP model, I added some lines.

First a data declaration

tuple forcedResultT {
  string taskName;
  int presence;
};

{forcedResultT} forcedResult = ...;


And a constraint that forces the task selection

forall(f in forcedResult) {
  presenceOf(task[f.taskName]) == f.presence;


Hope this helps.
You have more examples of model scripting in the OPL distribution.

Didier.

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

[elham said:]

Thank you so much for your help. You saved me. It works wonderfull now.
#ConstraintProgramming-General
#DecisionOptimization