Single-Machine Scheduling with Release Times and Tails |
| |
| Authors: | Nodari Vakhania |
| |
| Institution: | 1. Science Faculty, State University of Morelos, Av. Universidad 1001, Cuernavaca, 62210, Morelos, Mexico, and
2. Inst. of Computational Math., Akuri 8, Tbilisi, 93, Georgia
|
| |
| Abstract: | We study the problem of scheduling jobs with release times and tails on a single machine with the objective to minimize the makespan. This problem is strongly NP-hard, however it is known to be polynomially solvable if all jobs have equal processing time P. We generalize this result and suggest an O(n 2 log nlog P) algorithm for the case when the processing times of some jobs are restricted to either P or 2P. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
