An approximation algorithm for scheduling two parallel machines with capacity constraints.
type: Item
instance of: scholarly article
title: An approximation algorithm for scheduling two parallel machines with capacity constraints.
zbMATH Open document ID: 1126.90031
DOI: 10.1016/S0166-218X(02)00601-7
author: Heng Yang
author: Yinyu Ye
author: Jiawei Zhang
published in: Discrete Applied Mathematics
publication date: 2003-09-22T00:00:00Z
review text: In the paper an approximation algorithm for the parallel machine problem \(P2| q| \sum{w_jC_j}\) is proposed. Jobs have to be processed on two identical parallel machines with limited capacity such that the weighted sum of completion times is minimized. After formulating the problem as a maximum cut problem with capacity constraints it is solved with semidefinite programming. It is proved that the approximation algorithm has a worst-case ratio of 1.1626.
reviewed by: Sigrid Knust
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 1984624
zbMATH Keywords: scheduling
zbMATH Keywords: parallel machines
zbMATH Keywords: maximum cut
zbMATH Keywords: approximation algorithm
zbMATH Keywords: semidefinite programming
describes a project that uses: Outward rotations
MaRDI profile type: Publication
cites work: Q4247459
cites work: Q4247460
cites work: Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
cites work: Q3002852
cites work: Q4231921
cites work: Semidefinite relaxation and nonconvex quadratic optimization
cites work: Algorithms for Scheduling Independent Tasks
cites work: Algorithmic derandomization via complexity theory
cites work: Convex quadratic and semidefinite programming relaxations in scheduling
cites work: Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
cites work: A .699-approximation algorithm for Max-Bisection.
cites work: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
full work available at URL: s0166-218x(02)00601-7
OpenAlex ID: W2021083541
description: scientific article; zbMATH DE number 1984624