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

On an on-line scheduling problem for parallel jobs

โœ Scribed by Edwin Naroska; Uwe Schwiegelshohn

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
101 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

This paper addresses the non-preemptive on-line scheduling of parallel jobs. In particular we assume that the release dates and the processing times of the jobs are unknown. It is already known that for this problem Garey and Graham's list scheduling algorithm achieves the competitive factor 2 -1 m for the makespan if m identical machines are available and if each job requires only a single machine for processing. Here, we show that the same factor also holds in the case of parallel jobs.

๐Ÿ“œ SIMILAR VOLUMES

Randomized On-line Scheduling of Paralle
Randomized On-line Scheduling of Parallel Jobs
โœ Jiล™ฤฑ́ Sgall ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 230 KB

We study randomized on-line scheduling on mesh machines. We show that for scheduling independent jobs randomized algorithms can achieve a significantly better performance than deterministic ones; on the other hand with dependencies randomization does not help.

Scheduling jobs and maintenance activiti
Scheduling jobs and maintenance activities on parallel machines
โœ Chung-Yee Lee; Zhi-Long Chen ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 147 KB ๐Ÿ‘ 1 views

Most machine scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines need to be maintained and hence may become unavailable during certain periods. In this paper, we study the problem of processing a set of n jobs on m parallel machin

Exact algorithms for scheduling multiple
Exact algorithms for scheduling multiple families of jobs on parallel machines
โœ Zhi-Long Chen; Warren B. Powell ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 140 KB

## Abstract In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent o