Skip to main content


Weitere Artikel dieser Ausgabe durch Wischen aufrufen

12.08.2020 | Ausgabe 4/2020 Open Access

Journal of Combinatorial Optimization 4/2020

A characterization of optimal multiprocessor schedules and new dominance rules

Journal of Combinatorial Optimization > Ausgabe 4/2020
Rico Walter, Alexander Lawrinenko
Wichtige Hinweise

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.


The paper on hand approaches the classical makespan minimization problem on identical parallel machines from a rather theoretical point of view. Using an approach similar to the idea behind inverse optimization, we identify a general structural pattern of optimal multiprocessor schedules. We also show how to derive new dominance rules from the characteristics of optimal solutions. Results of our computational study attest to the efficacy of the new rules. They are particularly useful in limiting the search space when each machine processes only a few jobs on average.
Über diesen Artikel

Weitere Artikel der Ausgabe 4/2020

Journal of Combinatorial Optimization 4/2020 Zur Ausgabe

Premium Partner