Résumés
Abstract
In the paper we mainly study the makespan problem of scheduling n groups of jobs on n special-purpose processors and m general-purpose processors at different speeds. We first propose an improved LPT algorithm and investigate several properties of this algorithm. We then obtain an upper bound for the ratio of the approximate solution T to the optimal solution T* under the improved LPT algorithm.
Keywords:
- Mathematics Subject Classification (2000): 90B35, 68M20,
- Heuristic algorithm,
- LPT algorithm,
- approximate solutions,
- optimal solutions,
- upper bound
Veuillez télécharger l’article en PDF pour le lire.
Télécharger