bouquet field horses horses horses

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

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.

Single machine scheduling, earliness/tardiness, dominance properties,optimal schedule, genetic algorithms.

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. Source code with instances(1.269MB)