Skip to main content


Swipe to navigate through the articles of this issue

12-08-2020 | Issue 4/2020 Open Access

Journal of Combinatorial Optimization 4/2020

A characterization of optimal multiprocessor schedules and new dominance rules

Journal of Combinatorial Optimization > Issue 4/2020
Rico Walter, Alexander Lawrinenko
Important notes

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.
About this article

Other articles of this Issue 4/2020

Journal of Combinatorial Optimization 4/2020 Go to the issue

Premium Partner

    Image Credits