Parallel Genetic Algorithm for a Multiobjective Rescheduling Problem

H. Iima (Japan)


Optimization and Scheduling, Genetic Algorithms, Multi objective Optimization, Flexible Job Shop Problem.


This paper deals with a multiobjective rescheduling prob lem in a flexible job shop for alteration of due date. The objectives of this problem are to minimize both the total tardiness and a difference from the schedule worked out for the problem before the alteration. A parallel genetic al gorithm with two subpopulations is proposed for obtaining the Pareto optimal solutions of this problem. Particularly, an individual description is proposed in this algorithm for generating solutions with a smaller difference of schedule. The genotype in this individual description is expressed by sequencing job numbers. In the decoding procedure, the schedule of each job is determined by referring the sched ule before the alteration. Moreover, this paper presents a selection operation so that the subpopulations can search different areas of solution space. In this selection opera tion for one subpopulation, we select solutions which are different from a non-dominated solution found by the other subpopulation. It is confirmed from the computational re sult that the proposed method is effective.

Important Links:

Go Back