Minimization of Makespan in Job Shop Scheduling with Heuristic and Genetic Algorithms

Author (s):

  1. Dr. Sridhar K., Chhatrapati Shivaji Institute of Technology, Durg, Chhattisgarh, India,
  2. Raushan Kumar, Department of Mechanical Engineering, Durg, Chhattisgarh, India


As the performance of manufacturing system is directly related to the optimum utilization of time and resources, optimal scheduling of work activities plays an important role. Job shop scheduling is an optimization problem, in which a set of jobs has to be processed on a set of machines such that some specific objective functions are to be minimized. Here an effort has been made to minimize the makespan and average job flow time of the job shop scheduling problem of following two natures: 5-job 3-machine problem and 10-job 5-machine problem. Data for these problems were collected from a small scale industry. This paper describes the steps in well-known heuristics such as Palmer’s, Campbell Dudek and Smith (CDS) & Nawaz Enscore and Ham (NEH) and a simple algorithm for proposed Genetic Algorithm. This paper investigates the present scheduling system followed by the industry and presents the solutions for the problems considered through heuristics and proposed Genetic Algorithm. Then the comparisons were made among the results obtained through proposed genetic algorithm, heuristics and LEKIN scheduling software to suggest an optimal sequence for the problems considered.

No of downloads: 39