An Application of the Local Branching to the Identical Parallel Machines Scheduling Problem
| Autor: | Scarpin Cassius Tadeu, Talita Mariana Pinho Schimidt, Gustavo Valentim Loch, Nathália Cristina Ortiz da Silva |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
0209 industrial biotechnology
Machine scheduling 021103 operations research General Computer Science Job shop scheduling Computer science 0211 other engineering and technologies 02 engineering and technology Variation (game tree) Upper and lower bounds Branching (linguistics) Task (computing) 020901 industrial engineering & automation Convergence (routing) Electrical and Electronic Engineering Integer programming Algorithm |
| Zdroj: | IEEE Latin America Transactions. 17:1047-1054 |
| ISSN: | 1548-0992 |
| DOI: | 10.1109/tla.2019.8896828 |
| Popis: | In this paper, we consider the Identical Parallel Machine Scheduling Problem, with sequence-dependent setup time and the aim of minimizing makespan. We present two solution approaches: mathematical formulation of Mixed Integer Linear Programming (MILP) and the exact Local Branching method. The aim of this paper is the application and comparison of performance between the two approaches and the analysis of the convergence of each method. This analysis was based on the variation of setup times (between 10% and 50% of the processing time of the task in a machine, depending on the test performed), number of tasks (20, 30, 40, 50 and 100) and the number of machines available (3 and 5 machines). Both approaches were tested with a computational time of one hour in each test. As a consequence, we compared the optimality GAP for all instances by calculating the Lower Bound of each generated problem. The results obtained for instances with 30 tasks or more indicate that the Local Branching method presented better results when having a more significant number of machines. This gain increases as there is an increase in the number of tasks and machines. For smaller problems and with fewer parallel machines, the MILP approach presents lower GAP values. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|