A Fast Algorithm for Scheduling Equal-Length Jobs on Identical Machines

NODARI VAKHANIA

Resumen


THE PROBLEM OF SEQUENCING JOBS OF EQUAL DURATIONS WITH AVAILABLE (READINESS) TIMES AND THE ADDITIONAL TAILS ON A SET OF PARALLEL IDENTICAL PROCESSORS IS CONSIDERED. THE OBJECTIVE IS TO MINIMIZE THE MAXIMAL COMPLETION TIME. WE PRESENT A NEW POLYGOMIAL ALGORITHM WHICH IMPROVES THE RUNNIG TIME OF THE PREVIOUSLY KNOWN BEST ALGORITHM UNDER THE REALISTIC ASSUMPTION THAT TAILS OF ALL JOBS ARE BOUNDED BY SOME SUFFICIENTLY LARGE CONSTANT.

Palabras clave


SCHEDULING; IDENTICAL PROCESSORS; READINESS TIME; TAIL; COMPUTATIONAL COMPLEXITY

Texto completo:

pdf


Contacto:
Oscar Zavala