Originally posted by: WeeLoon

Hi all,

dvar interval assignment[t in Tasks][e in Eqps] optional size processing_time[t][e]; 
cumulFunction F [e in Eqps] = sum(t in Tasks: t.type != "Clean") stepAtEnd(assignment[t][e], e.height)
    - sum (t in Tasks: t.type == "Clean") stepAtStart(assignment[t][e], 0, 9999);
forall (e in Eqps)
    F[e] <= e.limit;  

Some tasks are processing in batch. I need to divide e.height by the number of tasks processing in each batch, but I just can't think of a way.

In another sense, supposed e.height is 100, if there is only 1 task is processed in a particular batch, then the cumulFunction F should increase by 100. If 2 tasks are processed in batch (start and end at the same time), the total height increase should also be 100 (instead of e.height + e.height = 200). I can't use endOf(assignment[t][e]) with cumulFunction F since it is a decision variable.

Any help would be greatly appreciate. Thank you.

Hi

at some point you want to write

F[e]<=maxCumul;

You could also write

F[e]<=maxCumul * x[e];

Could that help in your case ?

regards

Originally posted by: WeeLoon

Hi Alex,

Sorry for not phrasing my problem correctly. I am afraid your suggestion might not work in this case, as I need to trace the exact value of cumulFunction F from start to the end.

Pls allow me to restructure my model with more details.

dvar interval assignment[t in Tasks][e in Eqps] optional size processing_time[t][e]; 
cumulFunction F [e in Eqps] = sum(t in Tasks: t.type != "Clean") stepAtEnd(assignment[t][e], e.height)
 - sum (t in Tasks: t.type == "Clean") stepAtStart(assignment[t][e], 0, 9999);
forall (e in Eqps)
    F[e] <= e.limit;  

Let e.limit be 150 and the initial value of F be 0, after first task completed, F becomes 100, after second task completed, F becomes 200, so another tasks of type clean will be chosen to be run to reset F to 0. As mentioned, 2 tasks might be executed in batch, what i would like to achieve is, for each batch, whether there is only one task or two tasks, the F is increased by 100, instead of 100+100 = 200.

Thanks for your help.

Originally posted by: Petr Vilím

Hello,

