M-machine SDST flow shop scheduling using modified heuristic genetic algorithm

Abstract

Bi-criteria flow shop scheduling problems with sequence dependent set up time (SDST) have seen an increasing attention of managers and researchers in recent years. A very restricted research has been reported on bi-criteria SDST flow shop scheduling problems dealing with due date related performance measures. In the present work, a modified heuristic based genetic algorithm (MHGA) has been developed for the aforesaid scheduling problem subject to the minimization of weighted sum of total weighted squared tardiness and makespan criterion. The modified heuristic algorithms, along with other available heuristics and dispatching rules in the literature have also being developed to solve the problem instances given by Taillard. A computational analysis has been made to evaluate the performance of the proposed MHGA for upto 200 jobs and 20 machines problems. Comparative analysis with the help of defined performance index known as relative percentage deviation (RPD) verifies that it is viable and effective approach when compared with others heuristic/dispatching rules based genetic algorithms for the SDST flow shop scheduling, especially for larger sized problems.

Keywords: Flow shop scheduling, Modified Heuristic Genetic algorithm (MHGA), Sequence dependent set up time, makespan,
total weighted squared tardiness.