Originally posted by: Tobias_

Hello,

the following situation, a task T can be proccesed from machine A and machine B.

Machine B is 20% faster then machine A, because machine B is a new modell.

The percentage value  is a fixed value that is given one time in the model and don't change.

 

I allready modeld most of the workshop, following the scheduling tutorial. (https://ibmdecisionoptimization.github.io/tutorials/html/Scheduling_Tutorial.html)

I also found the example 'setup_times.py" (file is attached)

 

In the setup_times example, is for every machine a list with tasks and the associateddurations.

Im not happy about this method, because when the amount of machine increases there have to been handeld with many lists.

One workaround I thought about to handle the problem with a delay.

The duration for task T is specified for machining on machine B.
If task is scheduled on machine A, a delay is added. 
Time(maschine_A) =  duration[T] * 1,20

But this seem also not to be that easy and also the visualisation won't be really readable.

Is there a function provided for this problem in docplex?
Or has anyone a smarter idea to solve this problem?
 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Petr Vilím

Hello,

I looked at your code and it seems to me perfectly accurate. What exactly is the issue? You said:

I'm not happy about this method, because when the amount of machine increases there have to been handled with many lists.

Are you talking about the size of the matrices for setup times or about the list of durations? Approximately how many tasks do you have in mind? Or you're going to add more machines? How many then?

The current model has optional interval variable for every pair (task, machine). Having one additional integer value in a list of durations for a particular machine is not an issue (interval variable is quite heavier than one integer).

Regarding matrices of setup times, they grow quadratically with the size of tasks. That could be a bigger issue. The preferred way to address it is to introduce "types". Each task may have a type and setup time is specified between different types (not before tasks directly). This way, when number of types is smaller than number of tasks, the matrix size could be reduced.

Note that optional interval variables and setup times given by setup matrix lead to the best propagation during the search. Setup times could be modeled differently (in particular by functions such as typeOfNext, startOfNext etc) however it not propagate as much. As the result the performance may degrade dramatically and the memory consumption could be even bigger (since search tree becomes deeper because of missing propagation).

Best regards, Petr

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Tobias_

Hello Petr,

thanks for your answer.

The posted file is only a example I found and not my actual model.

 

I'm wory about to handle for every machine a task list.

In the example it is named 'tasks_m1 = [mdl.interval_var(...)]'

 

My current prototype has 5 machines, but for the final product it can be up to 20 machines.

I also need only the different durations, setup times are no problem i have to handle.

The amount of tasks can variat between 10 up to 1000 or more.

It depends on how long the schedule should reach into the future.

My actual design is a similar to the design of the problem that is posted here (file: CP-Schedule.py)

 

So I have actual the following design for oders:

       order_0 = ([needed workings], [durations], [start-, end-time], [precedences])

and in the model, a interval_var for the needed workings:

       itvs[(a,w)] = mdl2.interval_var(size = durations, name=name) [a = count variable / w = workings]

also a list of maschines with skills, there machine 2 and machine 3 can do the same working, but machine 3 has a better skill level (means faster production):

       machines = [('machine_1', 'working_1', 1), (' machine_2', 'working_2', 1), ('machine_3', 'working_2', 3), ...]

 

So in my opinion to make for every machine a task list is brings an overhead that have to be handled.

Because for some tasks is only one machine avaible so there is only one duration time.

But for about 20% of the workings are two or more machines avaible with different durations for the tasks.

 

This is the reasons why I am looking for a way to give the information about the longer/faster duration with the machines and not with the tasks.

I hope it is now more clear what I mean and want to model.

 

But you wrote that there is a maybe a way to do this with 'types'.

I'm very new to the program, so have you any example or description how to use this?

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Petr Vilím

Hello Tobias,

types could be used to model setup times. For example, tasks A and B can have type 0 and tasks C and D type 1. When setup times may be given between types and not between tasks directly. I.e. setup time between A and C is the same than between B and D because in both cases it is a setup from type 0 to type 1. Then the matrix could be reduced from 4x4 (between tasks) to 2x2 (between types).

Let's take a step back. The main power behind constraint programming is constraint propagation. Every constraint you put into your model has propagation algorithm behind that tries to recognize infeasible values of involved decision variables. Such infeasible values are removed from variable domains. This is a kind of smart look ahead that could reduce the search space significantly. The art of designing the right model is not only to describe the problem accurately but also to describe the problem using constraints that propagate well.

In our case, the propagation in the current model is the following. There is optional interval variable for every pair of (task, machine). So, during the search, the engine can reason about each such pair separately. For example, noOverlap constraint search for machine M1 reasons about minimum possible start times of all the tasks that could be scheduled on M1, taking into account tasks that search already assigned to M1. It could be that noOverlap constraint detects that there is actually no way to handle task T1 because there is already too many tasks allocated on M1. Then the optional interval variable for (T1, M1) is set to absent. Then alternative constraint reasons about all the ways task T1. It notice that task (T1, M1) is no longer possible and maybe only remaining option is (T1, M2). So it forces T1 to be performed by M2 by setting optional interval variable for (T1, M2) to present. NoOverlap constraint for M2 may react on that. It could be that M2 becomes almost full and has to refuse some long duration tasks, e.g. T2 and T3. Alternative constraint for T2 and T3 may react on that and allocate those tasks elsewhere (if there is only one option left). And so on. This kind of propagation may eliminate a lot of infeasible options and reduce search space dramatically.

Note that this kind of reasoning is possible only with optional interval variables for every pair of (task, machine). If you want to know more then I recommend the following papers:

Laborie, Rogerie: Reasoning with Optional Interval Variables

Laborie, Rogerie, Shaw, Vilim: Reasoning with Conditional Time-Intervals Part II: An Algebraical Model for Resources

Yes, reasoning about every pair (task, machine) requires more memory. But it could be handled. Usually memory is not the issue, more often the issue is the size of the search space. In your case 1000 machines with 20 options gives 20 000 interval variables and that's not an issue (in terms of memory). Don't expect proof of optimality though.

And back to your question, I don't see any other way to model your problem. Before I thought the issue are setup times. But if you want to replace multiple noOverlap constraints with setup times by something else with less interval variables, then I don't see any way to do that.

Petr

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Tobias_

Hello Petr, 

 

thanks for your great and detailed answer. I have now been able to implement it and it works correctly

One question to it the first recomended paper "Laborie, Rogerie: Reasoning with Optional Interval Variables", i don't find with google.
Have you a link for it?

 

But now I have a another problem.

In the part for the solver what is to minimize i have wrote the following:

 

 

mdl2.add(

       mdl2.minimize(

          mdl2.sum(

               mdl2.min(mdl2.end_of(itvs[id,'last machine']) - mdl2.start_of(itvs[id,'first machine']))

               + mdl2.min(earlines_cost * mdl2.max(['order_end_time' - mdl.end_of(itvs[id,'last task']) , 0]))

               + mdl2.min( delay_cost * mdl2.max([mdl2.end_of(itvs[id,'last task']) - 'order_end_time' , 0]))

          )

     )

)

 

The lines descriped in words:

     Line 1: minimize time that need a order to be processed

     Line 2: minimize time that the order is finished before the end date

     Line 3: minimize time that the order is finished after the end date

 

 

Then i run this code with 5 orders (all orders have the end date '30') and the described optimization function. I get folowing result:

order0: (start=38, end=4503599627370474, size=4503599627370436, length=4503599627370436)
order1: (start=0, end=4503599627370464, size=4503599627370464, length=4503599627370464)
order2: (start=5, end=4503599627370454, size=4503599627370449, length=4503599627370449)
order3: (start=4503599627370479, end=4503599627370494, size=15, length=15)
order4: (start=4503599627370469, end=4503599627370484, size=15, length=15)

This makes absolutly no sense. But the result say gap is 0.00% and cost is only 120.

There seme that the compination of line 1 & 2 makes the problem, because then i run 1 &3 and 2 & 3 the solutions are ok.

Then i set the end time of all orders to '60' the combination of all three lines make no problem.

 

Example of a good solution with line 2 & 3:

order0: (start=0, end=30, size=30, length=30)
order1: (start=15, end=45, size=30, length=30)
order2: (start=10, end=40, size=30, length=30)
order3: (start=20, end=35, size=15, length=15)
order4: (start=5, end=20, size=15, length=15)

 

Have anyone a idea that makes here the troubles?

 

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Petr Vilím

Hello,

hard to say what is wrong, the problem could be in earliness_cost or delay_cost and I don't know their definition.

Note that there could be multiple solutions with the same cost. It could be that in some scenarios CP Optimizer first find a "nicer" solution in case 1&3 and 2&3.

I suggest to split the objective function into multiple smaller sub-expressions and add them as KPIs to the solver. Here is documentation:

https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.9.0/ilog.odms.studio.help/CP_Optimizer/Release_notes/topics/relnotes_V1290_changes_kpi.html#changes-kpi

This way, you will see in the log values of the KPI expressions every time a solution is found. And you can find out which sub-expression has different value than expected.

Best regards, Petr

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Tobias_

Hello,

 

thanks again for you answer.

Thats exactly the thing I searched for.

 

But I do not know if I got it right

The KPI is not only for showing the values at and after the solution proces, also for optimize the values defined with the KPI.

 

Because i modifed the house time example a bit to use the KPI function.

 

Variant 1 with the original minimization function:

It deliver the solution showed in picture 1 (solution_variant_1).

The cost of the solution is 5000.

mdl1.add(
    mdl1.minimize(
        400 * mdl1.max([mdl1.end_of(moving) - 100, 0]) 
        + 200 * mdl1.max([25 - mdl1.start_of(masonry), 0]) 
        + 300 * mdl1.max([75 - mdl1.start_of(carpentry), 0]) 
        + 100 * mdl1.max([75 - mdl1.start_of(ceiling), 0]) 
    )
)

In variant 2 I take the inner part of the mdl1.minimize and add it into a add_kpi function.

Now it deliver no optimal solution and it ignores completly the optimization of the earlines and delays costs.

Showed in picture 2 (soluotion_variant_2)

The cost of this solution is 21000.

 

mdl1.add_kpi(
    mdl1.min(  
        400 * mdl1.max([mdl1.end_of(moving) - 100, 0]) 
        + 200 * mdl1.max([25 - mdl1.start_of(masonry), 0]) 
        + 300 * mdl1.max([75 - mdl1.start_of(carpentry), 0]) 
        + 100 * mdl1.max([75 - mdl1.start_of(ceiling), 0]) 
    ), 'cost'
)

mdl1.add(mdl1.minimize(1))

 

I have also attached the python file.

Have I there a big mistake in my thinkings?
Or does the KPI function no provides these features i want

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Petr Vilím

Hello,

KPI expressions are not not minimized or maximized automatically. They are only evaluated and the value is printed whenever a solution is found. If you want minimize or maximize a value of a KPI expression then it is necessary to put it inside minimize/maximize.

In particular "minimize(1)" has no effect because 1 is a constant. Therefore every solution has the same objective value and the search stops after the first solution is found (as this solution is optimal).

I was thinking about something like this:

IloIntExpr endMoving = mdl1.max([mdl1.end_of(moving) - 100, 0]);
IloIntExpr startMasonry = mdl1.max([25 - mdl1.start_of(masonry), 0]);
IloIntExpr startCarpentry = mdl1.max([75 - mdl1.start_of(carpentry), 0]);
IloIntExpr startCeiling = mdl1.max([75 - mdl1.start_of(ceiling), 0]);
        
mdl1.add(mdl.minimize(400*endMoving + 200*startMasonry + 300*startCarpetry + 100*startCeiling));
...
cp.add_kpi(endMoving, "endMoving");
cp.add_kpi(startMasonry, "startMasonry");
cp.add_kpi(startCarpentry, "startCarpentry");
cp.add_kpi(startCeiling, "startCeiling");

 

Best regards, Petr

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Tobias_

Hello, 

this clears it a lot.

 

 Have I any possibility to say the minimize function which value is the most important for  me?

For example I building houses with different tasks, I have the three following values in the minimize part

- reduce 'starting to early' (1)

- reduce 'ending to late' (2)

- reduce 'lenght all parts need of the house' (3)

The minimization of (1) & (2) are very important, because they cost the entrepreneur money and maybe the costumers are not happy then the house is finished late.

The minimazation of (3) is nice, maybe reduce driving cost, but not so imporant as the happyness of the costumer.

 

Does the optimizer have any function with which I can tell the solver what value the weight value is?
So that then the solver tries to minimize this the most?

 

----

 

Maybe someone stumple over this Thread.

To the question i have asked on Monday at 4:19 PM , I have found the solution, that works perfectly for me.

 

Instead of using this line:

          mdl2.min(mdl2.end_of(itvs[id,'last machine']) - mdl2.start_of(itvs[id,'first machine']))

I used the function length_of:

          mdl2.min(mdl2.length_of(order[id])

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: Petr Vilím

There are basically two ways to combine multiple objectives. You can assign them different weights and combine them together like this:

  minimize(100*objective1 + 10*objective2 + objective3);

Or you can use staticLex to combine objectives:

  minimize(staticLex(objective1, objective2, objective3));

Basically with staticLex solutions are compared lexicographically: if objective1(solution1) < objective1(solution2) then solution1 is better regardless objective2 and objective3. In contract with weights solution1 could still be worse if objective2 and/or objective3 are much worse than in solution2.

Here is documentation for staticLex:

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.9.0/ilog.odms.ide.help/OPL_Studio/opllang_quickref/topics/tlr_oplf_staticLex.html

Note that with staticLex CP Optimizer concentrates primarily on the first objective. So in your case it could be best to combine the two approaches like this:

  minimize(staticLex(10*objective1 + objective2), objective3);

Regards, Petr

#DecisionOptimization
#OPLusingCPOptimizer