Single Machine
Scheduling Problem with Job Dependent Penalties:
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 , due date dj , earliness penalty
j , and
tardiness penalty j . 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
the optimal schedule should satisfy, when the penalties are job dependent. Using
these properties, we present an adjacent pair wise interchange algorithm. This
algorithm 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. This we call as genetic algorithm with
dominance properties (GADP). 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 (GADP) is examined on available test
problems. We compared the performance of GADP with simple genetic algorithm
(SGA). In SGA the initial solutions are random solutions. We present the results
to show that this method GADP performs very well.
KEY WORDS:
Single machine scheduling, earliness/tardiness, dominance properties,optimal schedule, genetic algorithms.
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.)
- Source code with instances(1.269MB)
