Open-shop production scheduling with reverse flows

Abstract The purpose of this paper is to present a mixed-integer linear programming model for the scheduling problem in an open-shop manufacturing system involving reverse flows, where two job flows (direct and reverse) in two opposite directions are processed on the same machines. The aim is to minimize the maximum completion time of all jobs on all machines (i.e., the makespan). A numerical example is presented and solved using the GAMS software (version 25.1.2) to validate the proposed mathematical model. As this problem is NP-hard, a vibration damping-based optimization (VDO) algorithm is proposed to solve large-scale problems in reasonable execution times. Besides, the Taguchi experimental design approach is employed to adjust and estimate the appropriate values of the VDO’s parameters. Finally, the computational results of this algorithm are compared to the results obtained by a Simulated Annealing (SA), Cuckoo Search (CS), Ant Colony Optimization (ACO), Harmony Search (HAS), Imperialist Competitive (ICA), and Bat algorithm (BA). The statistical comparison results on several randomly generated problems of different sizes using the Kruskal-Wallis test reveals the better performance of the VDO algorithm.