Exact makespan minimization of unrelated parallel machines
Open Journal of Mathematical Optimization, Volume 2 (2021), article no. 2, 15 p.

We study methods for the exact solution of the unrelated parallel machine problem with makespan minimization, generally denoted as R||C max . Our original application arises from the automotive assembly process where tasks needs to be distributed among several robots. This involves the solutions of several R||C max instances, which proved hard for a MILP solver since the makespan objective induces weak LP relaxation bounds. To improve these bounds and to enable the solution of larger instances, we propose a branch–and–bound method based on a Lagrangian relaxation of the assignment constraints. For this relaxation we derive a criterion for variable fixing and prove the zero duality gap property for the case of two parallel machines. Our computational studies indicate that the proposed algorithm is competitive with state-of-the-art methods on different types of instances. Moreover, the impact of each proposed feature is analysed.

Supplementary Materials:
Supplementary materials for this article are supplied as separate files:

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.4
Keywords: unrelated parallel machine problem, makespan, variable fixing, binary knapsack, Lagrangian relaxation
Edvin Åblad 1; Ann-Brith Strömberg 2; Domenico Spensieri 1

1 Fraunhofer-Chalmers Research Centre and Chalmers University of Technology, Gothenburg, Sweden
2 Chalmers University of Technology and University of Gothenburg, Gothenburg, Sweden
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{OJMO_2021__2__A2_0,
     author = {Edvin \r{A}blad and Ann-Brith Str\"omberg and Domenico Spensieri},
     title = {Exact makespan minimization of unrelated parallel machines},
     journal = {Open Journal of Mathematical Optimization},
     eid = {2},
     pages = {1--15},
     publisher = {Universit\'e de Montpellier},
     volume = {2},
     year = {2021},
     doi = {10.5802/ojmo.4},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.4/}
}
TY  - JOUR
AU  - Edvin Åblad
AU  - Ann-Brith Strömberg
AU  - Domenico Spensieri
TI  - Exact makespan minimization of unrelated parallel machines
JO  - Open Journal of Mathematical Optimization
PY  - 2021
SP  - 1
EP  - 15
VL  - 2
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.4/
DO  - 10.5802/ojmo.4
LA  - en
ID  - OJMO_2021__2__A2_0
ER  - 
%0 Journal Article
%A Edvin Åblad
%A Ann-Brith Strömberg
%A Domenico Spensieri
%T Exact makespan minimization of unrelated parallel machines
%J Open Journal of Mathematical Optimization
%D 2021
%P 1-15
%V 2
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.4/
%R 10.5802/ojmo.4
%G en
%F OJMO_2021__2__A2_0
Edvin Åblad; Ann-Brith Strömberg; Domenico Spensieri. Exact makespan minimization of unrelated parallel machines. Open Journal of Mathematical Optimization, Volume 2 (2021), article  no. 2, 15 p. doi : 10.5802/ojmo.4. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.4/

[1] Edvin Åblad Intersection-free load balancing for industrial robots, Masters thesis, Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg (2016)

[2] Edvin Åblad R||Cmax Solver, Fraunhofer-Chalmers Centre GitHub repository, 2021 (https://github.com/Fraunhofer-Chalmers-Centre/RCmax/releases/v1.0)

[3] Edvin Åblad; Domenico Spensieri; Robert Bohlin; Johan S. Carlson Intersection-free geometrical partitioning of multirobot stations for cycle time optimization, IEEE Trans. Autom. Sci. Eng., Volume 15 (2018) no. 2, pp. 842-851 | DOI

[4] Tobias Achterberg; Thorsten Koch; Alexander Martin Branching rules revisited, Oper. Res. Lett., Volume 33 (2005) no. 1, pp. 42-54 | DOI | MR | Zbl

[5] Alejandro Marcos Alvarez; Quentin Louveaux; Louis Wehenkel A machine learning-based approximation of strong branching, INFORMS J. Comput., Volume 29 (2017) no. 1, pp. 185-195 | DOI | MR | Zbl

[6] Mokhtar S. Bazaraa; Hanif D. Sherali; C. M. Shetty Subgradient optimization methods, Nonlinear Programming: Theory and Algorithms, John Wiley & Sons, 2006 | DOI

[7] Rachid Belgacem; Abdessamad Amir A new modified deflected subgradient method, J. King Saud Univ. Sci., Volume 30 (2018) no. 4, pp. 561-567 | DOI

[8] Timo Berthold Heuristic algorithms in global MINLP solvers, Ph. D. Thesis, Technische Universität Berlin (2014), 366 pages

[9] Leonardo Borba; Marcus Ritt A heuristic and a branch-and-bound algorithm for the assembly line worker assignment and balancing problem, Comput. Oper. Res., Volume 45 (2014), pp. 87-96 | DOI | MR | Zbl

[10] Paolo M. Camerini; Luigi Fratta; Francesco Maffioli On improving relaxation methods by modified gradient techniques, Nondifferentiable Optimization, Springer, 1975, pp. 26-34 | DOI | Zbl

[11] Michele Conforti; Gerard Cornuejols; Giacomo Zambelli Integer Programming, Springer, 2014 | Zbl

[12] Luis Fanjul-Peyro; Rubén Ruiz Iterated greedy local search methods for unrelated parallel machine scheduling, Eur. J. Oper. Res., Volume 207 (2010) no. 1, pp. 55-69 | DOI | MR | Zbl

[13] Matteo Fischetti; Andrea Lodi Local branching, Math. Program., Volume 98 (2003) no. 1, pp. 23-47 | DOI | MR | Zbl

[14] Matteo Fischetti; Paolo Toth An additive bounding procedure for combinatorial optimization problems, Oper. Res., Volume 37 (1989) no. 2, pp. 319-328 | DOI | MR | Zbl

[15] Antonio Frangioni; Emiliano Necciari; Maria Grazia Scutellà A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems, J. Comb. Optim., Volume 8 (2004) no. 2, pp. 195-220 | DOI | MR | Zbl

[16] Martin Gairing; Burkhard Monien; Andreas Woclaw A faster combinatorial approximation algorithm for scheduling unrelated parallel machines, International Colloquium on Automata, Languages, and Programming (Lecture Notes in Computer Science), Volume 3580 (2005), pp. 828-839 | DOI | MR

[17] Gerald Gamrath; Anna Melchiori; Timo Berthold; Ambros M Gleixner; Domenico Salvagnin Branching on multi-aggregated variables, Integration of AI and OR Techniques in Constraint Programming (Lecture Notes in Computer Science), Volume 9075 (2015), pp. 141-156 | DOI | Zbl

[18] Marco Ghirardi; Chris N. Potts Makespan minimization for scheduling unrelated parallel machines: A recovering beam search approach, Eur. J. Oper. Res., Volume 165 (2005) no. 2, pp. 457-467 | DOI | Zbl

[19] Celia A. Glass; Chris N. Potts; P. Shade Unrelated parallel machine scheduling using local search, Math. Comput. Modelling, Volume 20 (1994) no. 2, pp. 41-52 | DOI | Zbl

[20] Ronald L. Graham; Eugene L. Lawler; Jan Karel Lenstra; A. H. G. Rinnooy Kan Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, Volume 5, Elsevier, 1979, pp. 287-326 | DOI | MR | Zbl

[21] Gurobi Optimization, LLC Gurobi Optimizer Reference Manual, 2020 (http://www.gurobi.com)

[22] Michael Held; Philip Wolfe; Harlan P. Crowder Validation of subgradient optimization, Math. Program., Volume 6 (1974) no. 1, pp. 62-88 | DOI | MR | Zbl

[23] Ellis Horowitz; Sartaj Sahni Exact and approximate algorithms for scheduling nonidentical processors, J. Assoc. Comput. Mach., Volume 23 (1976) no. 2, pp. 317-327 | DOI | MR | Zbl

[24] Stefan Irnich; Guy Desaulniers; Jacques Desrosiers; Ahmed Hadjar Path-reduced costs for eliminating arcs in routing and scheduling, INFORMS J. Comput., Volume 22 (2010) no. 2, pp. 297-313 | DOI | MR | Zbl

[25] Klaus Jansen; Lorant Porkolab Improved Approximation Schemes for Scheduling Unrelated Parallel Machines, Math. Oper. Res., Volume 26 (2001) no. 2, pp. 324-338 | DOI | MR | Zbl

[26] Torbjörn Larsson; Michael Patriksson; Ann-Brith Strömberg Ergodic, primal convergence in dual subgradient schemes for convex programming, Math. Program., Volume 86 (1999) no. 2, pp. 283-312 | DOI | MR | Zbl

[27] Jan Karel Lenstra; David B. Shmoys; Éva Tardos Approximation algorithms for scheduling unrelated parallel machines, Math. Program., Volume 46 (1990) no. 1–3, pp. 259-271 | DOI | MR | Zbl

[28] Silvano Martello; David Pisinger; Paolo Toth Dynamic Programming and Strong Bounds for the 0–1 Knapsack Problem, Manage. Sci., Volume 45 (1999) no. 3, pp. 414-424 | DOI | Zbl

[29] Silvano Martello; François Soumis; Paolo Toth Exact and approximation algorithms for makespan minimization on unrelated parallel machines, Discrete Appl. Math., Volume 75 (1997) no. 2, pp. 169-188 | DOI | MR | Zbl

[30] Silvano Martello; Paolo Toth Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990 (www.or.deis.unibo.it/kp/KnapsackProblems.pdf) | Zbl

[31] Ethel Mokotoff Parallel machine scheduling problems: A survey, Asia-Pac. J. Oper. Res., Volume 18 (2001) no. 2, pp. 193-242 | MR | Zbl

[32] Ethel Mokotoff; Philippe Chrétienne A cutting plane algorithm for the unrelated parallel machine scheduling problem, Eur. J. Oper. Res., Volume 141 (2002) no. 3, pp. 515-525 | DOI | MR | Zbl

[33] Magnus Önnheim; Emil Gustavsson; Ann-Brith Strömberg; Michael Patriksson; Torbjörn Larsson Ergodic, primal convergence in dual subgradient schemes for convex programming, II: the case of inconsistent primal problems, Math. Program., Volume 163 (2017) no. 1–2, pp. 57-84 | DOI | MR | Zbl

[34] David Pisinger A minimal algorithm for the 0-1 knapsack problem, Oper. Res., Volume 45 (1997) no. 5, pp. 758-767 | DOI | MR | Zbl

[35] Boris T. Polyak Minimization of unsmooth functionals, U.S.S.R. Comput. Math. Math. Phys., Volume 9 (1969) no. 3, pp. 14-29 | DOI | Zbl

[36] Marius Posta; Jacques A Ferland; Philippe Michelon An exact method with variable fixing for solving the generalized assignment problem, Comput. Optim. Appl., Volume 52 (2012) no. 3, pp. 629-644 | DOI | MR | Zbl

[37] Claudio Sandi Solution of the machine loading problem with binary variables, Combinatorial Programming: Methods and Applications (B. Roy, ed.) (NATO Advanced Study Institutes Series), Volume 19, Springer, 1975, pp. 371-378 | MR

[38] Hanif D. Sherali; Osman Ulular A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems, Appl. Math. Optim., Volume 20 (1989) no. 1, pp. 193-221 | DOI | MR | Zbl

[39] Steef L. van de Velde Duality-based algorithms for scheduling unrelated parallel machines, ORSA J. Comput., Volume 5 (1993) no. 2, pp. 192-205 | DOI | MR | Zbl

[40] Vijay V. Vazirani Approximation Algorithms, Springer, 2003

[41] Mariona Vilà; Jordi Pereira A branch-and-bound algorithm for assembly line worker assignment and balancing problems, Comput. Oper. Res., Volume 44 (2014), pp. 105-114 | DOI | Zbl

[42] Andreas Wotzlaw Scheduling Unrelated Parallel Machines—Algorithms, Complexity, and Performance, VDM Verlag, 2007

Cited by Sources: