Brief Announcement
| Autor: | Jing Li, Kefu Lu, Kunal Agrawal, Benjamin Moseley |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
020203 distributed computing
Mathematical optimization Parallelizable manifold ComputingMilieux_THECOMPUTINGPROFESSION Job shop scheduling Computer science Distributed computing 0102 computer and information sciences 02 engineering and technology Directed acyclic graph 01 natural sciences Scheduling (computing) 010201 computation theory & mathematics 8. Economic growth Associated function 0202 electrical engineering electronic engineering information engineering |
| Zdroj: | SPAA |
| DOI: | 10.1145/3087556.3087590 |
| Popis: | We consider scheduling parallelizable jobs online to maximize the throughput or profit of the schedule. A set of n jobs arrive online and each job Ji has an associated function pi(t), the profit obtained for finishing job Ji at time t. Each job has its own arbitrary non-increasing profit function. We consider the case where each job is a parallel job that can be represented as a directed acyclic graph (DAG). We give the first non-trivial results for the profit scheduling problem for DAG jobs showing O(1)-competitive algorithms using resource augmentation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|