In this paper, the identical parallel machine scheduling problem with periodic tool changes due to wear is addressed under the total completion time minimization objective. Due to machine availability restrictions induced by tool replacement operations, the problem is NP-hard in the strong sense. A mixed integer linear programming (MILP) model has been developed with the aim to provide the global optimum for small-sized test cases. Furthermore, a hybrid metaheuristic procedure based on genetic algorithms has been specifically designed to cope with larger instances. A comprehensive experimental analysis supported by a non-parametric statistical test has been fulfilled to select the best metaheuristic configuration in terms of decoding strategy and parameters driving the search mechanism as well. Then, the proposed optimization procedure has been compared with three alternative methods arising from the relevant literature on the basis of a wide benchmark of test cases. The obtained results, also supported by a proper statistical analysis, demonstrate the effectiveness of the proposed approach for solving the tool change scheduling problem at hand.

Minimizing the total completion time on a parallel machine system with tool changes

COSTA, ANTONIO;FICHERA, Sergio
2016

Abstract

In this paper, the identical parallel machine scheduling problem with periodic tool changes due to wear is addressed under the total completion time minimization objective. Due to machine availability restrictions induced by tool replacement operations, the problem is NP-hard in the strong sense. A mixed integer linear programming (MILP) model has been developed with the aim to provide the global optimum for small-sized test cases. Furthermore, a hybrid metaheuristic procedure based on genetic algorithms has been specifically designed to cope with larger instances. A comprehensive experimental analysis supported by a non-parametric statistical test has been fulfilled to select the best metaheuristic configuration in terms of decoding strategy and parameters driving the search mechanism as well. Then, the proposed optimization procedure has been compared with three alternative methods arising from the relevant literature on the basis of a wide benchmark of test cases. The obtained results, also supported by a proper statistical analysis, demonstrate the effectiveness of the proposed approach for solving the tool change scheduling problem at hand.
Tool change; Unavailability; Metaheuristics; Mixed integer linear programming; Dunn’s test
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.11769/17954
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 22
social impact