日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細


公開

会議論文

Dynamic Scheduling with Incomplete Information

MPS-Authors
/persons/resource/persons44076

Bast,  Hannah
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
There are no locators available
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
フルテキスト (公開)
公開されているフルテキストはありません
付随資料 (公開)
There is no public supplementary material available
引用

Bast, H. (1998). Dynamic Scheduling with Incomplete Information. In Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA-98) (pp. 182-191). New York, USA: ACM Press.


引用: https://hdl.handle.net/11858/00-001M-0000-000F-3783-9
要旨
We consider the following scheduling problem: Our goal is to execute a given amount of arbitrarily decomposable work on a distributed machine as quickly as possible. The work is maintained by a central scheduler that can assign chunks of work of an arbitrary size to idle processors. The difficulty is that the processing time required for a chunk is not exactly predictable---usually the less, the larger the chunk---and that processors suffer a delay for each assignment. Our objective is to minimize the total wasted time of the schedule, that is, the sum of all delays plus the idle times of processors waiting for the last processor to finish. We introduce a new deterministic model for this setting, based on estimated ranges $[\alpha(w),\beta(w)]$ for processing times of chunks of size $w$. Depending on $\alpha$, $\beta$, and a measure for the overall deviation from these estimates, we can prove matching upper and lower bounds on the wasted time, the former being achieved by our new \emph{balancing} strategy. This is in sharp contrast with previous work that, even under the strong assumption of independent, approximately normally distributed chunk processing times, proposed only heuristic scheduling schemes supported merely by empirical evidence. Our model naturally subsumes this stochastic setting, and our generic analysis is valid for most of the existing schemes too, proving them to be non-optimal.