Minimizing total tardiness of orders with reentrant lots in a hybrid flowshop

This study focuses on a hybrid flowshop scheduling problem, in which there are serial stages, each with identical parallel machines. In the hybrid flowshop, each order is composed of multiple lots with the same due date, and each lot can be processed on any one of parallel machines at each stage. In addition, there are reentrant flows since lots of certain orders have to visit the stages twice. Heuristic algorithms are suggested for the scheduling problem with the objective of minimizing total tardiness of a given set of orders. In these algorithms, the list-scheduling method is employed, and lots are scheduled with priorities determined with a construction method. Computational experiments are performed on randomly generated test problems. Results show that the suggested algorithms perform better than well-known dispatching rules for various scheduling problems and an algorithm that is used in a real system.