An Efficient Genetic Algorithm for Minimizing the Makespan in a Scheduling Problem

In the current industrial context, the optimization of operations such as transportation has found a significant place in the manufacturing systems. Scheduling is a crucial, yet extremely complex process in any industry. A large number of varied factors that must be considered when creating a schedule. Flow-shop scheduling is an optimization problem and is a variant of optimal job scheduling. In this paper, we investigate a two stage flow shop problem to minimize the maximum completion time (makespan). The motivation to study a two-stage flow shop problem with dedicated machines and transportation times arises from its practical significance in real-life industrial settings. The problem consists of one common machine at the first stage and two dedicated machines at the second stage. First, all the jobs are treated on the common machine at the first stage. Then jobs are transported by a robot with unit capacity, to be executed on the second stage. Depending on the job type, each job is executed on a dedicated machine at the second stage. Since the genetic algorithm is very effective at finding optimal solutions to a wide variety of problems in the literature, we propose an efficient genetic algorithm to solve this NP-Hard problem. We propose several lower bounds for the makespan to evaluate the performance of the genetic algorithm. An experimental study is conducted to evaluate the efficiency of our proposed genetic algorithm. The computational results show that small difference between lower bound and the makespan obtained by GA algorithm. This reveals that results are close to the optimal solution and that GA algorithm can find near-optimal solution in a short CPU time.