A new heuristic for the flowshop scheduling problem to minimize makespan and maximum tardiness

This paper presents a new heuristic for solving the flowshop scheduling problemthat aims to minimize makespan and maximize tardiness. The algorithm is ableto take into account the aforementioned performance measures, finding a set ofnon-dominated solutions representing the Pareto front. This method is based onthe integration of two different techniques: a multi-criteria decision-makingmethod and a constructive heuristic procedure developed for makespanminimization in flowshop scheduling problems. In particular, the technique fororder preference by similarity of ideal solution (TOPSIS) algorithm is integratedwith the Nawaz–Enscore–Ham (NEH) heuristic to generate a set of potentialscheduling solutions. To assess the proposed heuristic’s performance, comparisonwith the best performing multi-objective genetic local search (MOGLS) algorithmproposed in literature is carried out. The test is executed on a large number ofrandom problems characterized by different numbers of machines and jobs.The results show that the new heuristic frequently exceeds the MOGLS results interms of both non-dominated solutions, set quality and computational time.In particular, the improvement becomes more and more significant as the numberof jobs in the problem increases.