Originally posted by: Shirasawa

Hello,

I've been trying to model the resource-constrained project scheduling problem (rcpsp) with sequence dependent setup times by CP Optimizer (C++). I used the information of "Modeling sequence-dependent setup times and Sequence-dependent setup costs" as reference, but I haven't modeled it. I can only add the following code to the distributed sample sched_rcpsp.cpp:

IloIntArray2 setupDuration(env, nbTasks);
for (IloInt ti=0; ti<nbTasks; ++ti) {
setupDuration[ti]= IloIntArray(env, nbTasks);
for (IloInt tj=0; tj<nbTasks; ++tj)
setupDuration[ti][tj] = ...;
}
IloTransitionDistance dist(setupDuration);

An instance of transition distance is used in the no-overlap constraint (IloNoOverlap), but, in the rcpsp, overlaps are permitted between tasks that are done by the same resource. So, in this case, IloTransitionDistance might not be used. Could you please tell me how to model it? I urgently need your help. Thanks all for any help.

Originally posted by: PhilippeLaborie

Hello,

Setup times are usually defined on a set of non-overlapping activities. In the case of cumulative resources like RCPSP, how would you define the setup time between two activities and what is it supposed to model ?

Philippe

Originally posted by: Shirasawa

Dear Philippe

It sure is. Setup times are usually a set of non-overlapping activities, but they are also considered to be a set of activities where overlapping is allowed. A nice example of the later setup time may be called a schedule-dependent setup time (SDT). Please refer to the following paper for SDT (Mika et al. 2008, Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times. European Journal of Operational Research, 187(3), 1238-1250.).

I quoted a sentence from the this paper.

"A schedule-dependent setup time is defined as a setup time dependent on the assignment of resources to activities over time, when resources are, e.g., placed in different locations."

"... schedule-dependent setup times occur when setup-required resources have to be transported or transmitted from one location to another in order to prepare a resource unit in the latter location for executing an activity."

Originally posted by: PhilippeLaborie

I see. For a pair of tasks with precedence constraint ai->aj, the delay of the precedence will depend on the allocated modes (resp. mi_k, mj_l). You have several ways to model that in CP Optimizer:

1. You can post precedence constraints between each pair of optional interval variables representing the different modes with the adequate delay: endBeforeStart(mi_k, mj_l, setuptimei_k->j_l).

2. You can create an integer variable that returns the mode modei associated with each task ai. If PRES is an array with the presenceOf expressions of the modes: PRES=[presenceOf(mi_1),presenceOf(mi_2),...] you can for instance do something like: PRES[modei]==1. Then you can have a delay expression between ai and aj that depends on the mode: endBeforeStart(ai,aj,SETUPTIME[mi][mj])

3. As mentioned in the article you referred to, in practice these setup times correspond to some items that are necessary for executing the activities and that need to be moved from one location/machine to another. If in your real problem you can identify these items, you could create one CP Optimizer state function for each of these items with a transition distance stating that a given item can be only at one position at a time (but tasks using this item can overlap, provided they require the item to be at the same location) and that there is some setup time to move the items. The state of the state function (alwaysEqual(stateFunction, state)) would define the location of the item.
 

Hope it helps,

Philippe

Originally posted by: Shirasawa

Dear Philippe,

Many thanks for the prompt reply, I really appreciate your help. According to the proposed approach, I will give it a try and let you know if I need further help.

Regards

Shirasawa