International Journal of Innovative
Computing, Information and Control
Volume 4, Number 3, March 2008c
ICIC International °2008
ISSN 1349-4198
pp. 559—575

DISTRIBUTED OPTIMIZATION METHOD FOR SIMULTANEOUS
PRODUCTION SCHEDULING AND TRANSPORTATION ROUTINGIN SEMICONDUCTOR FABRICATION BAYS
Takahiro Furusho1 , Tatsushi Nishi2 and Masami Konishi1
1

The Graduate School of Natural Science and Technology
Okayama University
3-1-1 Tsushima-naka, Okayama 700-8530, Japan{ furusho; konishi }@cntr.elec.okayama-u.ac.jp
2Graduate School of Engineering ScienceOsaka University
1-3 Machikaneyama, Toyonaka city, Osaka 560-8531, Japan(Corresponding author) nishi@sys.es.osaka-u.ac.jp

Received December 2006; revised May 2007
Abstract. In this study, we propose a decentralized optimization method for production
scheduling, transportation routing for AGVs and motion planning for material handlingrobots simultaneously. The system consists of a process agent that creates production
schedule, AGV agents to generate collision-free routing for multiple AGVs, and a handling agent that determines motion planning for material handling system. Each agent
repeats the information exchange and replanning until a feasible solution is derived. The
eﬀectiveness of the proposed method is confirmed by comparing the results of the proposed
method and those of the conventional method. Experimental study demonstrates the feasibility of the proposed method.
Keywords: FMS, Scheduling, Simultaneous optimization, Automated guided vehicle,Transportation, Experimental study

1. Introduction. For semiconductor industry, simultaneous optimization for schedulingand transportation is desired to ensure eﬃcient manufacturing operations to reduce production and transportation costs in automated manufacturing systems with increasing
highly intensified competition among worldwide production. It is necessary to improve
production systems through reducing waiting time and increasing machine utilization.
One of the predominant characteristics for semiconductor manufacturing systems is thatthe production system includes repetitive production process, AGVs transportation systems and several material handling systems transporting products between production
machines and AGV systems which can be seen in flexible manufacturing systems (FMS).
Scheduling methods for FMS and transportation routing for automated guided vehicle (AGV) have been widely studied in previous FMS scheduling literature. Simulation
based methods for scheduling a jobshop type FMS is studied by Tunali [1], mixed integer programming problem formulation with a heuristic procedure is proposed by Liu andMacCathy [2]. Petri-net based simulation for reentrant systems is studied by Odrey etal. [3]. One common approach for scheduling reentrant manufacturing systems is dispatching rule [4]. However, it is diﬃcult to obtain near optimal solution by the dispatchingheuristics. For AGV routing problems, genetic algorithm (GA) [5] or a distributed routeplanning method has been proposed by Nishi et al. [6]. The method can derive the routing
to minimize total transportation time for AGVs by repeating the generation of routing
for each AGV and data exchanging between the routing for each AGV.
559