Exact makespan minimization of unrelated parallel machines

Åblad, Edvin; Strömberg, Ann-Brith; Spensieri, Domenico

Open Journal of Mathematical Optimization, Tome 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\left|\right|C_{\text{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\left|\right|C_{\text{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:

• RCmax-instances.zip

• results.zip

Mots clés : unrelated parallel machine problem, makespan, variable fixing, binary knapsack, Lagrangian relaxation

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

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

[3] Åblad, Edvin; Spensieri, Domenico; Bohlin, Robert; Carlson, Johan S. 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] Achterberg, Tobias; Koch, Thorsten; Martin, Alexander Branching rules revisited, Oper. Res. Lett., Volume 33 (2005) no. 1, pp. 42-54 | DOI | MR | Zbl

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

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

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

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

[9] Borba, Leonardo; Ritt, Marcus 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] Camerini, Paolo M.; Fratta, Luigi; Maffioli, Francesco On improving relaxation methods by modified gradient techniques, Nondifferentiable Optimization, Springer, 1975, pp. 26-34 | DOI | Zbl

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

[12] Fanjul-Peyro, Luis; Ruiz, Rubén 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] Fischetti, Matteo; Lodi, Andrea Local branching, Math. Program., Volume 98 (2003) no. 1, pp. 23-47 | DOI | MR | Zbl

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

[15] Frangioni, Antonio; Necciari, Emiliano; Scutellà, Maria Grazia 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] Gairing, Martin; Monien, Burkhard; Woclaw, Andreas A faster combinatorial approximation algorithm for scheduling unrelated parallel machines, International Colloquium on Automata, Languages, and Programming (Caires, Luís; Italiano, Giuseppe F.; Monteiro, Luís; Palamidessi, Catuscia; Yung, Moti, eds.) (Lecture Notes in Computer Science), Volume 3580, Springer (2005), pp. 828-839 | DOI | MR

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

[18] Ghirardi, Marco; Potts, Chris N. 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] Glass, Celia A.; Potts, Chris N.; Shade, P. Unrelated parallel machine scheduling using local search, Math. Comput. Modelling, Volume 20 (1994) no. 2, pp. 41-52 | DOI | Zbl

[20] Graham, Ronald L.; Lawler, Eugene L.; Lenstra, Jan Karel; Kan, A. H. G. Rinnooy 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] Held, Michael; Wolfe, Philip; Crowder, Harlan P. Validation of subgradient optimization, Math. Program., Volume 6 (1974) no. 1, pp. 62-88 | DOI | MR | Zbl

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

[24] Irnich, Stefan; Desaulniers, Guy; Desrosiers, Jacques; Hadjar, Ahmed 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] Jansen, Klaus; Porkolab, Lorant Improved Approximation Schemes for Scheduling Unrelated Parallel Machines, Math. Oper. Res., Volume 26 (2001) no. 2, pp. 324-338 | DOI | MR | Zbl

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

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

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

[29] Martello, Silvano; Soumis, François; Toth, Paolo 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] Martello, Silvano; Toth, Paolo Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990 (www.or.deis.unibo.it/kp/KnapsackProblems.pdf) | Zbl

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

[32] Mokotoff, Ethel; Chrétienne, Philippe 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] Önnheim, Magnus; Gustavsson, Emil; Strömberg, Ann-Brith; Patriksson, Michael; Larsson, Torbjörn 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] Pisinger, David A minimal algorithm for the 0-1 knapsack problem, Oper. Res., Volume 45 (1997) no. 5, pp. 758-767 | DOI | MR | Zbl

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

[36] Posta, Marius; Ferland, Jacques A; Michelon, Philippe 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] Sandi, Claudio Solution of the machine loading problem with binary variables, Combinatorial Programming: Methods and Applications (Roy, B., ed.) (NATO Advanced Study Institutes Series), Volume 19, Springer, 1975, pp. 371-378 | MR

[38] Sherali, Hanif D.; Ulular, Osman 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] van de Velde, Steef L. Duality-based algorithms for scheduling unrelated parallel machines, ORSA J. Comput., Volume 5 (1993) no. 2, pp. 192-205 | DOI | MR | Zbl

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

[41] Vilà, Mariona; Pereira, Jordi 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] Wotzlaw, Andreas Scheduling Unrelated Parallel Machines—Algorithms, Complexity, and Performance, VDM Verlag, 2007