A new Modified Longest Processing Time algorithm and an Iterated Local Search algorithm are developed for the scheduling problem in which independent jobs are nonpreemptively scheduled on uniform parallel machines with the objective of minimizing the makespan, i.e., the completion time of the last job. Our computational results show that the Modified Longest Processing Time algorithm is able to reduce the average error, to increase the number of optimal solutions, and to determine a greater number of best solutions with respect to the Longest Processing Time algorithm. Furthermore, the Iterated Local Search algorithm is shown to be effective in reducing the average error significantly and yielding optimal solutions in over 80% of the tested instances.

Heuristics for Scheduling Uniform Machines

Domenico De Giovanni;Giuseppe Paletta;
2018

Abstract

A new Modified Longest Processing Time algorithm and an Iterated Local Search algorithm are developed for the scheduling problem in which independent jobs are nonpreemptively scheduled on uniform parallel machines with the objective of minimizing the makespan, i.e., the completion time of the last job. Our computational results show that the Modified Longest Processing Time algorithm is able to reduce the average error, to increase the number of optimal solutions, and to determine a greater number of best solutions with respect to the Longest Processing Time algorithm. Furthermore, the Iterated Local Search algorithm is shown to be effective in reducing the average error significantly and yielding optimal solutions in over 80% of the tested instances.
978-988-14048-8-6
scheduling, uniform parallel machines, longest processing time algorithm, iterated local search algorithm
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/283796
 Attenzione

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

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