A new polynomial algorithm is developed for the classical multiprocessor scheduling problem in which independent jobs arenonpreemptively scheduled on identical parallel machines with the objective of minimizing the makespan, i.e. the latest job finishing time. The algorithm at first generates and merges a set of partialsolutions in order to obtain a feasible solution for themultiprocessor scheduling problem. Then a set of bin packing problems are solved in order to improve the solution, by iterativelyusing a MultiFit type procedure on different job sets. The effectiveness of this approach is evaluated by solving a large number of benchmark instances. The results indicate that theproposed algorithm, called PSMF, is very competitive with well known constructive algorithms for a wide range of instances. Furthermore, PSMF is competitive with respect to some of the bestheuristics for parallel machine scheduling problems only when it uses a 2-exchange procedure.

Partial Solutions and MultiFit Algorithm for Multiprocessor Scheduling

PALETTA, Giuseppe;
2015

Abstract

A new polynomial algorithm is developed for the classical multiprocessor scheduling problem in which independent jobs arenonpreemptively scheduled on identical parallel machines with the objective of minimizing the makespan, i.e. the latest job finishing time. The algorithm at first generates and merges a set of partialsolutions in order to obtain a feasible solution for themultiprocessor scheduling problem. Then a set of bin packing problems are solved in order to improve the solution, by iterativelyusing a MultiFit type procedure on different job sets. The effectiveness of this approach is evaluated by solving a large number of benchmark instances. The results indicate that theproposed algorithm, called PSMF, is very competitive with well known constructive algorithms for a wide range of instances. Furthermore, PSMF is competitive with respect to some of the bestheuristics for parallel machine scheduling problems only when it uses a 2-exchange procedure.
Multiprocessor scheduling ; Identical parallel machines ; MultiFit ; Approximation algorithms
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/139144
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact