|
|||||
|
|
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem |
|
| Authors: | Cynthia A Phillips Andreas S Schulz David B Shmoys Cliff Stein Joel Wein |
| Institution: | (1) Sandia National Labs, Albuquerque, NM;(2) Department of Mathematics, Technical University of Berlin, 10623 Berlin, Germany;(3) School of Operations Research & Industrial Engineering and Department of Computer Science, Cornell University, Ithaca, NY, 14853;(4) Department of Computer Science, Sudikoff Laboratory, Dartmouth College, Hanover, NH;(5) Department of Computer Science, Polytechnic University, Brooklyn, NY, 11201 |
| Abstract: | We consider the problem of scheduling n jobs withrelease dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion time of the optimal nonpreemptive schedule to that of the optimal preemptive schedule is at most 7/3, improving a bound of
Shmoys and Wein. |
| Keywords: | scheduling preemptive scheduling release dates identical parallel machines average completion time approximation algorithms relaxations linear programming |
| 本文献已被 SpringerLink 等数据库收录！ | |