Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
Copyright policy )Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
Summary: The author develops an algorithm assigning \(\lfloor n/2\rfloor\) tasks to one processor and \(\lceil n/2\rceil\) to another. The absolute difference between the optimal makespan and the heuristic makespan is proved to be bounded by \(O(\log n/n^ 2)\), almost surely, when task durations are independently and uniformly distributed on \([0,1]\). Total flow time is minimized if the tasks on each processor are sequenced in nondecreasing order of their processing times.
Deterministic scheduling theory in operations research, Analysis of algorithms and problem complexity, makespan scheduling, probabilistic algorithm analysis, Performance evaluation, queueing, and scheduling in the context of computer systems
Deterministic scheduling theory in operations research, Analysis of algorithms and problem complexity, makespan scheduling, probabilistic algorithm analysis, Performance evaluation, queueing, and scheduling in the context of computer systems
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).25 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!