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: https://doi.org/10.5802/ojmo.4
Keywords: unrelated parallel machine problem, makespan, variable fixing, binary knapsack, Lagrangian relaxation
@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},
     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/}
}
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 (2016) (Masters thesis)

[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 | Article

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

[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 | Article | MR 3612402 | Zbl 1364.90224

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

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

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

[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 | Article | MR 3161251 | Zbl 1348.90220

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

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

[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 | Article | MR 2659420 | Zbl 1205.90121

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

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

[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 | Article | MR 2071378 | Zbl 1133.90337

[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 | Article | MR 2184682

[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 | Article | Zbl 06605753

[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 | Article | Zbl 1066.90029

[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 | Article | Zbl 0810.90066

[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 | Article | MR 558574 | Zbl 0411.90044

[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 | Article | MR 341863 | Zbl 0284.90057

[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 | Article | MR 395801 | Zbl 0329.68041

[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 | Article | MR 2677216 | Zbl 1243.90064

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

[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 | Article | MR 1725232 | Zbl 0946.90059

[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 | Article | MR 1054138 | Zbl 0715.90063

[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 | Article | Zbl 1231.90338

[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 | Article | MR 1451960 | Zbl 0882.68016

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

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

[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 | Article | MR 1916033 | Zbl 1081.90558

[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 | Article | MR 3632974 | Zbl 1383.90025

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

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

[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 | Article | MR 2950499 | Zbl 1259.90062

[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 439136

[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 | Article | MR 998403 | Zbl 0675.90069

[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 | Article | MR 1217919 | Zbl 0777.90019

[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 | Article | Zbl 1307.90090

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