Artículos de revistas
A Fast Algorithm for Scheduling Equal-Length Jobs on Identical Machines
A Fast Algorithm for Scheduling Equal-Length Jobs on Identical Machines
Autor
VAKHANIA, NODARI
Institución
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. 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.