Multi-objective optimization: Scale the objectives - JobShop problem

[s.k...@mbo-osswald.de]

Hey,

I am trying to solve a multi-objective optimization JobShop (with transition costs, due dates, alternatives and a machine calendar that provides times where the machines are shut off) problem with 6 different objectives, such as:

1) makespan

2) sum of all start times

(to avoid unnecessary gaps, because not all the time the jobs can be scheduled back to back, because some of them have an earliest start date that is way in the future)

3) ranks of all already posted jobs 

(that have to be scheduled with higher priority)

4) sum of all transition costs

(to make it more efficient)

5) sum of the time a job exceeded its deadline/due date

(to keep the customer happy)

6) negative sum of the time a job finishes early

(to favor jobs that were placed earlier than others - if possible, depending on things like due date, earliest start date, etc.)

All this objectives are of different magnitude.

For example:

1) 6234, 

4) 1390, 

2) 134130, 

3) 5310, 

5) 132427, 

6) -95635

(the time unit is hour)

Right now I try to scale (with the help of the old schedule of the input data I am trying to optimize) and prioritize them by hand (by adding coefficients in the objective function for each factor) , but because with every new set of job data the numbers can change, and also with every found solution the magnitude changes a little, this is not really an optimal approach I think.

I also don't know how to do one objective at a time, because when I solve with the first objective and get a good feasible or even optimal solution with an objective x, then I can't just do another run with the second objective and feed it with the solution of the first run. Because I also had to add something like

model.Add(objective < x) to the second run, but the objective in the second run maybe has a totally different magnitude than the objective solution from the first run and the constraint may be rubbish.

Or not?

Also I am afraid that it takes a lot more time to solve every objective by itself.

I also would like to try to "group" for example the lateness factor 5).

So not optimizing over the sum of hours, but if a job is exceeding its due date for 0-7 days it gets 1 "point", if its exceeding its due date for 7-30 days it gets 5 "points", if its between 30-60 its 10 "points" and if its late for more than 60 days it will get 20 "points".

Something like that.

But I don't know how to do that, without attempting to get values of variables before they are being calculated by the solver.

I can't do something like:

lateness= model.NewIntVar(...)

if lateness > 30:

 do this

or 

model.Add(lateness_points = 1).OnlyEnforceIf(lateness < 30)

What can I do about this?

[Laurent Perron]

1) if the first phase is model.minimize(XXX) and you get a value xxx for the objective. In the second phase just add model.Add(XXX <= xxx) then minimize(YYY). And so on.

2) just look at: https://github.com/google/or-tools/blob/stable/ortools/sat/doc/channeling.md

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/28aa929f-613b-47fd-b625-16ae15d81dbbn%40googlegroups.com.

[s.k...@mbo-osswald.de]

Oh right, had a little thinking blunder there...

Thanks a lot!

[Priidik Vilumaa]

I would be interested to hear how successful this is - I am currently facing the same problem on a different optimization problem (multiple objective, different magnitudes and very hard to precompute "good" coefficients).

Best,

Priidik

[s.k...@mbo-osswald.de]

Hey,

so I really like this approach. I have a lot less problems like 'one objective overpowering another one'.

I still have to (resp. can) control the priority of the different objectives a little bit by setting the order of which objective should be minimized first, which second and so on, and by setting a time limit for each run with a different target objective.

But for me it takes A LOT longer, because after every run the solver takes up to 45 minutes to terminate/end.

Before I only had to calculate this in one time, now I have to add it in 6 times to my expected total run time.

[Priidik Vilumaa]

Interesting, thanks for letting me know. Definitely considering implementing this now.

Best,

Priidik