Modelling the machine loading problem of FMSs and its solution using a tabu-search-based heuristic	August 13 2012
In this Paper, the FMS loading problem is discussed with the bi-criterion objective to minimize the system unbalance and throughput by the use of tabu-search heuristic. Manufacturing technology focuses primarily on flexibility and productivity. With the product variety and product life being the characterizing standards it is important that flexibility of the job shop is maintained as its efficiency is increased. in the presence of available machine time and tool slots as constraints The complexity of basic Machine Loading Problem in FMS is very high due to the different flexibility criteria as part selection, Operation allocation and various constraint involved on availability of tool slot and time on machine. In this paper, initially 2 heuristic  are used. In heuristic 1,sequece is generated using fixed part sequencing rule and then  in heuristic 2,Tabu search methodology is used to perturb the sequence obtained from previous heuristic The proposed methodology has been tested on ten problems representing three types of FMSs: small, medium and large		Shivangi-93 International Journal of  Computer Integrated manufacturing 2005 Author U. M. B. S. Sarma, Suman Kant, Rahul Rai & M. K Tiwari

Explaining Flexible manufacturing System.

      A flexible manufacturing system (FMS) is an integrated computer-controlled configuration which consists of numerical control (NC) machine tools, auxiliary production equipment and a material handling system (MHS).It is designed to simultaneously manufacture a low to medium volumes of a wide variety of high quality products at low cost.

objectives

The objectives of FMS mainly includes in achieving efficiency in a balanced automated high volume mass production and in low volume job-shop production .  It  developes a method of grouping part operations and tools on the principle of conjoint measurement and solved the machine loading problem by minimizing the maximum difference between machine utilization called system over utilization time. These features permit economic production of a large variety of parts in low volumes. . A supervisory computer is used to control the whole system.

Design problem

 There are two types of decision problems associated with FMSs: Design problems (selection of machines, robot layout decisions, AGVs, path selection etc) and Operational problems (part type selection, resource grouping, production ratio determination, allocation of resources and loading)

.

                                      Heuristic

It  refers to experience-based techniques for problem solving, learning, and discovery. Where an exhaustive search is impractical, heuristic methods are used to speed up the process of finding a satisfactory solution. Examples of this method include using a rule of thumb, an educated guess, an intuitive judgment, or common sense.

                               Tabu Search Heuristic

      It  is a local search method used for mathematical optimization.

Local searches take a potential solution to a problem and check its immediate neighbors (that is, solutions that are similar except for one or two minor details) in the hope of finding an improved solution

The tabu-search-based heuristic is regarded as a ‘higher level’ iterative improvement/procedure that is

used for solving various computationally complex problems. Many successful implementations of tabu

search, for obtaining optimal or near optimal solution of problems pertaining to process planning, scheduling, set partitioning and loading etc, It begins with an initial feasible solution and attempts to find a better solution by investigation among a large pool of neighbourhood solutions. This method is characterized by its inherent simplicity, high adaptability, a short term memory process via a tabu

list, to escape local optima and avoid cycling. The process also allows backtracking to previous solutions,

which may lead to a better solution, known as aspiration. These features of a tabu list and aspiration

make tabu search a powerful optimization tool for solving the machine loading problem

Problem Description

FMS in which six part types are to be processed on four machines, each having three tool slots and different processing times for every operation. Each part type consists of two operations, which can be performed, on any of the machines without altering the sequence of operations. The adaptability of each machine to perform many different operations allows several operation assignment possibilities generating alternative part routes.

Thus, there can be a fairly large number of combinations in which operations of the part type can be assigned on the different machines while satisfying all the technological and capacity constraints. Further consideration of flexibilities such as: tooling flexibilities, part movement flexibilities, etc., along with the constraints of the system configuration and operational feasibility make the problem even more complex.

These operation–machines allocation combinations are evaluated using two common performance measures: system unbalance and throughput. System unbalance is the sum of unutilized or over-utilized time on all machines available in the system. Maximization of machine utilization is identical to minimization of system unbalance, whereas _throughput_ refers to the units of part types produced.

    Problem Statement

Developmemt of Objective Function

Objective functions used here are the minimization of system unbalance and the maximization of throughput for the following reasons:

(1) Minimization of system idle time leads to higher machine utilization,

(2) One of the most important goals of any loading policy is enhancing total system output, which is the same as throughput,

(3)  throughput maximization by balancing the workloads on the machine often results in limiting the tardiness

Mathematically

The first objective function is to minimize the system unbalance equivalently, and to maximize

the system utilization. 

The second objective function is to maximize the throughput or, equivalently, to maximize the

system efficiency.

overall objective function is to maximize F

   Constraints

System Unbalance

System unbalance. The system unbalance deals with the ideal time remained on machines after allocation of all feasible part types: the constraint can be expressed as XM

Tool Slot Constraint

The tool slots constraint ensures that the number of slots required to perform the operations of the part types on a machine should always be less than or equal to the tool slots capacity of that machine.

The constraint can be expressed as

Solving Approaches to the Loading Problem.

Machine-loading problem can be addressed mainly by four approaches:

a) Heuristic oriented methods.

b) Optimization-based methods or Mathematical programming approaches.

c) Multi-criteria decision-making approaches.

d) Simulation based approaches.

a) Mathematical programming approaches

In this Paper, they  have applied Heuristic oriented methods

Initial feasible solution. The initial feasible solution is obtained from heuristic 1. In this research, the ‘shortest processing time’ (SPT) based part sequencing rule has initially been considered to resolve the part ordering/part input sequencing problems. SPT as a dispatching rule

for part types performs better on average for the loading problem of a random FMS as far as the objective of balancing the workload is concerned. The SPT as a part sequencing rule attempts to maximize the throughput in comparison to LIFO, FIFO, LPT etc. In light of the above facts, the initial part sequencing is

here considered according to the SPT sequencing rule.

 Generation of neighbourhood. Generation of neighbourhood is carried out by the following steps.

Step 1. For a given part sequence enlist the number of unassigned part types.

Step 2. Interchange the unassigned part types among the assigned types in the given sequence only.

This procedure is illustrated with an example.

Let us assume that S is a feasible part sequence, and

UA is a set of unassigned part types.

Consider a problem having seven jobs. Say, for a specific case, with a given number of operations and

other details, the part sequence and unassigned part types are

S={6,1,4,7,3,5,2}

UA={2,5}

Tabu list size. The size of tabu list assumed in this article is three. A lower value of tabu list size will

result in insufficient memory for matching of the current best candidate solution with those of previous

iterations. A higher tabu list size did not improve the quality of the result, hence the tabu list size of three. In the beginning, the tabu list is a null set, which means that the tabu list does not have any sequence.

Methodology of Tabu search heuristic

Replacing assigned Part with Unassigned Part

Tabu list = {f,f,f}
S_b= S_C= S_O= {6,1,4,7,3,5,2}  F_b= F_C= F_O= 0.7250

Iterating in similar manner 4 times

Objective function value 0.7835

Finding from the study

The proposed tabu search-based heuristic solution methodology is characterized by it inherent simplicity and high adaptability and short-term memory process. While performing the computational experiments with the proposed tabu-search-based heuristic, the following parameters were chosen to solve :size of tabu list = 3, maximum iteration = 4 and perturbation policy, in which ‘each assigned part is replaced by an unassigned in one in a sequential manner’ is adopted to generate the neighborhood solution.

The proposed heuristic attempts to optimize an objective function, which is a combination of system unbalance and throughput   Where as  in  majority of earlier researchers treated system unbalance and throughput separately as their objective functions