Non-clairvoyant scheduling for weighted flow time

A non-clairvoyant scheduler makes decisions having no knowledge of jobs. It does not know when the jobs will arrive in the future, that is, it is online, and how long the jobs will be executed after they arrive. For non-clairvoyant scheduling, we first study the problem to minimize the total stretch...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2003-07, Vol.87 (1), p.31-37
Main Authors: Kim, Jae-Hoon, Chwa, Kyung-Yong
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Computer science
control theory
systems
Computer systems performance. Reliability
Decision making
ESP
Exact sciences and technology
Extrasensory perception
Flow control
Flow time
Non-clairvoyance
Operational research and scientific management
Operational research. Management science
Production scheduling
Scheduling
Scheduling, sequencing
Software
Studies
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A non-clairvoyant scheduler makes decisions having no knowledge of jobs. It does not know when the jobs will arrive in the future, that is, it is online, and how long the jobs will be executed after they arrive. For non-clairvoyant scheduling, we first study the problem to minimize the total stretch. And we also consider the case in which the weights of jobs are known when they arrive, while their lengths are still unknown. In this case, we find a schedule to minimize the total weighted flow time. The weighted versions of well-known algorithms, Round Robin and Balance, are investigated.
ISSN:0020-0190
1872-6119
DOI:10.1016/S0020-0190(03)00231-X