๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Non-clairvoyant scheduling for weighted flow time

โœ Scribed by Jae-Hoon Kim; Kyung-Yong Chwa

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
115 KB
Volume
87
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ SIMILAR VOLUMES

One-machine job-scheduling with non-cons
One-machine job-scheduling with non-constant capacity โ€” Minimizing weighted completion times
โœ H.F. Amaddeo; W.M. Nawijn; A. van Harten ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 720 KB

In this paper an n-job one-machine scheduling problem is considered, in which the machine capacity is time-dependent and jobs are characterized by their work content. The objective is to minimize the sum of weighted completion times. A necessary optimality condition is presented and we discuss some