Semi-definite relaxation algorithm for single machine scheduling with controllable processing times

DOI10.1142/S0252959905000142MaRDI QIDQ1774270zbMATH OpenFDO

Authors Feng Chen, Liansheng Zhang

Publication date 29 April 2005

Published in Chinese Annals of Mathematics. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0252959905000142

zbMATH Keywords

approximation algorithmscheduling with controllable timessemi-definite programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• Convex quadratic programming relaxations for parallel machine scheduling with controllable processing times subject to release times
• An approximation algorithm for a single-machine scheduling problem with release times, delivery times and controllable processing times
• scientific article; zbMATH DE number 2089208
• A linear time approximation scheme for the single machine scheduling problem with controllable processing times
• Single machine scheduling with controllable processing times and compression costs. I: Equal times and costs

Cited in

(3)

• Immediate schedule adjustment and semidefinite relaxation
• Convex quadratic programming relaxations for parallel machine scheduling with controllable processing times subject to release times
• Extending the single machine-based relaxation scheme for the job shop scheduling problem

This page was built for publication: Semi-definite relaxation algorithm for single machine scheduling with controllable processing times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1774270)