A new approximation algorithm for unrelated parallel machine scheduling problem with release dates

In this research, we consider the unrelated parallel machine scheduling problem with release dates. The goal of this scheduling problem is to find an optimal job assignment with minimal sum of weighted completion times. As it is demonstrated in the present paper, this problem is NP-hard in the strong sense. Albeit the computational complexity, which renders the optimality seeking a formidable task within polynomial time, a 4-approximation algorithm is devised and proved in comparison with the 16/3-approximation(Hall et al. 1997). In the newly proposed algorithm, the original scheduling problem is divided into several sub-problems based on the release dates. For each sub-problem, a convex quadratic integer programming (CQIP) 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 0-1 constraint, a branch and bound (B&B) based method and a local search (LS) strategy are applied separately to locate the integer solution of each sub-problem. Consequently, the solution of the original scheduling problem can be constituted by integrating the outcomes of the sub-problems with the help of the proposed approximation algorithm. In the case study section, the computational efficiency and accuracy of the presented algorithm are verified over wide range of instance sizes in terms of CPU time and quality of solutions.

Article

Download

View A new approximation algorithm for unrelated parallel machine scheduling problem with release dates