Online deadline scheduling on faster machines.
type: Item
instance of: scholarly article
title: Online deadline scheduling on faster machines.
zbMATH Open document ID: 1042.68017
DOI: 10.1016/S0020-0190(02)00332-0
author: Jaehoon Kim
author: Kyung-Yong Chwa
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: Online deadline scheduling is to determine which jobs are accepted or rejected, where jobs have the deadline by which they must finish their processing and they arrive in the online fashion. The slack of a job is the gap between its arrival time and the last time when it can first be scheduled to meet its deadline. The job instance is given such that the slack of each job is at least \(\kappa\) times its processing time, where \(\kappa\) is called patience. In this paper, online algorithms have faster machines than the adversary. We investigate the speed of machines on which the online algorithms can achieve the optimality and parametrize them by the patience.
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 1856502
zbMATH Keywords: Scheduling
zbMATH Keywords: Online algorithms
MaRDI profile type: Publication
cites work: Improvements in throughout maximization for real-time scheduling
cites work: On-line scheduling with hard deadlines
cites work: Q4252312
cites work: Speed is as powerful as clairvoyance
cites work: Q4551382
cites work: Performance guarantee for online deadline scheduling in the presence of overload
cites work: Q3128889
cites work: Q4526977
full work available at URL: s0020-0190(02)00332-0
OpenAlex ID: W2080816716
description: scientific article; zbMATH DE number 1856502