✦ LIBER ✦

Approximation schemes for scheduling on parallel machines

✍ Scribed by Noga Alon; Yossi Azar; Gerhard J. Woeginger; Tal Yadid

Publisher: Springer US
Year: 1998
Tongue: English
Weight: 124 KB
Volume: 1
Category: Article
ISSN: 1094-6136
DOI: 10.1002/(sici)1099-1425(199806)1:1<55::aid-jos2>3.0.co;2-j

No coin nor oath required. For personal study only.

✦ Synopsis

We discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The goal is to optimize objective functions that solely depend on the machine completion times.

As a main result, we identify some conditions on the objective function, under which the resulting scheduling problems possess a polynomial-time approximation scheme. Our result contains, generalizes, improves, simplifies, and unifies many other results in this area in a natural way.

📜 SIMILAR VOLUMES

A min-sum 3/2-approximation algorithm fo

A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines

✍ Fabián A. Chudak 📂 Article 📅 1999 🏛 Springer US 🌐 English ⚖ 70 KB

We consider the problem of minimizing the sum of weighted completion times of jobs scheduled on unrelated parallel machines. That is, there are n jobs and m machines; job j takes p GH units of time if processed on machine i and has a weight w H . If C H is the completion time of job j, the objective

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

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

Scheduling for parallel dedicated machin

Scheduling for parallel dedicated machines with a single server

✍ Celia A. Glass; Yakov M. Shafransky; Vitaly A. Strusevich 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 443 KB

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two paralle

Polynomial time approximation algorithms

Polynomial time approximation algorithms for machine scheduling: ten open problems

✍ Petra Schuurman; Gerhard J. Woeginger 📂 Article 📅 1999 🏛 Springer US 🌐 English ⚖ 91 KB 👁 2 views

We discuss what we consider to be the 10 most vexing open questions in the area of polynomial time approximation algorithms for NP-hard deterministic machine scheduling problems. We summarize what is known on these problems, we discuss related results, and we provide pointers to the literature. Copy

Scheduling on M parallel machines subjec

Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time

✍ Ali Allahverdi; John Mittenthal 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 346 KB

Efficient support for fine-grain paralle

Efficient support for fine-grain parallelism on shared-memory machines

✍ LOWENTHAL, DAVID K.; FREEH, VINCENT W.; ANDREWS, GREGORY R. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB 👁 1 views

A coarse-grain parallel program typically has one thread (task) per processor, whereas a finegrain program has one thread for each independent unit of work. Although there are several advantages to fine-grain parallelism, conventional wisdom is that coarse-grain parallelism is more efficient. This p