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

Quality of move-optimal schedules for minimizing total weighted completion time

โœ Scribed by Tobias Brueggemann; Johann L. Hurink; Walter Kern

Publisher
Elsevier Science
Year
2006
Tongue
English
Weight
184 KB
Volume
34
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

โœฆ Synopsis

We study the minimum total weighted completion time problem on identical machines. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio 3 2 . In a special case, the approximation ratio is 3 2 -1/ โˆš 6 โ‰ˆ 1.092.

๐Ÿ“œ SIMILAR VOLUMES

Approximation algorithms for minimizing
Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel
โœ Joseph Y-T. Leung; Haibing Li; Michael Pinedo ๐Ÿ“‚ Article ๐Ÿ“… 2006 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 214 KB

## Abstract We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is re

Scheduling of a single machine to minimi
Scheduling of a single machine to minimize total weighted completion time subject to release dates
โœ Lucio Bianco; Salvatore Ricciardelli ๐Ÿ“‚ Article ๐Ÿ“… 1982 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 764 KB

## Abstract In this paper the __n__/1/__r__~j~ ฮฃ~j~ __w__~__j__~ __C__~__j__~ problem under the assumptions of nonpreemptive sequencing and sequence independent processing times is investigated. After pointing out the fundamental properties, some dominance sufficient conditions among sequences are