let me rephrase what I understood so far about the problem (and correct me please if I'm wrong). Your resource has some kind of "dirtiness level" and each batch increases this level by 100 regardless of the size of the batch (in particular regardless the number of overlapping interval variables that form the batch). There's maximum dirtiness level and cleaning activities that could be scheduled in order to reduce the dirtiness level.

What is not clear to me though is what exactly is a batch. Do you already have a model for the batches that ignores dirtiness? Activities in a batch have to start together and end together? How many activities could be in a batch? Etc. It is common to have multiple cumul functions for one physical resource in order to model all of its aspects. Or cumul and and a state function. Modeling of dirtiness depends a lot of the model of the batches and so we cannot answer without knowing more details.

Thanks, Petr

Originally posted by: WeeLoon

Hi Petr,

Thanks for your reply.

You are right. I have some tasks to be executed on some equipment. These tasks are mandatory. In the mean time, I have cleaning task that are optional and they only need to be executed when the dirtiness level reach the limit. For batching, supposed the batch size of a equipment is 2, this means at most 2 tasks can be executed on the same equipment at the same time, and they need to start and end at the same time.

For now, I have completed the batching concept. What I am stuck with is, how to increase the dirtiness level regardless of the number of tasks in a batch and to force the optional cleaning task to be executed once the dirtiness limit is reached.

dvar interval assignment[t in Tasks][e in Eqps] optional size processing_time[t][e];

cumulFunction DirtinessLevel[e in Eqps] = step(0, e.initialDirtinessValue) 
        + sum(t in Tasks: t.type != "CLEAN") stepAtEnd(assignment[t][e], e.dirtinessValue)
        - sum(t in Tasks: t.type == "CLEAN") stepAtStart(assignment[t][e], 0, 99999999)
        + sum(t in Tasks: t.type == "CLEAN") stepAtEnd(assignment[t][e], e.dirtinessValueAfterCleaning);

dexpr int totalCycleTime = sum(t in Tasks, e in Eqps) endOf(assignment[t][e])

cumulFunction BatchSize[e in Eqps] = sum(t in Tasks) pulse(assignment[t][e], 1);

//Some constraints for batching tasks. Tasks need to satisfy certain conditions to be executed together. I already finished this part.

forall(e in Eqps)
  BatchSize[e] <= e.batchsize; 

forall (e in Eqps)
  DirtinessLevel[e] <= e.DirtinessLimit;

forall (t in Tasks: t.type != "CLEAN")
  sum(e in Eqps) presenceOf(assignment[t][e]) == 1;
   
forall (t in Tasks: t.type == "Clean")
  sum(e in Eqps) presenceOf(assignment[t][e]) <= 1;  

For example, for equipment E1, the initial dirtiness level is 150 and the dirtiness limit 300. 

Now I have 2 tasks, T1 (t.dirtinessValue = 100) and T2 (t.dirtinessValue = 100). If T1 is executed alone, upon completion, the dirtiness level will become 250.

If  T1 and T2 are executed in batch, the dirtiness level should become 250 instead of 350 (this will decide whether the cleaning task is triggered).

Thanks everyone for helping me.

Originally posted by: Petr Vilím

It seems that dirtinessValue could be different for each task. What if there is a batch consisting of two tasks with two different dirtinessValues? Could it happen? I have in mind a model that increases dirtiness for each batch but it cannot be configured for each task.

Thanks, Petr

Originally posted by: WeeLoon

Each task may have different value of dirtiness. However, for 2 tasks to be executed in batch, they must be of the same type, and their dirtinessValue will always be the same.

Originally posted by: Petr Vilím

Hello,

here is a solution suggested by my colleague. For simplicity I will call the real tasks (interval assigment in your model) Ai where i is an index. The idea is to introduce for each Ai another optional interval Bi such that: 

presenceOf(Bi) => presenceOf(Ai)
startAtStart(Ai,Bi)
endAtEnd(Ai,Bi)

For a given batch, we want that one and only one of the Bi corresponding to the Ais in the batch is present, this Bi will represent the "batch interval". This can be done by creating a cumul function (only one for the machine) :

batch = sum_i pulse(Bi,1)

And:

alwaysIn(batch,Ai,1,1)

So Ai requires batch cumul function to be 1 during Ai. Therefore some Bi must be present in order to increase the value of batch cumul function. However not more than one Bi could be present because then the value of the cumul function would be too high. You can use intervals Bi to increase dirtiness of the resource accordingly. The cost of the extra modeling is not huge and the intervals Bi are always synchronized with the Ai so they will be fixed more or less together in the search.

One can also post the redundant constraint:

batch <= 1

And maybe (though they can be less useful):

alwaysIn(batch,Bi, 1, 1)
noOverlap([Bi])

Experiment with those constraints for yourself whether they help (and it is always recommended to experiment with multiple data sets or at least multiple settings of RandomSeed parameter in order to avoid making decisions based on just one run since one run could be just very lucky/unlucky).

The only issue with this model is the introduction of many symmetries due to the selection of which Bi is present in a given batch. I.e. there are many equivalent solutions that differs only in selection of Bi. This can be fixed by using an additional state function (again, only one for the machine) 'minID' with the following constraints:

alwaysIn(minID,Ai,0,i)
alwaysEqual(minID,Bi,i)

This will ensure that among the Bis in a batch only the one corresponding to the smallest index i in the batch is selected. Again, try for yourself, sometimes breaking symmetries is counterproductive.

Best regards, Petr

Originally posted by: WeeLoon

Dear Petr,

Your colleague's solution works like a charm. The increasing of cost for modeling are quite obvious though, as my model is huge. I will see what I can do to improve the performance. Thank you.

Besides, my DiirtinessLevel cumulFunction above will sometimes perform the cleaning task even the DirtinessLimit is not reached yet. Do you have any idea how to force the cleaning task to start ONLY after the Dirtiness Limit is reached?

Best regards, Lim.

Originally posted by: WeeLoon

Dear Petr,

My DirtinessLevel cumulFunction above will sometimes perform the cleaning task even the DirtinessLimit is not reached yet. Do you have any idea how to force the cleaning task to start ONLY after the Dirtiness Limit is reached?

Best regards, Lim.

Originally posted by: ChrisBr

Hello Wee Loon,

I suggest to try something like:
alwaysIn(DirtinessLevel, cleaningTask, DirtinessLimit, (maxint div 2)-1);
or if DirtinessLimit is never exactly reached:
alwaysIn(DirtinessLevel, cleaningTask, DirtinessLimit-delta, (maxint div 2)-1);

see cumul-functions doc.

However, this constraint could appear to be too strong.

In that case you could try to use a searchPhase instead. Setting cleaning-tasks at the end of the searchPhase would forces the search to instantiate other tasks in priority and we can expect that the cleaning-tasks would be instantiated by the propagation process.

I hope this helps,

Chris.

Originally posted by: WeeLoon

Hi Chris. Sorry for late reply.

May I know, what do you mean by the constraint could be too strong. For delta, what value should I put?

Thank you, Chris.

Originally posted by: PhilippeLaborie

The constraint alwaysIn(f, itv, vmin, vmax) states that the value of function f during interval itv must always be in the range [vmin,vmax]. Thus the proposed constraint alwaysIn(DirtinessLevel, cleaningTask, DirtinessLimit, DirtinessLimit) states that in order to perform a cleaning task, the level of dirtiness must be equal to DirtinessLimit, so you will never execute a cleaning task if the level is smaller. Of course, this constraint can be used if you are in a model where the cleaning task decreases the dirtiness level at its end time. In case of a formulation where the cleaning task decreases the dirtiness level at its start time, you would need an additional very small interval variable (e.g. length=1) that ends at the start time of the cleaning task and post the alwaysIn constraint on this interval.

The constraint may be too strong because depending on the dirtiness of the tasks, you may not be able to *exactly* reach the dirtiness limit. For instance if your dirtiness limit is 153 and all your increments of dirtiness by tasks are multiple of 2, then level 153 can never be reached and the model would be infeasible. That's the reason for introducing a delta which clearly depends on your context. 

Originally posted by: WeeLoon

Dear Chris and Philippe,

With slight modification, your solution works exactly as what I intended. Really appreciate your help. Thank you.

Best regards,

WeeLoon