bouquet field horses horses horses

Single Machine Scheduling: Genetic Algorithm with Dominance Properties

V. Mani1, Pei-Chann Chang2, Shih Hsin Chen2
1 Department of Aerospace Engineering,
Indian Institute of Science
Bangalore, 560-012, India.
2 Department of Industrial Engineering,
Yuan Ze University
Ne-Li, Tao-Yuan, Taiwan, 32026, R.O.C

This paper considers a single machine scheduling problem with n jobs, in which each job j (j = 1, 2, ..., n) has a processing time pj and a due date dj . The objective is to minimize the sum of earliness and tardiness costs, without considering machine idle times. In other words, the objective is to find the optimal schedule for these jobs. First, we derive the dominance properties of (the conditions on) the optimal schedule based on the processing times and due dates of these jobs. Using these properties, we present an algorithm that results in a better schedule from a randomly generated initial schedule. So, we apply our algorithm to the randomly generated schedules and obtain a good starting schedules in the genetic algorithm. It is known that genetic
algorithm with a good initial solution will give better results in less computation time. The performance of genetic algorithm with good initial solutions (obtained from our algorithm) is examined on available test problems. We present the results to show that this method of obtaining starting schedules performs very well.

Related Material:

  1. Result table
  2. Instance (Francis Sourd, and Kerem Bulbul)
  3. GA Parameter settings: (Crossover Rate: 0.8, Mutation rate: 0.3, Generations: 1000, Population Size: 100.)
  4. Java source code with instances(1.404 MB) (Please refer to the OpenGA with the latest update.)