ST-13-008
A local Guided Optimization Algorithm for Multi-objective
Reentrant Production Line Scheduling Problems
Xin Wei
∗
(Graduate School of Information, Production and Systems, Waseda University)
Song Gao (Graduate School of Information, Production and Systems, Waseda University)
Shigeru Fujimura (Graduate School of Information, Production and Systems, Waseda University)
Abstract
This paper presents a multi-objective optimization algorithm for solving the scheduling problem in reentrant produc-
tion line. Semiconductor device and liquid crystal display (LCD) fabrication process on reentrant production line, in
which a similar sequence of processing step is repeated several times. A real world reentrant production line scheduling
problem has been investigated in this paper. Based on the probability m odels, a local guided optimization algorithm is
proposed for this problem. The experimental results have demonstrated th e efficiency of proposed algorithm.
Key words: Multi-objective optimization, Reentrant production line, Penalty Cost, Makespan, Genetic algorithm.
1. Introduction
Recently, the scheduling prod uction problem of manu-
facturing systems attracts the academic and industrial re-
searchers. This scheduling problem occurs in different types
of workshop, such as job sh op, flow shop, open shop and
etc
(1)
. The job shop and flow shop are two typical scheduling
problems. In job shops, jobs may be processed with random
routes on all stages, and each route having a low process-
ing time to complete all jobs. I n flow shops, the processing
routes of all jobs are fixed and acyclic, as in assembly lines.
More recently, with the advent of semiconductor manufac-
turing plants, thin film p roduction and liquid crystal display
manufacturing line, this production system needs to be ex-
panded to consider another class of systems, which we call
“reentrant production lines”
(2)
.
In semiconductor industry, such as film transistor, liquid
crystal display (LCD) manufacturing and etc., the reentrant
operations visit in some stages or machines many t imes for
completing one job. For example, to product a liquid crystal
display, the glass may undergo some processes several times
during LCD process if multiple layers are required for the fi-
nal product. We call this new kind of manufacturing shop as
reentrant flow shop ( RFS)
(3)
, which is defined as th at a set
of n jobs need to be processed on m machines following the
same route and every job must be processed on certain stages
more than once. In t he practical reentrant production line,
in order to reduce works in process and cycle time, usually
some parallel machines are put in the same stage. This pa-
per has studied on actual production cases of semiconductor
factory, in which the procedure final testing of semiconduc-
tor products is mainly concerned. The semiconductor final
testing is the last procedure of semiconductor production,
which is responsible for the function detection, final assem-
bly and package work before the semiconductor products
are shipped out to customers. Semiconductor Final Test-
ing Problem (SFTSP) case includes almost all the flow shop
factors as reentry characteristic, serial and batch processing
stages, job-clusters and parallel machines. There are some
researchers using genetic algorithm (GA)
(4)
, tabu search
(5)
and quantum evolutionary algorithm
(6)
to solve the reen-
trant flow shop with the objective of minimizing makespan
(the time interval required to complete all the jobs). How-
ever, the requ irement of this factory is to simultaneously
reduce the makespan and penalty cost of delay jobs, and
to face the current high competition. The scheduling prob-
lem of this factory has been considered as a multi-objective
reentrant flow shop problem.
The non-dominated sorting genetic algorithm II (NSGA-
II)
(7)
is a recently developed multi-objective optimization
approach. It has been applied to solve the various multi-
objective problems. To improve of performance of NSGA-II
for solving this multi-objective SFTSP, this paper has pro-
posed a local guided probability model in form NSGA-II.
The new approach has been called as NSGA-II- LG (N SGA-
II with local guided). NSGA-II has used a sequence of jobs
to represent a solution. The jobs position in one solution has
strongly effect the solution quality which has short makespan
and low penalty cost. However, in the form NSGA-II, the
mutation and crossover has applied the random way s to find
the optimal solutions. To improve the efficiency of NSGA-II,
the probability model has been used to control the search di-
rection for finding optimal solutions. The probability mod el
records the movement of jobs, forwardly or backwardly. On
the other hand, it also guides the search direction to pre-
vent many negative movements. The ex periment results also
have demonstrated the effectiveness and faster convergence
of NSGA-II-LG for this problem.
The organization of this paper likes as follows. Section 2
describes the problem statements and exhibits mathematical
models for objectives of minimizing makespan and penalty
cost. The topic of section 3 is our proposed approach. In
section 4, computational experiments are presented, and the
results are illustrated for comparing with the former ap-
1/6