18-09-2012, 11:39 AM
A heuristic based on multi-stage programming approach for machine-loading problem in a flexible manufacturing system
A heuristic based on multi-stage.pdf (Size: 207.48 KB / Downloads: 58)
Abstract
Manufacturing industries are rapidly changing from economies of scale to economies of scope, characterized by short product life
cycles and increased product varieties. This implies a need to improve the efficiency of job shops while still maintaining their flexibility.
These objectives are achieved by Flexible manufacturing systems (FMS). The basic aim of FMS is to bring together the productivity of
flow lines and the flexibility of job shops. This duality of objectives makes the management of an FMS complex. In this article, the
loading problem in random type FMS, which is viewed as selecting a subset of jobs from the job pool and allocating them among
available machines, is considered. A heuristic based on multi-stage programming approach is proposed to solve this problem. The
objective considered is to minimize the system unbalance while satisfying the technological constraints such as availability of machining
time and tool slots. The performance of the proposed heuristic is tested on 10 sample problems available in FMS literature and compared
with existing solution methods. It has been found that the proposed heuristic gives good results.
Introduction
A flexible manufacturing system (FMS) can be defined as
an integrated computer-controlled configuration of numerical
control (NC) machine tools, other auxiliary production
equipment, and a material handling system (MHS)
designed to simultaneously manufacture a low to medium
volumes of a wide variety of high quality products at low
cost [1].
FMS is a production system based on economies of
scope wherein several part types are simultaneously
resident in the system. The subsystems are versatile
computer-controlled equipment such as NC machines,
automated guided vehicles (AGV), coordinate measuring
machines and robots. The setup times are small and the
number of buffer spaces provided in the system is minimal.
Mathematical programming approaches
The first mathematical formulation for FMS-loading
problem was given by stecke [3]. The grouping and
loading were formulated as non-linear 0–1 mixed integer
programs. Solution methodologies with several
computational simplifications had been developed. These
formulations assumed that a product-mix problem
was already solved and therefore limit the models to be
suitable only for dedicated FMS [14]. O’Grady and
Menon [5] employed a goal programming model for
loading a real-life FMS. Berrada and Stecke [6] developed
a branch-and-bound algorithm for balancing workloads on
machines. Guerrero et al. [7] developed mixed-integer
linear program considering alternative routes for each part
type. Also, the optimal number of copies of each tool type
to be loaded into each tool magazine was directly
determined.
Problem description
The FMS under consideration in this paper consists of a
number of multi-functional CNC machines, tools with the
potential to execute several operations, automated material
handling devices and other amenities, where several types
of jobs arrive with varied processing requirements. Jobs are
available in batches and some of them are to be selected for
processing during a given planning horizon. Job selection
and loading constitute two major components of a tactical
planning problem of any FMS. The job selection problems
are concerned with selecting the sets of jobs to be produced
during the upcoming planning horizon while the
loading problems involve allocation of operations and
required tools for the selected jobs on the machines [11].
The complexity of these problems depends on whether
the FMS is of a dedicated type or a random type. A
dedicated type system is designed to produce a rather
small family of similar parts with a known and limited
variety of processing requirements, while in a random-type
system a large family of parts having a wide range of
characteristics with random elements is produced and the
product mix is not completely defined at the time of
installing the system [10].
Computational testing
The proposed heuristic is tested on the benchmark
problems available in literature [14]. In literature, there are
some variations in the calculation of system unbalance.
Shanker and Srinivasulu [10] considered only unutilized
machine time and Mukhopadhyay et al. [14] considered
unutilized and over-utilized machine time in calculating of
system unbalance. In proposed heuristic (say heuristic 1),
we calculated system unbalance as is done in [14], the
solutions for the 10 problems are given in Table 4 and the
comparative results are given in Table 5.
Conclusions
The main contribution of this research is to develop an
efficient heuristic based on multi-stage programming
approach for solving machine-loading problem of random
FMS. Most of the previous studies generate job sequence
based on either predetermined sequencing rules such as
shortest processing time (SPT) rule or employing metaheuristics
such as simulated annealing (SA), Genetic
algorithm (GA) etc. and operation allocation problem is
considered next. In this research, an attempt has been made
to treat job sequencing and operation allocation problem
concurrently.