An Arc-Flow Model for the Makespan Minimization Problem on Identical Parallel Machines
| Autor: | Nizar Souayah, Mehdi Mrad |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
Arc-flow model 021103 operations research General Computer Science Job shop scheduling Linear programming Computer science Bin packing problem parallel machines Minimization problem 0211 other engineering and technologies General Engineering Approximation algorithm Duality (optimization) 02 engineering and technology Upper and lower bounds 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing General Materials Science scheduling lcsh:Electrical engineering. Electronics. Nuclear engineering integer programming lcsh:TK1-9971 |
| Zdroj: | IEEE Access, Vol 6, Pp 5300-5307 (2018) |
| ISSN: | 2169-3536 |
| Popis: | In this paper, we consider the basic makespan minimization problem on identical parallel machines. The aim of this study is to solve, to optimality the hard instances of the literature. We present an integer linear program based on an innovative arc-flow model inspired from the duality between the bin packing problem and the parallel-machine scheduling problem. The proposed mathematical model is tested on a large set of hard instances. The results of computational experiments attest the efficiency of the new approach and prove that it outperforms the existing ones. In addition to its efficiency, the proposed method is simple and easy to use. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|