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
Abstract:
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:
- Result table
- Instance (Francis Sourd, and Kerem Bulbul)
- GA Parameter settings: (Crossover Rate: 0.8, Mutation rate: 0.3, Generations: 1000, Population Size: 100.)
- Java source code with instances(1.404 MB) (Please refer to the OpenGA with the latest update.)
