A new approximation algorithm for unrelated parallel machine scheduling with release dates
| Autor: | Mingzhong Wan, Zhi Pei, Ziteng Wang |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Semidefinite programming
Mathematical optimization 021103 operations research Branch and bound Job shop scheduling Computer science business.industry Numerical analysis 0211 other engineering and technologies General Decision Sciences Approximation algorithm 02 engineering and technology Binary constraint Management Science and Operations Research Upper and lower bounds Scheduling (computing) Local search (optimization) business Time complexity |
| Zdroj: | Annals of Operations Research. 285:397-425 |
| ISSN: | 1572-9338 0254-5330 |
| Popis: | In the current study, an unrelated parallel machine scheduling problem with release dates is considered, which is to obtain a job assignment with minimal sum of weighted completion times. Although this problem is NP-hard in the strong sense, which renders the optimality seeking a formidable task within polynomial time, a 4-approximation algorithm based on the constant worst-case bound is devised and proved in comparison with the existing 16/3-approximation (Hall et al. in Math Oper Res 22(3):513–544, 1997). In the newly proposed algorithm, the original scheduling problem is divided into several sub-problems based on release dates. For each sub-problem, a convex quadratic integer programming model is constructed in accordance with the specific problem structure. Then a semi-definite programming approach is implemented to produce a lower bound via the semi-definite relaxation of each sub-problem. Furthermore, by considering the binary constraint, a branch and bound based method and a local search strategy are applied separately to locate the optimal solution of each sub-problem. Then the solution of the original scheduling problem is derived by integrating the outcomes of the sub-problems via the proposed approximation algorithm. In the numerical analysis, it is discovered that the proposed methods could always obtain a scheduling result within $$1\%$$ of the optimal solution. And an asymptotic trend could be observed where the quality of solutions improves even further as the scale of the scheduling problem increases. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink