Originally posted by: SystemAdmin

Hi,
I'm old to LP and IP modeling using CPLEX Callable Library but am new to CP and having a very difficult time. I am trying to model a scheduling problem similar to the one discussed at http://www.ibm.com/developerworks/forums/message.jspa?messageID=14401029#14401029 in order to compare the result against that of a heuristic I developed.
The problem is this:
1. k vehicles (machines) are available.
2. n tasks are available for scheduling, all of which are optional.
3. Each task may be possible to schedule on a subset of vehicles.
4. Each feasible task/vehicle pair may have 1 or more time windows.
-Associated with each task/vehicle/time window triple is a processing time, a utility, and a set of transition times to all other tasks on that vehicle.
5. Each time window is at least as large as the processing time associated with it.
6. Each task can only be done once (across all machines) and each machine can only work on one task at a time.
7. The objective is to find the schedule that maximizes the utility over all machine.

Since the above is complicated enough, for now, there is no preemption and no 'clustering' of tasks together although once I learn how to do this model correctly, I'd like to extend it to those.

My first question is completely technical: In the user manuals and white papers I've found going through OPL examples, transition time is modeled as a triple. E.g. in the gsoplsched.pdf file found in OPL's documentation, this is what they say: "Transition times can be modeled using tuples with three elements. The first element is the interval variable type of one task, the second is the interval variable type of the other task and the third element of the tuple is the transition time from the first to the second. An integer interval variable type can be associated with each interval variable."
I thought this means that I could create a tuple type that represent the "from" and "to" portions of the triple but I simply cannot get the syntax to work correctly. I.e. declare tuple TransitionIJ{ allocOpp i, allocOpp j, int time}, create a {TransitionIJ} transTimes set, and then call noOverlap(sequenceVar, transTimes)
but I cannot get it right.

2. Here is my model: I haven't gotten to using the step function to model the time windows, but even without that, I'm trying to understand why this model seems to output garbage. Note that each vehicle's time period is currently divided into a set of consecutive route legs though I think I could successfully get rid of that if it's more efficient. Please also note that I have commented out the transition time stuff since I can't even get the syntax right and I am currently simply trying to solve the satisfiability problem before trying to get the objective function correct.
*****************
using CP;

tuple VehicleLeg { //this compartmentalizes the reference to a particular leg for a particular vehicle
int vehicle;
int leg;
//we don't need to know the start/end time for each leg since each allocOpp has its own time windows
};

tuple allocOpp { //this captures the platform and leg for a task
key VehicleLeg vehLeg;
key int task; //the task that this allocOpp would accomplish
int numTW; //the number of time windows that this allocOpp has (usually just 1)
float pTime; //processing time for a particular task on a particular platform and leg
//(note that if there are multiple time windows for this allocOpp, the duration
//is the same for all of them)
int value; //the utility gained by accomplishing the task associated with this allocOpps
int glIndex; //a global list of all allocOpps; my idea was to make it easier since some allocOpps have multiple time windows
};

tuple TimeWindow { //this captures each time window for a particular allocOpp/vehicle pair (and identifies what index time window it is for a particular allocOpp/vehicle pair)
key int glIndex; //relate the time window to its allocOpp w/o having to write out the entire allocOpp
key int twNum; //twNum == 1..numTW for this allocOpp (i.e. where glIndex = tao.glIndex)
float start;
float end;
};

tuple TransitionIJ { //the tuple that is used to build our transition time matrix
allocOpp i; //transition from allocOpp i to allocOpp j
allocOpp j;
int tIJ; //we MUST use integer transition times unfortunately;
};

{allocOpp} opps = ...;
{VehicleLeg} rtes = ...;
{TimeWindow} tWindows = ...;
{TransitionIJ} transTimes = ...;

int n = ...; //number of unique tasks
int K = ...; //number of vehicles

dvar interval taskshttp://i in 1..n; //there are n tasks we're trying to do (none is required to be done); each may have multiple allocOpps (a maximum of one allocOpp per vehicle leg)

//This is the array of all allocOpps. Each is associated with a task (a many-allocOpp-to-one-task relationship).
//Not all of them necessarily can be scheduled which is why they are optional.
dvar interval tasksOnMachinesopps optional;

//this declares the set of K vehicle sequences, i.e. solutions for each vehicle;
//IFF task t is doable by vehicle k, then there is at least one t in opps for it and thus this particular task/vehicle pair can appear in vehicle k's
//solution sequence.
dvar sequence vehicleshttp://k in 1..K in all(t in opps: t.vehLeg.vehicle == k) tasksOnMachines[t];

//maximize sum (t in opps) t.value;

constraints {
forall(i in 1..n)
alternative(tasks[i], all(t in opps: t.task==i) tasksOnMachines[t]);
forall(k in 1..K)
noOverlap(vehicles[k]);//, TransitionIJ);
};

Thank you for giving any help on what areas of the model I'm going wrong in and how I should move forward. I'm sure most of this is rather elementary - I think my biggest issue is how to link the time windows with the tasks as that just is not happening right now.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Didier Vidal

Hi,

To answer your first question about the use of transition time, the trick is to define the type of each interval in the sequence. To illustrate this, I have written below a small examples that uses your notation. Hope this helps.
Didier.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Didier Vidal

Sorry,
The attachment with code example wasn't uploaded yesterday. Second attempt.

Didier.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Thank you Didier -your model was very helpful, and using this as a starting point, I finally found an example in the documentation that explained more about what "type" meant in terms of the noOverlap function and transition times.
Thank you!
William
#DecisionOptimization
#OPLusingCPOptimizer