A \(\frac 32\)-approximation algorithm for parallel machine scheduling with controllable processing times

DOI10.1016/S0167-6377(01)00080-3zbMath0981.90027MaRDI QIDQ5949906

Feng Zhang, Zhi-Long Chen, Guochun Tang

Publication date: 5 December 2001

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

quadratic programmingapproximation algorithmscheduling with controllable processing timestotal weighted completion time problem

Mathematics Subject Classification ID

Quadratic programming (90C20) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items

A survey of scheduling with controllable processing times, Unrelated parallel machine scheduling problem with special controllable processing times and setups, Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms, Approximation schemes for job shop scheduling problems with controllable processing times, Single machine scheduling with resource dependent release times and processing times, Multicriteria scheduling

Cites Work

• A survey of results for sequencing problems with controllable processing times
• Single machine scheduling with discretely controllable processing times
• Some comments on sequencing with controllable processing times
• A bicriterion approach to preemptive scheduling of parallel machines with controllable job processing times
• Convex quadratic and semidefinite programming relaxations in scheduling
• Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine
• Scheduling Multiple Variable-Speed Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item