On the Impact of Transport Times in Flexible Job Shop Scheduling Problems

Manufacturing systems require a careful scheduling of the resource usage to maximize the production efficiency. In a completely automated environment, the transport system should be orchestrated to work smoothly with the other resources. While the impact of job characteristics, such as fixed or variable processing times of the tasks composing the jobs, or task dependencies, has been extensively studied, the role of the transport system has received less attention.In this paper we consider a conveyor belt as a mean of transportation among a set of production machines. In this scenario, there is no input or output buffer at the machines, and the transport times depend on the availability of the machines. We propose a heuristic based on randomization, called SCHED-T, which is able to find a near optimal joint schedule for job processing and transfer in few seconds. We test our solution on known benchmarks, along with real-world instances, showing that our scheduler is able to predict accurately the overall processing time of a production line.