Applying Two String Chromosomes for Solving Scheduling Problems in FMS using Genetic Algorithm

Author(s):

Mahendra Kumar Salvi , Geetanjali Institute of Technical, Studies, Udaipur; Indresh Jain, Geetanjali Institute of Technical, Studies, Udaipur; Mohmd. Zuber Khan, Geetanjali Institute of Technical, Studies, Udaipur

Keywords:

NP-hard, Scheduling, Chromosome representation, GA, Non-identical parallel machines, FMS

Abstract:

Scheduling in Flexible Manufacturing System (FMS) has been the subject of intensive academic research due to its complexity and computational effort required. The FMS scheduling problems have proved to be NP-hard problems and it is not possible to achieve optimal solution to NP-hard problems by mathematical approach in a short time horizon. The present research work is focused on the FMS scheduling problem having a non-identical parallel machine environment. The objective is to minimize the maximum completion time of jobs using Genetic Algorithm (GA). The GA is one of the most efficient algorithms that aim to converge faster and provide optimal solutions in a considerable short time span. Apart from a number of ways of chromosome representation, a new type of chromosome representation has been proposed which generates no infeasible strings; hence no local or global harmonization is required. Since there is no possibility of generating infeasible strings, a considerable amount of computational effort has been saved which helps GA to converge faster and provide optimal solutions. The suggested chromosome representation has been applied to solve non-identical parallel machine problem and the results have been compared to one of the most popular heuristic applied to solve FMS scheduling problems in real-time.

Other Details:

Manuscript Id	:	RMSCRP017
Publication Date	:	05/04/2017
Page(s)	:	60-64

Download Article