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

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.