Comparisons of bi-objective genetic algorithms for hybrid flowshop scheduling with sequence-dependent setup times

Abstract

This paper addresses the scheduling problems in a hybrid flowshop with two objectives of minimising the makespan and total tardiness. Since this problem is NP-hard, evolutionary algorithms based on the genetic algorithm (GA) namely; BOGAW, BOGAC, BOGAT, and BOGAS are proposed for searching the Pareto-optimal frontier. In these algorithms, we propose to generate a section of solutions for the next generation using a neighbourhood search structure on the best individual in each generation. The selection procedure selects the best chromosome based on an evaluation mechanism used in the algorithm (i.e., weighted sum, crowding distance, TOPSIS and single-objective). The aim of this paper is to clarify that the cited characteristic is efficient and it enhances the efficiency of algorithms. Therefore, we perform a comparison between the proposed algorithms to find the best alternative. Data envelopment analysis is used to evaluate the performance of approximation methods. The obtained result from the comparison shows that, BOGAC is the more efficient. To continue, since the efficiency of our idea is not clear, we compare our efficient algorithm with other efficient algorithms in the literature (namely PGA-ALS and MOGLS). The final persuasive results support the idea that BOGAC in comparison with PGA-ALS and MOGLS is more effective and efficient.

Keywords:

• bi-objective hybrid flowshop scheduling
• crowding distance
• genetic algorithm
• TOPSIS
• weighted sum