Flexibility is a key concept in the management of modern manufacturing systems.
The principal motivation is to achieve rapid response to costumer demands by
improving the efficiency of a job shop while retaining its flexibility (Blayzewicz
et al., 2007; Groover, 2007). To achieve this
goal the term Flexible Manufacturing System (FMS) is defined. Flexible manufacturing
systems have many potential advantages including high flexibility, high machine
utilization, low work-in-process inventory and is an unsupervised production
system. Scheduling is in the heart of this control system and therefore plays
a crucial role to achieve intended goals (Liu and MacCarthy,
1997; Groover, 2007). FMS combines the merits of job
shop and flow shop production systems. The high level of automation previously
reserved for mass production is now also achievable for medium-sized production
and the manufacturing flexibility enables companies to react quickly to changes
in customer demand (Jerald et al., 2006). FMS
is an integrated computer controlled complex of automated material handling
devices and Numerically Controlled (NC) machine tools that can process medium-sized
volumes of a variety of part types (Liu and MacCarthy, 1997;
Groover, 2007; Tung et al., 1999;
Noorul Haq et al., 2003). Scheduling FMS problems
are more difficult than the conventional production systems. This is because
of a number of reasons such as machine setup times, part routing and operations
scheduling. Besides, there are resources other than machines to be considered.
These resources are material handling devices, buffer storages and tool magazines.
FMS scheduling problems are proved to be NP-hard and mathematical programming
approaches need to be better suited and improved for real-world FMS scheduling
problems (Liu and MacCarthy, 1997; Sankar
et al., 2003; Kim et al., 2004).
Therefore, the success of an FMS lies in the design of an appropriate scheduling
procedure that optimizes the performance measures of such a system. As many
operational problems are directly linked to scheduling problems, the design
of appropriate scheduling mechanisms for FMS is of equal importance to the design
of FMS itself. The scheduling problems in FMS are related to the execution of
production orders and include raw part input sequencing, machine and vehicle
scheduling, monitoring system performance and taking the necessary corrective
actions (Chan and Chan, 2001).
In this study, scheduling problem in one special configuration of FMS known
as Flexible Manufacturing Cell (FMC) is considered. An FMC consists of a set
of Single Flexible Machines (SFM) and only one material handling device that
can be used when it is idle (Liu and McCarthy, 1997;
Maccarthy and Liu, 1993a, b)
and the whole system is under computer control. Moreover, different from the
earlier research study, this study focuses on both machine and AGV.
Scheduling of flexible manufacturing systems received enormous attention over
the last three decades. Three different approaches are mainly used. One approach
is mathematical programming formulation (Liu and McCarthy,
1997; Choi and Lee, 2004). Liu
and MacCarthy (1997) developed a comprehensive global MILP for the class
of FMSs known as flexible manufacturing cells, or in short, FMCs. The proposed
model considers both aspects, of a scheduling procedure, i.e., loading and sequencing
and scheduling the machines, material handling systems and storages. Three objective
functions including mean completion time, maximum completion time or makespan
and maximum tardiness are defined. Based on the model, a global heuristic procedure
is described. The results show that the optimality performance of the global
heuristic procedure is much better than loading and then sequencing approach.
The main disadvantage of this model, as is the case for large scale industrial
problems, is the time required to solve the problem as its size increases and
therefore recently developed methods must be used.
Ahluwalia and Ping (1991) proposed a distributed approach
to job scheduling in an FMS environment. It is assumed that each machine is
equipped with a general purpose computer that controls it during its processing
function. Each machine is represented as a node that is capable of communicating
with other nodes (machine tools) through its assigned computer. This system
is formulated as a linear programming model to solve the scheduling problem.
When the system malfunctions, the job rescheduling is based on a non-linear
programming model. Results show this approach frees up the main processor for
other tasks and is well suited for a large and complex manufacturing system.
Jiang and Hsiao (1994) proposed a new mathematical programming
for scheduling an FMS. In their model, operation scheduling and part routing
with alternative plans are considered. They presented two models, models A and
B, with different objectives. These objectives are absolute deviation of meeting
due dates and the minimum of total completion time, respectively.
The second approach is heuristics, dispatching rules and simulation which are
very common in practice. Sabuncuoglu and Hommertzheim (1992)
proposed a dynamic dispatching rule for on-line simultaneous scheduling of machines
and AGVs in an FMS. This dispatching rule uses various priority rules based
on the status of jobs. Using this information, decisions are made hierarchically
to identify the appropriate part and machine to be served. Mean flow time and
mean tardiness are regarded as objective functions. Simulation results indicate
that their approach outperforms existing scheduling rules for a number of experimental
Sridharan and Babu (1998) applied simulation technique
to made multi-level decisions for FMS scheduling problem. Then, the results
of this simulation model have been used for developing a meta-model which investigates
how accurate these results are. They finally concluded that these meta-models
are useful for FMS under study so as to evaluate various multi-level scheduling
decisions in FMS.
Sabuncuoglu and Karabuk (1998) presented a heuristic
algorithm based on the filtered beam search for scheduling flexible manufacturing
systems. The main assumptions considered are buffer capacity and routing and
sequence flexibility that is used in generating schedules for machines and AGVs.
The performance criteria are mean flow time, mean tardiness and makespan. To
further explore algorithm efficiency, statistical experiments were designed
which shows considerable improvements in system performance.
Chan and Chan (2001) conducted a simulation modeling
study on a flexible manufacturing system which minimizes three performance criteria
simultaneously, i.e., mean flow time, mean tardiness and mean earliness. They
used priority dispatching rules that frequently changed according to the system
status. To monitor criteria, three indices were used. These indices, then, were
ranked in descending order showing how worse the system condition is. In such
case an appropriate rule will be selected to tackle that criterion with largest
index. This mechanism is called pre-emptive. Results show that a solution (range
of frequency) can always be obtained for changing the dispatching rule, so that
the system is better than one which just uses fixed FMS scheduling rules.
The third and last approach is based on artificial intelligence techniques.
This includes meta-heuristics, neural networks, fuzzy logic and expert systems.
Ulsoy et al. (1997) proposed a GA-based approach
to schedule jobs and AGVs concurrently in an FMS. Their study is worth considering
since a new chromosome representation is used. Another aspect of this GA is
the crossover operator that is used for the first time.
Logendran and Sonthinen (1997) presented a tabu search-based
approach for the job-shop type flexible manufacturing systems. First, a mixed
integer programming is developed and then a strong heuristic algorithm based
on the concept known as tabu search is developed to tackle problems of industrial
merit. For this, they introduced six different versions of proposed algorithm.
To measure the performance of this tabu search-based heuristic, a randomized
complete block design is experimented.
Jerald et al. (2006) have considered two major
resources in FMS, i.e., machine and AGV and developed a genetic algorithm called
Adaptive Genetic Algorithm. The objective function is combined from two parts. The first part minimizes penalty cost and the second minimizes machine idle time. These two aspects, to some extent, are interconnected. In other words, if AGV is properly scheduled, then the idle time of machines can be minimized; as such, their utilizations can be maximized. The penalty cost part of the objective function minimizes not meeting committed due dates.
Noorul Haq et al. (2003) proposed a multi level
scheduling for FMS to generate realistic schedules for the efficient operation
of the FMS. Other resources than machines such as material handling device,
AS/AR and tool management is considered. To generate schedules, combined a heuristic
method, namely Giffler and Thompson (Sakawa, 2001; Baker, 1974)
is combined with GA and Simulated Annealing (SA).
Reddy and Rao (2006) developed a hybrid multi-objective
GA for scheduling machines and AGV in an FMS concurrently. Three objectives
or criteria are considered including makespan, mean flow time and man tardiness.
The proposed HGA is combined with a heuristic approach that is used to schedule
AGV. As researchers stated, this type of hybridization is capable to reduce
the size of strings and the number of constraints and as such, increase algorithm
efficiency. Initial population is randomly generated.
Kim et al. (2004) proposed a new GA called network-based
genetic algorithm for scheduling jobs in FMSs. A static environment is modeled
which in scheduling literature means that all jobs are ready or ready time is
zero. A mathematical programming with minimization makespan, total flow time
and total tardiness as objective functions is presented. Then a network-based
hybrid GA combined with a neighborhood search procedure was developed. As numerical
experiments show, this algorithm is both effective and efficient for FMS scheduling.
In many real cases there are more than one objective that should be considered
simultaneously (Sankar et al., 2003; Kim
et al., 2004; Reddy and Rao, 2006). Prabaharan
et al. (2006) considers sequencing and scheduling of jobs and tools
in a flexible manufacturing cell. To achieve this, two methodologies are used
to derive optimal solutions. The first method is commonly used is Priority Dispatching
Rules (PDRA) and the second one is Simulated Annealing Algorithm (SAA). One
aspect of their proposed algorithm is the use of Giffler and Thompson procedure
for active feasible schedule generation. The performance of these two algorithms
are compared with makespan and computational time. The analysis reveals that
the SAA based heuristic provides an optimal or near optimal solution with reasonable
Tung et al. (1999) presented a hierarchical approach
to scheduling Flexible Manufacturing Systems (FMSs) that pursues multiple performance
objectives and considers the process flexibility of incorporating alternative
process plans and resources for the required operations. In so doing, they proposed
a multi-objective priority index that simultaneously considers order tardiness
cost, inventory cost, order profit, processing time, due date and order size.
Using the just mentioned multi-objective priority index, rough-cut schedules
will be generated and evaluated for performance measure at the system level.
FLEXIBLE MANUFACTURING CELLS SCHEDULING
Here, scheduling problem in an FMC environment is described. In so doing, model assumptions and definitions are presented. Moreover, a genetic algorithm-based technique is proposed to solve the scheduling problem in a FMC. This GA differs from existing GA-based techniques in various ways. One major difference is scheduling generator phase that combines four priority dispatching rules, each of which handles one type of resources or constraints inherent in flexible manufacturing cells. In the following, first, model assumptions are presented and, then, the elements of proposed GA are fully described.
Model assumptions and definition: Here, assumptions, based on which
under-consideration problem is stated and solved, will be presented. In what
follows these assumptions are outlined:
||Processing time of each operation is known in advance. The problem is
considered in a static environment
||Transportation times between machines are based on the AGV speed and distance
between two different machines
||Loading and unloading times are negligible and can be eliminated
||Setup times in this model are sequence-dependent
||Machines and AGV breakdown are not accounted for
||All machines can process every part and related operations, only if equipped
with appropriate tools
||Tooling constraints are not considered. In other words, the considered
resources are machines, material handling device and buffers
||Each machine can process only one part at a time
||Preemption is not allowed
||Processing times are scheduling-independent but machine-dependent, i.e.,
machine eligibility is taken into account. This assumption is considered
just here for the first time
||Technological constraints are known a priory
||There are two buffers before and after each machine
||To avoid system dead lock, it is assumed that there is a central buffer
with unlimited capacity to keep in-line parts
Based on the above-mentioned assumptions, with some limitations to some extend,
Liu and MacCarthy (1997) developed a very comprehensive mathematical programming
formulation with seven sets of constraints, each showing one aspect of the flexible
In this study a GA-based technique is proposed and developed to generate an (near) optimal solution for scheduling problem. Minimizing makespan or Cmax is defined as objective function.
Genetic algorithm technique: In this part the proposed GA is outlined.
Genetic algorithms are non-deterministic stochastic search methods that utilize
the theories of evolution and natural selection to solve a problem within a
complex solution space, or more specifically combinatorial optimization problems
(Sakawa, 2001; Gen and Cheng, 2000; Gen
and Cheng, 1997). The element and mechanism of genetic algorithms are representation,
population, evaluation, selection, operator and parameter. The algorithm starts
with a randomly generated initial population consisting of sets of chromosomes
that represent the solution of the problem. These are evaluated for the fitness
function, or equivalently objective function and then selected according to
their fitness value. The elements of the proposed GA are explained hereafter.
Representation: Every solution of the problem has equivalent representation
in GA domain. To link each solution to a chromosome, a coding scheme is needed.
In this study each solution is coded as string of integer numbers (Reddy
and Rao, 2006), which is called pheno style (Sankar et
al., 2003). Care must be taken in generating feasible solution that
maintains the precedence relations of operations related to the same job. This
is crucial in job shop-based scheduling. The following example shows how this
Example: A scheduling situation with 4 work centers and 3 work pieces
is considered. There are 10 operations and the chromosomes consist of 10 genes.
Fitness function: Each individual generated is evaluated for its completion
time. The makespan, then, is the maximum of jobs completion times. Mathematically,
if completion time is defined as:
Makespan would be
Another aspect of GA is operators that play a major role in finding (near -)
optimal solution. There are three operators: reproduction or selection, crossover
and mutation (Reddy and Rao, 2006).
Crossover: The technique used here to cross over two chromosomes is
named job-based crossover which never violates precedence relations between
operations (Reddy and Rao, 2006; Gen
and Cheng, 2000; Gen and Cheng, 1997). Based on this
scheme, once two chromosomes are selected as parents, a job is randomly selected
and its corresponding operations are directly copied into respective positions
of offspring. This method guarantees that precedence relations are not violated.
Then, the remaining unfilled positions are fulfilled with operations of another
parent. The example below clarifies the above method.
Example: Chromosomes selected for crossover are P1: 1 5 8 2 6 9 3 7 10 4 and P2: 5 8 1 9 2 3 6 10 7 4.
Let the job selected be 2 and the corresponding operations of job 2 are 5,
6 and 7.
P1: 1 5 8 2 6 9 3 7 10 4
P2: 5 8 1 9 2 3 6 10 7 4
Resulting offspring are:
OS1: 5 1 8 2 9 3 6 10 7 4
OS2: 8 5 1 9 6 2 3 7 10 4
Mutation: Operation swap mutation is used. Two random positions on the
chromosome are chosen and the operations associated with these positions are
swapped. Operation swap mutation may cause infeasibilities in terms of the precedence
relations and a repair function is used to eliminate any such infeasibility
(Sankar et al., 2003; Reddy and
Repair function: A repair function is used to see that the chromosomes
do not violate the precedence constraints (Ulsoy et al.,
1997). The four-step procedure below outlines the repair function in details:
||Find positions of the operations that violate the precedence relations
||Compute the distance between violating operations
||If the distance between them is less than half the chromosome length then
swap the operations, else go to step four
||Randomly pick any one operation and insert it before or after the other
depending on the precedence
Selection: The method used here is known as roulette wheel approach
that commonly used in practice (Gen and Cheng, 2000). It
belongs to the fitness-proportional selection and can select a new population
with respect to the probability distribution based on fitness values, i.e.,
the more fitted a chromosome is, the more chance it has to be selected.
Population and parameters: The initial population is randomly generated. The number of chromosomes in each generation, crossover and mutation rates, number of generation that algorithm should run to give a satisfying solution are considered as GA parameters that must be initialized at the beginning of GA run.
Apart from GA methodology, to evaluate each string or solution it is needed to schedule jobs on different machines considering problem constraints. In so doing, four Priority Dispatching Rules (PDR) are combined. These include Earliest Completion Finishing Time (EFT), SPT, Shortest Distance Time (SDT) and Fewest Waiting Jobs for Machine (FWJM). This proposed methodology work as follows: first, a job with earliest finishing time is selected to be processed on the corresponding machine. If there is more than one job, the job with shortest processing time for its subsequent operation is selected. Then tie is broken by considering the distance each job should travel, i.e., the shortest path is selected first by AGV. If again there is a tie, another PDR is taken into account. Based on this rule, the number of jobs in the target machine buffer determines which job should go first.
This GA in conjunction with proposed heuristic approach constructs the methodology presented for scheduling jobs and AGV in a flexible manufacturing cell.
Ga steps for scheduling fmc: Here, steps for scheduling a flexible manufacturing
cell are presented.
||Enter input data including number of machines, distance between machines,
number of jobs and corresponding operations, processing and setup times
and due dates. Enter GA parameters such as population size, crossover and
mutation rates and termination criteria
||Randomly generate an initial population using the encoding scheme
||Generate schedules using schedule-generator module
||Using roulette wheel approach select chromosomes to create mating pool
for next generation
||Generate offspring population using job-based crossover and bit-wise exchange
mutation operators. If some precedence relations are violated, go to step
6; otherwise go to step 7
||In case of any violation as a mutation result, run repair function as
described above and go to step 7
||Evaluate each chromosome in current population for objective function
based on the generated schedule
||Sort chromosomes based on the fitness function value
||If termination criterion is satisfied, then stop and print the fittest
chromosome as the best solution found; otherwise go to step 4 for next generation
In this part, the proposed approach is applied to schedule FMC with varying
parameters. The proposed algorithm is coded in Visual C++ 6. Many problems with
different parameters and values were considered and solved. The results are
tabulated. Since the problem environment is somehow similar to the one considered
by Liu and MacCarthy (1997), the MILP was solved by Lingo
8 and the results were compared with those of the heuristic approach.
First, 10 problem examples were randomly generated and shown in Table 1. In each problem example, different job sets with different operations were considered. Based on the mathematical formulation number of variables and constraints are also calculated and provided in this Table 1.
To further study the efficiency of proposed model, four scenarios were defined,
based on which both mathematical model and GA methodology are applied. These
scenarios consider one parameter that may affect the results.
||Problem data for experimental study
||Results for case 1
||Results for case 2
||Result for case 3
First, an FMC with two machines is considered and iteratively problem size
is increased by adding job with varying operations. Processing times are randomly
generated from a uniform distribution function (Table 2).
Then, the configurations of FMC, in terms of distance between machines or case
2 (Table 3), buffer size or case 3 (Table 4)
and speed of AGV or case four (Table 5), were changed. GA
parameters were remained unchanged, though their impacts on algorithm performance
can be effective.
This algorithm is coded in Visual C++ 6 along with coded MILP model in Lingo 8. Both were run on a PC with 2.6 GHz CPU and the results are tabulated in the following page.
These 4 cases or scenarios for mathematical model and GA approach are depicted
in (Fig. 1, 2), respectively. Figure
1 and 2 depicts and compares four scenarios. It can be
seen from these figures that how the configuration and layout of manufacturing
cell can increase the problem complexity.
||Results for case 4
||Computational time needed to solve problem by B and B
||Computational time for GA
Results: As results show, using GA to solve this problem will reduce
time needed to get best objective function dramatically showing that using this
technique is promising. Another fact that is worth mentioning is the impact
that FMS layout has on production planning in general and scheduling in particular,
i.e., the more machines were located away, the greater the makespan is. For
this reason layout of a cell must be considered in scheduling system design.
CONCLUSION AND FURTHER RESEARCH
Flexibility is a growing issue in modern industrial firms to respond varying product demand with short lifecycle. Therefore, new approaches are needed to resolve this issue. Since FMS scheduling problems are NP-hard, using heuristic methods are quite justified. In this study a class of FMS known as flexible manufacturing cell is considered. A new GA-based approach is proposed to schedule jobs and AGV for minimizing makespan.
The algorithm is coded in Visual C++ 6 and run for problems of different sizes.
The obtained results were compared with mathematical model developed by Liu
and MacCarthy (1997). As results show, the proposed model performs better
than MILP model. One reason that is worth considering is the required time to
solve medium to large size problems that is a crucial issue in industrial firms.
There are several directions to study on for future study and some are suggested
here. One aspect of every decision problem, as in the case of scheduling problem,
is multiple objectives that must be considered simultaneously. So, it is worth
considering more than one objective as the measures of system performance. Another
way is to apply other heuristic methods separately or in conjunction with GA.
Currently researchers are working on this problem with hybrid GA as a methodology in multi-objective environment.