Convex quadratic programming relaxations for parallel machine scheduling with controllable processin

• 作 者: ZHANG Feng CHEN Feng TANG Guoc
• 机 构: Department of Mathematics
• 出 处: 自然科学进展
• 发表日期: 2004年期
• 关键词: scheduling with controllable processing time release time quadratic programming

Scheduling unrelated parallel machines with controllable processing times subject to release times is investigated. Based on the convex quadratic programming relaxation and the randomized rounding strategy, a 2-approximation algorithm is obtained for a special case with the all-or-none property and then a 3-approximation algorithm is presented for general problem.