In the field of Scheduling Optimization, the Job-Shop scheduling problem entails a high level of complexity and is often solved with the aid of metaheuristic algorithms. In its Flexible version it is possible to choose the machine which wil l execute a specific operation. In this scenario both the scheduling and the routing problem need to be solved when aiming to optimize the production makespan. Many optimization approaches account for the routing decision by encoding it in addition to the job ordering, to let the metaheuristic algorithm account for this decision. The No-Wait Flexible Job-Shop is a variant of the problem characterized by consecutiveness constraints among operations, which need to start directly after the previous one's completion time. These constraints can be encountered for example in the pharmaceutical and metallurgic sector. In this context Timetabling Algorithms are used to decode the solution and provide a makespan given a schedule. In this paper, an approach to exploit the Timetabling Algorithm routing capabilities is discussed, in order to investigate which decision level of the optimization procedure shall execute the routing selection. Finally, possible experimental settings to validate the most convenient routing strategy are discussed.

A heuristic algorithm based on routing decisions for the No-Wait Flexible Job-Shop scheduling problem

Nucera D.;Negri E.;Fumagalli L.
2021

Abstract

In the field of Scheduling Optimization, the Job-Shop scheduling problem entails a high level of complexity and is often solved with the aid of metaheuristic algorithms. In its Flexible version it is possible to choose the machine which wil l execute a specific operation. In this scenario both the scheduling and the routing problem need to be solved when aiming to optimize the production makespan. Many optimization approaches account for the routing decision by encoding it in addition to the job ordering, to let the metaheuristic algorithm account for this decision. The No-Wait Flexible Job-Shop is a variant of the problem characterized by consecutiveness constraints among operations, which need to start directly after the previous one's completion time. These constraints can be encountered for example in the pharmaceutical and metallurgic sector. In this context Timetabling Algorithms are used to decode the solution and provide a makespan given a schedule. In this paper, an approach to exploit the Timetabling Algorithm routing capabilities is discussed, in order to investigate which decision level of the optimization procedure shall execute the routing selection. Finally, possible experimental settings to validate the most convenient routing strategy are discussed.
Proceedings of the 26th Summer School Francesco Turco
File in questo prodotto:
File Dimensione Formato  
Nucera et al 2021.pdf

accesso aperto

: Publisher’s version
Dimensione 267.91 kB
Formato Adobe PDF
267.91 kB Adobe PDF Visualizza/Apri

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/11311/1203295
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact