.png){kind=icon}
Return
A new approximation algorithm for unrelated parallel machine scheduling with release dates
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-019-03346-4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Unrelated parallel machine scheduling
Release dates
Semi-definite programming
Approximation algorithm
Branch and bound
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.5
Papers:
8.1K
Citations:
2.1W
Organization
Cited Papers
.png){kind=icon}
Apocalyptic belief and prophecy: constructing political legitimacy during the Yuan-Ming transition
PREAI
ShareSaveAn iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem
PREAI
ShareSaveShareSave
ShareSaveShareSave
View more