We study methods for the exact solution of the unrelated parallel machine problem with makespan minimization, generally denoted as . Our original application arises from the automotive assembly process where tasks needs to be distributed among several robots. This involves the solutions of several 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:
Revised:
Accepted:
Published online:
@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] Intersection-free load balancing for industrial robots, Masters thesis, Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg (2016)
[2] R||Cmax Solver, Fraunhofer-Chalmers Centre GitHub repository, 2021 (https://github.com/Fraunhofer-Chalmers-Centre/RCmax/releases/v1.0)
[3] 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] Branching rules revisited, Oper. Res. Lett., Volume 33 (2005) no. 1, pp. 42-54 | DOI | MR | Zbl
[5] A machine learning-based approximation of strong branching, INFORMS J. Comput., Volume 29 (2017) no. 1, pp. 185-195 | DOI | MR | Zbl
[6] Subgradient optimization methods, Nonlinear Programming: Theory and Algorithms, John Wiley & Sons, 2006 | DOI
[7] A new modified deflected subgradient method, J. King Saud Univ. Sci., Volume 30 (2018) no. 4, pp. 561-567 | DOI
[8] Heuristic algorithms in global MINLP solvers, Ph. D. Thesis, Technische Universität Berlin (2014), 366 pages
[9] 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] On improving relaxation methods by modified gradient techniques, Nondifferentiable Optimization, Springer, 1975, pp. 26-34 | DOI | Zbl
[11] Integer Programming, Springer, 2014 | Zbl
[12] 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] Local branching, Math. Program., Volume 98 (2003) no. 1, pp. 23-47 | DOI | MR | Zbl
[14] An additive bounding procedure for combinatorial optimization problems, Oper. Res., Volume 37 (1989) no. 2, pp. 319-328 | DOI | MR | Zbl
[15] 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] 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] 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] 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
[20] 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 Optimizer Reference Manual, 2020 (http://www.gurobi.com)
[22] Validation of subgradient optimization, Math. Program., Volume 6 (1974) no. 1, pp. 62-88 | DOI | MR | Zbl
[23] Exact and approximate algorithms for scheduling nonidentical processors, J. Assoc. Comput. Mach., Volume 23 (1976) no. 2, pp. 317-327 | DOI | MR | Zbl
[24] 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] Improved Approximation Schemes for Scheduling Unrelated Parallel Machines, Math. Oper. Res., Volume 26 (2001) no. 2, pp. 324-338 | DOI | MR | Zbl
[26] Ergodic, primal convergence in dual subgradient schemes for convex programming, Math. Program., Volume 86 (1999) no. 2, pp. 283-312 | DOI | MR | Zbl
[27] Approximation algorithms for scheduling unrelated parallel machines, Math. Program., Volume 46 (1990) no. 1–3, pp. 259-271 | DOI | MR | Zbl
[28] Dynamic Programming and Strong Bounds for the 0–1 Knapsack Problem, Manage. Sci., Volume 45 (1999) no. 3, pp. 414-424 | DOI | Zbl
[29] 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] Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990 (www.or.deis.unibo.it/kp/KnapsackProblems.pdf) | Zbl
[31] Parallel machine scheduling problems: A survey, Asia-Pac. J. Oper. Res., Volume 18 (2001) no. 2, pp. 193-242 | MR | Zbl
[32] 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] 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] A minimal algorithm for the 0-1 knapsack problem, Oper. Res., Volume 45 (1997) no. 5, pp. 758-767 | DOI | MR | Zbl
[35] Minimization of unsmooth functionals, U.S.S.R. Comput. Math. Math. Phys., Volume 9 (1969) no. 3, pp. 14-29 | DOI | Zbl
[36] 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] 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] 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] Duality-based algorithms for scheduling unrelated parallel machines, ORSA J. Comput., Volume 5 (1993) no. 2, pp. 192-205 | DOI | MR | Zbl
[40] Approximation Algorithms, Springer, 2003
[41] 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] Scheduling Unrelated Parallel Machines—Algorithms, Complexity, and Performance, VDM Verlag, 2007
Cited by Sources: