Page 225 - Mechatronics for Safety, Security and Dependability in a New Era

Ch43-I044963.fm Page 209 Tuesday, August 1, 2006 3:58 PM
3:58 PM
Tuesday, August
Page 209
1, 2006
Ch43-I044963.fm
209
209
REACTIVE SCHEDULING METHOD FOR TARDINESS MINIMIZATION PROBLEMS
Tardiness minimization problems
In this paper, the main concern is total tardiness, which is a criterion based on job due dates, and is
defined by Eqn. 1.

£max(0,C,. -d t) (1)
i=\

Where Q and d t are the completion time and the due date of the job J t respectively, and n is the total
number of the jobs under consideration.
The reactive scheduling process using GA is a time-consuming process in order to generate a good
solution. However, the reactive scheduling modifies the schedule in parallel to the production activity,
therefore, it is required to find a good solution in the limited time. An advanced crossover method is
discussed in the followings, in order to modify and improve the schedule in a short time.

Advanced crossover method
Each gene in an individual of the proposed GA method corresponds to a manufacturing operation to be
executed in the manufacturing system, and the list of the genes in the individual represents the
priorities for the execution of manufacturing operations in the production schedule. The lower bound
of the tardiness is estimated for the _y-th gene of the individual, by applying Eqn. 2.

dd, (2)

where,
LTy. lower bound of tardiness for the >"-th gene, which corresponds to the h-th operation of job Jj.
ft,: finishing time of the h-th operation of job </,.
pt f^ (s=h+\, ...,«): processing time of remaining operations of job Jj.
dd (. due-date of job J,-.

If the LT y is more than zero, it is impossible for job J t to finish the remaining operations by its due
date.

Two parent individuals and their crossover points are randomly selected in the first step of the
crossover operation. After that, only the genes having positive number of LT y between two crossover
points are exchanged with the genes of another parent individual, by the newly proposed crossover
method. The other genes of the parent individuals are survived to the offspring individuals, as shown
in Figure 2.

Reactive scheduling process
The reactive scheduling process is carried out by the following steps.

STEP1 Initialization
The present time T x (x 1,2,...) is set up. Computation time dt is estimated. It is the time for creating
=
the modified production schedules through STEP2 to STEP4.