Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Approximating scheduling unrelated parallel machines in parallel

Autor
Serna, M.; Xhafa, F.
Tipus d'activitat
Article en revista
Revista
Computational optimization and applications
Data de publicació
2002-03
Volum
21
Número
3
Pàgina inicial
325
Pàgina final
338
DOI
https://doi.org/10.1023/A:1013781304506 Obrir en finestra nova
URL
https://link.springer.com/article/10.1023/A:1013781304506 Obrir en finestra nova
Resum
We show how to approximate in NC the problem of scheduling unrelated parallel machines, for a fixed number of machines in which the makespan Cmax is the objective function to minimize. We develop an approximate NC algorithm which finds a schedule whose length is at most (1+o(1))(Cmax*+v(3·Cmax*ln(2n(n-1)/e))), where Cmax*, denotes the optimal schedule, n the total number of jobs and e a small positive constant. Our approach shows how to relate the linear program obtained by relaxing the integer...
Paraules clau
Computational complexity, Integer programming, Linear programming, Scheduling
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants