Résumés
Abstract
In the paper we mainly study the Cmax problem of scheduling n groups of jobs on n special-purpose processors and m general-purpose processors at the same speed provided the ready time of each job is less than times of its processing time. We first propose an improved LS algorithm. We then show that the bound for the ratio of the approximate solution T LS to the optimal solution T is less than (1 + )(2 − 1 n+m ). Moreover, we give an example to illustrate that it is tight for any ≥ 0.
Keywords:
- Heuristic algorithm,
- LS algorithm,
- LPT algorithm,
- general-purpose processors,
- special-purpose processors,
- tight bound
Veuillez télécharger l’article en PDF pour le lire.
Télécharger