Exact makespan minimization of unrelated parallel machines
We study methods for the exact solution of the unrelated parallel machine problem with makespan minimization, generally denoted as $R||C_\text{max}$. Our original application arises from the automotive assembly process where tasks needs to be distributed among several robots. This involves the solut...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2021-05-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.4/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825204985384665088 |
|---|---|
| author | Åblad, Edvin Strömberg, Ann-Brith Spensieri, Domenico |
| author_facet | Åblad, Edvin Strömberg, Ann-Brith Spensieri, Domenico |
| author_sort | Åblad, Edvin |
| collection | DOAJ |
| description | We study methods for the exact solution of the unrelated parallel machine problem with makespan minimization, generally denoted as $R||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||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. |
| format | Article |
| id | doaj-art-78764b16fe4844cca99a98b61b58474b |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2021-05-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-78764b16fe4844cca99a98b61b58474b2025-02-07T14:02:30ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602021-05-01211510.5802/ojmo.410.5802/ojmo.4Exact makespan minimization of unrelated parallel machinesÅblad, Edvin0Strömberg, Ann-Brith1Spensieri, Domenico2Fraunhofer-Chalmers Research Centre and Chalmers University of Technology, Gothenburg, SwedenChalmers University of Technology and University of Gothenburg, Gothenburg, SwedenFraunhofer-Chalmers Research Centre and Chalmers University of Technology, Gothenburg, SwedenWe study methods for the exact solution of the unrelated parallel machine problem with makespan minimization, generally denoted as $R||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||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.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.4/unrelated parallel machine problemmakespanvariable fixingbinary knapsackLagrangian relaxation |
| spellingShingle | Åblad, Edvin Strömberg, Ann-Brith Spensieri, Domenico Exact makespan minimization of unrelated parallel machines Open Journal of Mathematical Optimization unrelated parallel machine problem makespan variable fixing binary knapsack Lagrangian relaxation |
| title | Exact makespan minimization of unrelated parallel machines |
| title_full | Exact makespan minimization of unrelated parallel machines |
| title_fullStr | Exact makespan minimization of unrelated parallel machines |
| title_full_unstemmed | Exact makespan minimization of unrelated parallel machines |
| title_short | Exact makespan minimization of unrelated parallel machines |
| title_sort | exact makespan minimization of unrelated parallel machines |
| topic | unrelated parallel machine problem makespan variable fixing binary knapsack Lagrangian relaxation |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.4/ |
| work_keys_str_mv | AT abladedvin exactmakespanminimizationofunrelatedparallelmachines AT strombergannbrith exactmakespanminimizationofunrelatedparallelmachines AT spensieridomenico exactmakespanminimizationofunrelatedparallelmachines |