Originally posted by: Robert.mhf

I've come up with a task scheduling and resource allocation problem in which resources can start running a new task with a complex condition.

•     A resource can start a new task on an even time unit if at least 2n time units has passed from starting the previous task started on an even time unit.
•     The same holds for odd time units.

Below is a valid scheduling on a single resource. Each number represents that a new task has been started at that time.

•     0, 1, 2n, 2n+1, 4n, 4n+1, ...

I've got a lot of tasks with precedence relations in between (I know how to cope with the precedence relations) and several resources of this kind. I carried the scheduling out the following way which does not yields an optimal result:

•     Although a task can start on an odd or an even time unit, I've constrained half of the tasks to start on even time units and the other half on odd time units using "forbidStart" and "stepFunction".
•     Per resource s, I've considered two "cumulFunction"s s_even and s_odd.
•     Tasks that are forbidden to start on even (odd) time units need the s_odd (s_even) resource. I defined this constrained using "cumulFunction" and "pulse".

Although the above procedure produces a valid scheduling, it is not enough since I'm seeking for an optimal solution. Does anybody have any idea how to carry out this problem in CPLEX?

Originally posted by: PhilippeLaborie

It seems to me that your model almost does everything except for the allocation of the task to one of the two "resources".

I suppose that in your model, the duration of the interval variables on the resources is 2n, right?

I would just consider an additional interval variable 'task' of length 2n that represents the task and have an alternative on two optional tasks 'taskEven' and 'taskOdd'. These two intervals are the ones you already have in your model (with the adequate forbidStart constraints, and with a contribution to the adequate resource).

Note that instead of a cumul function you could use a noOverlap for the resources as they have a unit capacity, this may be useful if you have additional constraints on the sequencing of the tasks on these even/odd sequences.

Note also that instead of forbidStart, you could use something like: startOf(x,0)%2 == 0 (for the even tasks) and startOf(x,1)%2 == 1 for the odd tasks).

Originally posted by: Robert.mhf

Thanks for your immediate help and exact response.

I've got another question regarding the nooverlap constraint you suggested to use in the case resources have a unit capacity. In my case, there are more than one of such resource. Is there any way to use this constraint. Actually, I want to see which task has been scheduled on which resource? I thought maybe the nooverlap constraint could be useful.

Originally posted by: rdumeur

Dear Robert.mhf

If you want to determine which alternative is selected you can access the presence attribute value of the interval.

You might be interested to have a look at the  sched_rcpspmm example in:

    <CPLEX STUDIO INSTALLDIR>/opl/examples/opl/sched_rcpspmm 

which uses the presenceOf expression.

I hope this helps,

      Cheers,