Optimization Online


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

Zhi Pei(peizhi82***at***163.com)
Mingzhong Wan(825549106***at***qq.com)
Ziteng Wang(zwang3***at***niu.edu)

Abstract: 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.

Keywords: Unrelated parallel machine scheduling; Release dates; Semi-definite programming; Approximation algorithm; Branch and bound

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Applications -- OR and Management Sciences (Scheduling )


Download: [PDF]

Entry Submitted: 05/08/2018
Entry Accepted: 05/08/2018
Entry Last Modified: 05/08/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society