Originally posted by: SystemAdmin

Hi,
I've attached a parallel machine scheduling model that I got working today with some help from the forum concerning transition times.
It's rather complicated, but the gist is this:
1. each machine (really a vehicle) has multiple route legs.
2. Every task can be done on certain specified machine/leg pairs.
3. Each such machine/leg/task tuple can have multiple time windows associated with it.
4. For each machine/leg/task tuple, no matter how many time windows associated with it, the task duration and the value received is the same.
5. Transition times are different for every machine/leg pair.
6. All tasks are optional.

I have modeled all of the above and I maximize the value of the scheduled tasks. Everything works fine. What I noticed, though, is that if I change a time window for one particular task, j, such that it won't be in the solution, the whole problem returns 'no solution'.
Below is my .dat file. In the set 'tWindows, I have "<<<2 1> 4> 44 52>" which means that vehicle 2, leg 1, task 4 is feasible in 44-52. In 'opps', you can see that it has a duration of 8. If the window is instead 44-53, you will see that the model solves and vehicle 2, leg 1 does task 1 from 41-43, takes 5 seconds to transition to task 4 and then does task 4 from 45-53.
Using 44-52, however, the entire model has no solution which seems invalid since vehicle 2, leg 1 can still do task 1, for instance.

Can someone tell me what I've done wrong in a model that otherwise seems to do exactly what I want it to?
Thank you!

/********************************************* * OPL 6.3 Data * Creation Date: Jan 28, 2010 at 3:42:59 PM *********************************************/ platforms       = 
{ 1 2 
}; tasks           = 
{1 2 3 4
}; legsPerPlatform = [2  1]; oppIDs          = 
{ <<1 1> 1> <<1 1> 2> <<1 2> 1> <<1 2> 2> <<2 1> 1> <<2 1> 2> <<2 1> 3> <<2 1> 4> 
}; platLegs        = 
{ <1 1> <1 2> <2 1> 
}; opps            = 
{ <<<1 1> 2> 8 1345> <<<1 2> 2> 10  150>   <<<1 2> 1> 7 88888> <<<2 1> 1> 2 4560> <<<2 1> 3> 14 100000> <<<2 1> 4> 8 15098> 
}; tWindows        = 
{ <<<1 1> 2> 10 21> <<<1 2> 2> 34 56> <<<1 2> 2> 60 80> <<<1 2> 1> 33 36> <<<2 1> 1> 41 49> <<<2 1> 3> 0 101> <<<2 1> 4> 44 52> 
}; 
//transition times are symmetric!!                   transTimes      = [ 
{
},                                                 
//platform 1, leg 1 
{ <1 2 10> <2 1 10> 
},                              
//platform 1, leg 2 
{ <1 3 5> <1 4 2> <3 1 5> <3 4 7> <4 1 2> <4 3 7> 
} 
//platform 2, leg 2 ];

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,
With time window <<<2 1> 4> 44 52>, your model is indeed infeasible.

Task indTasks[1] has 2 alternatives in: alternative(indTasks[i], all(t in opps: t.oppID.tInd == i) tasksOnMachines[t]);
These two alternatives are: tasksOnMachines<<<1,2>,1>> and tasksOnMachines<<<2,1>,1>>.
But the time-window of <<<1,2>,1>> (33,36) is inconsistent with its duration (7).
Thus, the only possibility for indTasks[1] is tasksOnMachines<<<2,1>,1>> that will require its machine (<2,1>) for a duration of 2 somewhere over time-window 41,49.

Now, if we look at task indTasks[4] it only has a single alternative: tasksOnMachines<<<2,1>,4>> with a duration of 8 on the same machine as above (<2,1>).

If the time-window is 44,53, the solution is to first execute indTasks[1] on [41,43) followed by the transition between state 1 and state 4 (tt=2) and then, indTasks[4] on [45,53). If the time-window is 44,52, the model is infeasible.

If your model is oversubscribed, you can make those tasks optional and include in the objective function a term to maximize the number of executed tasks.
Hope it helps,

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Philippe,
Thank you - that was a naive CP modeler's question - my heuristic certainly does not force all tasks to be scheduled, and based on some of the examples of 'optional task scheduling' that I found in the documentation and in the forums, I thought that 'indTasks' couldn't be optional when 'tasksOnMachines' was also optional.
Anyway, that is fixed, and I have two purely syntactical questions.

1. In the model I attached, I declare an array of step functions where the index is over a set:
stepFunction Ft in opps".
Earlier in my figuring this out, I had indexed the step function by an array. Thus, in an 'execute' statement, I was able to output an individual step function. Now, though, I can't - using 'nextc' or 'first' or anything like that, I can't output, say, F[1] or F[t] where t = first(opps).
Is it possible to do this when indexing over a set?

2. I declare an array of transition time sets, 'transTimespl in platLegs' which only creates a set of transition times for vehicle/leg pairs that actually exist. This is to keep the model as sparse as possible. However, some vehicle/leg pairs have only one task on them - i.e. there are no transition times for that vehicle/leg pair. For now, I declare an empty transition time set, {}, but I'm wondering if that is highly inefficient? I.e. with 50 vehicle/leg pairs in a problem, would a number of empty sets create wasteful extra variables that slow the solve down?
Thank you,
William
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

sorry - it should read as Ft in opps and transtimespl in platLegs.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

For your first question, you can do as follows:

execute 
{ 
// Display first function var t1 = Opl.first(opps); writeln(F[t1]); 
// Display all functions 

for (var t in opps) 
{ writeln(F[t]); 
} 
};

For your second question, it is true that you can save some memory by testing whether or not the transition time is empty when posting the noOverlap constraints:

forall(plLegs in platLegs) 
{ 

if (0==card(transTimes[plLegs])) 
{ noOverlap(solnRtes[plLegs]); 
} 

else 
{ noOverlap(solnRtes[plLegs], transTimes[plLegs]); 
} 
}

But unless you work with very large matrices, it should not have a large impact.
Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Please disregard the question about printing individual step functions - I looked into OPL scripting and discovered that functions sufficed and from that I learned that:
var i = 1;
for (var opp in opps) {
writeln("Step function " + i++ + ": " + Fopp);
}
would suffice.
The other question still stands, however.
Thank you.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

thanks again - you are very kind to give so much help on this forum.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: flywithme

Dear Dr.

I am working a problem similar to yours very much, can i know your mail address, so we can exchange ideas. my mail address renjiehe@live.cn.
#DecisionOptimization
#OPLusingCPOptimizer