| Convex quadratic programming relaxations for parallel machine scheduling with controllable processing times subject to release times |
| |
| 作者姓名： | ZHANG Feng CHEN Feng TANG Guochun |
| |
| 作者单位： | Department of Mathematics, Shanghai Second Polytechnic University, Shanghai 201209, China;Department of Mathematics,Tongji University, Shanghai 200092, China,Department of Mathematics, Shanghai University, Shanghai 200436, China,Department of Mathematics, Shanghai Second Polytechnic University, Shanghai 201209, China;Department of Mathematics,Tongji University, Shanghai 200092, China |
| |
| 摘 要： | 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.
|
| 关 键 词： | scheduling with controllable processing time release time quadratic programming approximation alg |
Convex quadratic programming relaxations for parallel machine scheduling with controllable processing times subject to release times |
| |
| ZHANG Feng,CHEN Feng,TANG Guochun.Convex quadratic programming relaxations for parallel machine scheduling with controllable processing times subject to release times[J].Progress in Natural Science,2004,14(9):758-765. |
| |
| Authors: | ZHANG Feng CHEN Feng TANG Guochun |
| |
| Institution: | 1. Department of Mathematics, Shanghai Second Polytechnic University, Shanghai 201209, China;Department of Mathematics,Tongji University, Shanghai 200092, China
2. Department of Mathematics, Shanghai University, Shanghai 200436, China |
| |
| Abstract: | 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. |
| |
| Keywords: | scheduling with controllable processing time release time quadratic programming approximation algorithm |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《自然科学进展(英文版)》浏览原始摘要信息 |
| 点击此处可从《自然科学进展(英文版)》下载免费的PDF全文 |
