We consider the multiprocessor scheduling problem in which independent jobs are scheduled on identical parallel machines, with the objective of minimizing the normalized sum of square for workload deviations (NSSWD) criterion in order to obtain workload balancing. NSSWD and other criteria for the related problem of number partitioning are presented from a statistical viewpoint, which allows to derive some insightful connections with statistical measures of dispersion. A new local search algorithm is also developed. The algorithm at first generates and merges a set of partial solutions in order to obtain a feasible solution for the multiprocessor scheduling problem. Then a set of interchange procedures are utilized in order to improve the solution. The effectiveness of this approach is evaluated by solving a large number of benchmark instances.

A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria

COSSARI, Anthony;PALETTA, Giuseppe;
2012

Abstract

We consider the multiprocessor scheduling problem in which independent jobs are scheduled on identical parallel machines, with the objective of minimizing the normalized sum of square for workload deviations (NSSWD) criterion in order to obtain workload balancing. NSSWD and other criteria for the related problem of number partitioning are presented from a statistical viewpoint, which allows to derive some insightful connections with statistical measures of dispersion. A new local search algorithm is also developed. The algorithm at first generates and merges a set of partial solutions in order to obtain a feasible solution for the multiprocessor scheduling problem. Then a set of interchange procedures are utilized in order to improve the solution. The effectiveness of this approach is evaluated by solving a large number of benchmark instances.
Parallel machines scheduling; Normalized sum of square for workload; Statistical measures of dispersion; Heuristics
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: https://hdl.handle.net/20.500.11770/142202
 Attenzione

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

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