Scheduling Jobs Before Shut Down
| dc.contributor.author | Liberatore, Vincenzo | en_US |
| dc.date.accessioned | 2004-05-31T23:00:58Z | |
| dc.date.available | 2004-05-31T23:00:58Z | |
| dc.date.created | 1999-12 | en_US |
| dc.date.issued | 2000-02-15 | en_US |
| dc.description.abstract | Distributed systems execute background or alternative jobs while waiting for data or requests to arrive from another processor. In those cases, the following shut-down scheduling problem arises: given a set of jobs of known processing time, schedule them on m machines so as to maximize the total weight of jobs completed before an initially unknown deadline. We will present optimally competitive deterministic and randomized algorithms for shut-down scheduling. Our deterministic algorithm is parameterized by the number of machines m. Its competitive ratio increases as the number of machines decreases, but it is optimal for any given choice of m. Such family of deterministic algorithm can be translated into a family of randomized algorithms that use progressively less randomization and that are optimal for the given amount of randomization. Hence, we establish a precise trade-off between amount of randomization and competitive ratios. Distributed systems execute background or alternative jobs while waiting for data or requests to arrive from another processor. In those cases, the following <em>shut-down scheduling problem</em> arises: given a set of jobs of known processing time, schedule them on <em>m</em> machines so as to maximize the total weight of jobs completed before an initially unknown deadline. We will present optimally competitive deterministic and randomized algorithms for shut-down scheduling. Our deterministic algorithm is parameterized by the number of machines <em>m</em>. Its competitive ratio increases as the number of machines decreases, but it is optimal for any given choice of <em>m</em>. Such family of deterministic algorithm can be translated into a family of randomized algorithms that use progressively less randomization and that are optimal for the given amount of randomization. Hence, we establish a precise trade-off between amount of randomization and competitive ratios. (Also cross-referenced as UMIACS-TR-99-72) | en_US |
| dc.format.extent | 557597 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/1045 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-4081 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-99-72 | en_US |
| dc.title | Scheduling Jobs Before Shut Down | en_US |
| dc.type | Technical Report | en_US |