×

An approximation algorithm for single machine scheduling with controllable processing times. (Chinese. English summary) Zbl 1053.90105

Summary: We derive a 1.2752-approximation algorithm for the NP-hard single machine total weighted completion time problem with controllable processing times by the technique of semidefinite programming relaxation.

MSC:

90C22 Semidefinite programming
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
68W25 Approximation algorithms
PDFBibTeX XMLCite