Preemptive scheduling in overloaded systems

✍ Scribed by Marek Chrobak; Leah Epstein; John Noga; Jiřı́ Sgall; Rob van Stee; Tomáš Tichý; Nodari Vakhania

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 209 KB
• Volume: 67
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(03)00070-9

✦ Synopsis

The following scheduling problem is studied: We are given a set of tasks with release times, deadlines, and profit rates. The objective is to determine a 1-processor preemptive schedule of the given tasks that maximizes the overall profit. In the standard model, each completed task brings profit, while noncompleted tasks do not. In the metered model, a task brings profit proportional to the execution time even if not completed. For the metered task model, we present an efficient offline algorithm and improve both the lower and upper bounds on the competitive ratio of online algorithms. Furthermore, we prove three lower bound results concerning resource augmentation in both models.