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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2777-5860 |