Originally posted by: stoneren0316

Hello,
I am working on some flexible job shop like problem using CP Optimizer. In my problem, there are machines with multiple slots (maybe 3 slots). this means one machine of this kind can do 3 tasks one time at most. These 3 tasks have the same duration and must start at the same time.

For example,
Machine M has 3 slots;
job A has 3 sub-tasks and the 1st task must be processed on Machine M;
job B has 4 sub-tasks and the 2nd task must be processed on M.
Machine M can process the two tasks (maybe more) in parallel. If this happens, the two tasks must start and end at the same time.

Is there any way to model or solve the problem? 

Please help me.

Thanks a lot.

Originally posted by: stoneren0316

To simplify the problem, Let machine M must be full filled (3 tasks must be processed together).

Any help will be appreciated!

Originally posted by: ChrisBr

Hello Jie,

A way is to model using cumul-functions and state-functions.

For example you would define:
For the sake of simplicity, the samples are given here in OPL; of course, every features are available in other APIs (C++, Java, .Net, Python).

cumulFunction machineM = sum (s in SubTasks) pulse(subTask[s], 1);

where subTasks is an array of interval variables.

stateFunction state;

a state function used to manage the synchronization.

Then the constraints would look like:

machineM <= machineCapacity

This constraint is used to confine the values of the cumulFunction machineM to a non-negative range [0, machineCapacity].

forall(s in SubTasks)
  alwaysEqual(state, subTask[s], States[s], 1, 1);

This constraint specifies that the state function state must be defined, constant and equal to non-negative value States[s] everywhere between the start and end of interval subTasks[s], if the interval is present.
The two last parameters 1,1 mean that interval subTasks[s] is start-aligned with state function state, so interval subTasks[s] must start at the beginning of the interval where state is maintained. And interval subTasks[s] is end-aligned with state function state, so it must end at the end of the interval where state is maintained.

You might have a look at the distributed sample Wood cutting problem.

I hope this helps,

Chris.

Originally posted by: stoneren0316

Hello Chris, 

Thank you for your help.

I have read the cumul function and the state function, but I still don't quite understand your method. I have two questions below.

1. Should I in advance calclate how many times the machine M need to run , and make every run num as states of the state function?

2. How to connect the tasks with the states  (by using alwaysEqual), when the run order of tasks is unkown.

I'm new in CPLEX and I'm not familar with OPL, forgive me if I don't get your point.

Best regards.

Jie.

Originally posted by: Petr Vilím

Let me try to explain it differently. What you're describing seems to be "batching". Batch is a group of tasks that are processed together: they start together and end together. It is not known in advance how tasks will group together to form batches. Typically there is a maximum number of tasks in one batch (3 in your case).

It is necessary to use multiple constraints together to model all the aspects of the batching. To model one batching resource you need one cumul function, one state function and:

1. Each task should contribute a "pulse" on the cumul function. Then the maximum size of the batch is modeled by constraining the cumul function to be less then 3 (in your case).
2. Often only "compatible" tasks could form a batch. A typical example we use is an oven: you can bake multiple products in an oven however only if they require the same temperature. The temperature of the oven is the state of the state function. Tasks then require that the state function has particular value during their execution (i.e. the oven has the right temperature). It is typically modeled using alwaysEqual constraint (one alwaysEqual constraint per task). This way incompatible tasks (that require different states) cannot overlap.
3. When two tasks overlap then they have to start together and end together. We call it alignment. It is also modeled by state function, in particular by optional boolean parameters startAlign and endAlign of functions alwaysEqual and alwaysConstant. When both startAlign and endAlign are true for two overlapping tasks then they must start and end at the same time (and therefore form a batch).

In your case it seems that all tasks are compatible (you didn't mention any compatibility constraints). So you don't need alwaysEqual described in item 2 for this purpose. However you still need state function because of the alignment (item 3 above). So you may use the same value in all alwaysEqual constraints (in the oven example, all tasks require the same temperature), or you can use alwaysConstant constraint instead (since you don't really care about the actual value of the state).

So back to your questions:

• You don't need to calculate in advance the number of batches. It is not used in the model.
• The state could be always the same in alwaysEqual or you can use alwaysConstant instead.

I hope it helps, Petr

Originally posted by: stoneren0316

Hello Petr,

Your reply is exactly what I need and your descriction is so clear.

I have written the testing code and it works well.

Thank you very much!

Now I meet another problem when I try to limit the lower bound of the machine M capacity.

I tried to use IloAlwaysIn for every task on machine M to control the range of the cumul function like below, unfortunately it doesn't work.

model.add(IloAlwaysIn(env, cumulFunc, task[i], 2, 3));

The cp solve method return false when this constraint added.

(I believe there are feasible solutions for my data.)

(model.add(IloAlwaysIn(env, cumulFunc, task[i], 1, 3)) works well.)

I don't know why.

could you give me some advice?

Best regards

Jie

Originally posted by: Petr Vilím

I'm glad it helps. I think that what you did is right. I assume that task[i] contributes a pulse of size 1 to the cumulative function and cumulFunc is the function constrained to be <= 3. Maybe try to experiment with a really small problem so you can be really sure there is a solution? AlwaysIn with range 1..3 works because the constraint is satisfied simply by the pulse of that task.

Note that this kind of constraint does not propagate well, it may quite hurt the performance. By my experience, size of the batches increase naturally as the result of minimizing some other criteria such as makespan. Initial solutions may not be the best, but as makespan improves size of the batches increases. Of course, I don't know your reality of your problem. And you may optimize something else than makespan. But if batches of size >1 are not really mandatory then I would not add such a constraint. Especially if the motivation is just in order to get better solutions faster. Because on contrary, it may make the initial solution harder to find.

Petr

Originally posted by: stoneren0316

Hello Petr, 

Your advice really helps me a lot.

I tested on really small data.

In my problem, it is necessary to have the lower limit of product quantity of one cycle controlled, while the performance is even more important.

So I am considering to resolve it by batching the tasks in advance or by aligning them after solved.

By your experience, do you think these are usual ways？

Jie

Originally posted by: Petr Vilím

Hello Ji 

modeling a real-life problem as a math problem is very often in some ways inaccurate. Also the computed schedule is usually not followed in practice in every detail. It depends on the particular problem of course. The effectivity of the solver is another point. So for practical problems it is usually necessary to find a a mathematical model that is close enough the the real-life problem (so that the results are useful) but on the other hand still tractable by the solver. And therefore models may ignore some less important aspects of the problem.

So yes, you're thinking in the right direction. Designing the right model is a kind of art and it usually involves some amount of trials and errors. Post-processing of the computed schedule is very common technique. It is also common to optimize in multiple phases, e.g. first design a big high-level plan (such as batching) that ignores most of the problem and then extend the model by additional details and optimize the details (e.g. exact timing). My advice would be to try several different approaches. Do not put all your effort into only a single approach. It is hard to say in advance which one will work the best, the more you try the better results you may find.

To elaborate on another approach you mentioned. You can first optimize without the batching, then postprocess the schedule to fix the batching, and then you can even start from the this postprocessed solution and optimize again with the constraints for the batching (you give CP Optimizer an existing solution as a "starting point"). So there's really a lot of possibilities. It is even possible to use different solvers for different phases (in particular you may solve MIP models using CPLEX).

Best regards, Petr

Originally posted by: stoneren0316

Hello Petr,

I learned a lot from you.

Thank you.

Jie