  


A new approximation algorithm for unrelated parallel machine scheduling problem with release dates
Zhi Pei(peizhi82163.com) 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 NPhard in the strong sense. Albeit the computational complexity, which renders the optimality seeking a formidable task within polynomial time, a 4approximation algorithm is devised and proved in comparison with the 16/3approximation(Hall et al. 1997). In the newly proposed algorithm, the original scheduling problem is divided into several subproblems based on the release dates. For each subproblem, a convex quadratic integer programming (CQIP) model is constructed in accordance with the specific problem structure. Then a semidefinite programming approach is implemented to produce a lower bound via the semidefinite relaxation of each subproblem. Furthermore, by considering the 01 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 subproblem. Consequently, the solution of the original scheduling problem can be constituted by integrating the outcomes of the subproblems 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; Semidefinite programming; Approximation algorithm; Branch and bound Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 3: Applications  OR and Management Sciences (Scheduling ) Citation: Download: [PDF] Entry Submitted: 05/08/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  