A two-stage simulated annealing procedure for block layout problems

Rules for setting simulated annealing control parameters are proposed for block layout problems where different material-handling devices are dynamically assigned to individual material movements as layout solutions are perturbed. Recognizing the high cost of computing materials-handling cost in this type of problem, the rules are based on adapting an existing two-stage simulated annealing procedure to accelerate convergence. Experimental results suggest that the application of these rules yields solution quality comparable with other single and two-stage simulated annealing algorithms but with significantly fewer re-evaluations of the objective function.     

A simulated annealing algorithm based on a closed loop layout for facility layout design in flexible manufacturing systems

Facility layout design problems in flexible manufacturing systems (FMS) differ from traditional facility design problems and are more difficult to solve because there are more constraints that must be considered (i.e., cell shape, cell orientation, pick-up and drop-off point positions). The focus of this paper is on the closed loop type layout, which is based on a predetermined layout pattern. This layout pattern is commonly found in manufacturing settings since it requires a simplified material handling system configuration and since it facilitates a modular and expandable layout structure. The open-field type layout problem, where there is no predetermined layout pattern, may potentially have a more efficient configuration, since there are fewer restrictions. However, this problem is more difficult to solve and may result in configurations that are not desirable due to the lack of structure or modularity. The procedure developed in this paper improves the efficiency of the closed loop configuration by changing the rectangular shape of the loop to different sizes. In many cases, the resulting closed loop layout proves to be as efficient as the open field layout. A simulated annealing procedure (SA-CL) is used to search for the configuration that minimizes the total material handling costs. A comparison of the results with existing methods indicates that, based on solution quality and computational time, the SA-CL offers a favourable alternative for efficient layout design.     

Optimal algorithms for row layout problems in automated manufacturing systems

In many automated manufacturing environments, particularly flowlines and flexible manufacturing systems (FMSs), machines are arranged along a straight material-handling track with a material-handling device moving jobs from one machine to another. These layouts are referred to as row machine layouts. In this paper we study the row layout problem (RLP) under the design objective of minimizing the total backtracking distance of the material-handling device, which is an NP-complete problem. We propose the use of a dynamic programming algorithm for its solution. A special case of the problem, usually encountered in flexible manufacturing cells and which can be solved with a polynomial procedure, is also discussed. For the equidistance case (i.e., successive candidate locations are in equal distances), we formulate the problem as an integer linear program. The use of standard mathematical programming codes can efficiently solve this formulation.     

A heuristic procedure for loading problems in flexible manufacturing systems

The loading problem in a flexible manufacturing system (FMS) is viewed as selecting a subset of jobs from a job pool and allocating the jobs among machines. In this paper a heuristic solution to the loading problem has been suggested by developing the concept of essentiality ratio for the objective of minimizing the system unbalance and thereby maximizing the throughput. The proposed heuristic is tested on ten problems and the results show that the algorithm developed is very reliable and efficient.     

A large-scale hybrid simulated annealing algorithm for cyclic facility layout problems

The cyclic facility layout problem (CFLP) is a special case of the dynamic facility layout problem (DFLP) in which there are several production periods and the production cycle repeats itself by going to the first period after the last one because of the seasonal nature of products. In this article, a mixed integer programming formulation is developed for the CFLP. In the DFLP literature, department shapes are assumed to be given or fixed. However, this assumption does not hold in the case of the CFLP because the facility size is limited and the area requirements of the departments change significantly throughout the planning horizon. Therefore, department dimensions and sizes are considered as decision variables in the CFLP. A large-scale hybrid simulated annealing algorithm (LS-HSA) is proposed to solve the formulated problem and shown to be effective and versatile as it can be applied to various facility layout problems.     

A mixed-integer programming formulation for the double row layout of machines in manufacturing systems

The Double Row Layout Problem (DRLP) is the problem of allocating a given set of machines on both sides of a straight line corridor so as to minimise the total cost of transporting materials among machines. The DRLP occurs in several manufacturing plants, particularly in semiconductor manufacturing. While it has a large practical importance, the problem is very difficult to solve to optimality. In this paper, we construct a mixed-integer programming (MIP) formulation of the problem, which favourably compares to a previously published MIP formulation. The new model is found to present similar performance to another published MIP formulation, and it has the advantage of being more intuitive for handling qualitative inputs that may be required in a layout refinement phase.     

A new simulated annealing algorithm for the facility layout problem

In this paper we present an application of simulated annealing to facility layout problems with single and multiple floors. The facility layout problem is highly combinatorial in nature and generally exhibits many local minima. These properties make it a suitable candidate for simulated annealing. Using a new candidate layout generation routine and spacefilling curves, we develop an improvement-type layout algorithm based on simulated annealing that considers an expanded set of department exchanges. The resulting algorithm achieves low-cost solutions that are much less dependent on the initial layout than other approaches. We compare the performance of the simulated-annealing based algorithm with both steepest-descent and randomized approaches from the literature. Unlike other simulated annealing papers which typically present a statistical experiment to evaluate the effect of numerous control settings, all the experiments presented in this paper were conducted with control settings that are constant or easily specified. This approach facilitates the application of the proposed algorithm to real-life facility layout problems in both single and multiple floor facilities. Although the algorithm presented here can be applied to many types of facilities, our primary focus is on production facilities.     

A hybrid genetic algorithm for the single row layout problem

The arrangement of machines or departments along a straight line is known as single row layout and it is a widely employed configuration in flexible manufacturing systems. In this paper, a hybrid genetic algorithm (HGA) is proposed to solve the single row layout design problem with unequal sized machines and unequal clearances. The algorithm is developed by hybridisation of a genetic algorithm with a local search operator. The proposed HGA is tested on 51 well known data sets from the literature with equal and unequal clearances, and the results are compared with the best known solutions. Finally, algorithm's effectiveness in reaching previously known best solutions is revealed and improvements up to 7% in problems with unequal clearance are obtained.     

Task assignment problems in distributed computing systems by simulated annealing

Abstract

The stochastic, heuristic search algorithm called simulated annealing is considered for the problems of static task assignment in distributed computing systems. The purposes of task assignment problems are to assign modules of programs over a set of interconnected processors in order to both maximize the utilization of processors and minimize interprocessor communication costs. This problem has been proven to be NP‐hard. Although simulated annealing has been applied to a broad class of combinatorial optimization problems, but it requires a long computation time in order to converge to the globally optimal solution. In this paper, we design a very efficient annealing schedule with good move generation strategies and use the concept of specific heat and the frozen condition to obtain near‐optimal solutions for task assignment problems with a significantly large reduction in the number of iterations.     

A methodology for designing flexible cellular manufacturing systems

Cell formation in cellular manufacturing deals with the identification of machines that can be grouped to create manufacturing cells and the identification of part families to be processed within each cell. Dynamic and random variations in part demands can negatively impact cell performance by creating unstable machine utilizations. The purpose of this paper is to introduce and illustrate an interactive cell formation method that can be used to design 'flexible' cells. Flexibility in this context refers to routing flexibility (i.e., the ability for the cellular system to process parts within multiple cells) and demand flexibility (i.e., the ability of the cell system to respond quickly to changes in part demand and part mix). Through an experimental analysis using multiple data sets, we also validate the procedure and provide guidelines for parameter settings depending upon the type of flexibility of interest to the user. Finally, trade-offs and interdependences between alternative types of flexibility in the context of cellular systems are illustrated.     

A cross-entropy approach to the single row facility layout problem

The single row facility layout problem is to arrange a given number of facilities along a straight line so as to minimise the total cost associated with the interactions between the facilities. In this paper, a metaheuristic algorithm based on the cross-entropy method, incorporating a local search procedure and symmetry-breaking techniques, is developed to solve this problem. The proposed algorithm has been tested on some widely used benchmark instances. The computational results show that the proposed algorithm has found the optimal or the best solutions known so far for the instances of size with up to 100 facilities and is competitive with some existing algorithms.     

Using queuing theory and simulated annealing to design the facility layout in an AGV-based modular manufacturing system

An automated guided vehicle-based flow production system is used for manufacturing prefabricated bathroom units. One unit can occupy a space of more than 10?m². Due to large time deviations in sequential processes, queues are formed and greater plant space is needed. Reducing work-in-progress helps to save plant space but renders manufacture less efficient. The research explores better workstation arrangements. An open queuing network (OQN) model was used to approximate the flow production system. Since the problem of workstation arrangement is a combinatorial optimisation problem, simulated annealing (SA) was applied to search for a good solution. The combination of an OQN model and SA provides a powerful tool to solve the facility layout problem for a stochastic flow production system. The experimental results show that the proposed approach has the potential to guide industrial layout design and practice.     

Genetic algorithms and simulated annealing for scheduling in agile manufacturing

In this paper, genetic algorithms and simulated annealing are applied to scheduling in agile manufacturing. The system addressed consists of a single flexible machine followed by multiple identical assembly stations, and the scheduling objective is to minimize the makespan. Both genetic algorithms and simulated annealing are investigated based on random starting solutions and based on starting solutions obtained from existing heuristics in the literature. Overall, four new algorithms are developed and their performance is compared to the existing heuristics. A 2³ factorial experiment, replicated twice, is used to compare the performance of the various approaches, and identify the significant factors that affect the frequency of resulting in the best solution and the average percentage deviation from a lower bound. The results show that both genetic algorithms and simulated annealing outperform the existing heuristics in many instances. In addition, simulated annealing outperforms genetic algorithms with a more robust performance. In some instances, existing heuristics provide comparable results to those of genetic algorithms and simulated annealing with the added advantage of being simpler. Significant factors and interactions affecting the performance of the various approaches are also investigated.     

A flexible costing system for flexible manufacturing systems using activity based costing

Flexible manufacturing systems (FMSs) are designed to integrate the flexibility of job shops and the efficiency of mass production systems. Product costing methods have to adapt to this new technological environment. On one hand, the high production overhead cost of these systems requires a special attention to overhead allocation. On the other hand, the constantly changing setup configuration and production plans require a constant recalculation of overhead allocation and an a priori estimation of the expected production cost. This paper introduces the concept of flexible costing in FMSs, and proposes a method that modifies the overhead allocation based on the results of the production plan and on the simulated performance of the process. This approach is illustrated with some numerical examples.     

A due date-based dispatching rule for flexible manufacturing systems

In the paper a new dispatching rule is proposed, which extends the CEXSPT rule for dispatching jobs in a general cell's environment, i.e., a multiple-machine cell, where each machine type is assigned to a priority value. Each job is represented as a finite sequence of operations, ordered according to the type priorities of the cell's machines they are performed by. The algebraic background of the dispatching rule is described. The dispatching rule is implemented in the GOLDEN COMMON LISP programming language for IBM PC AT and compatible computers. A computer study of the performance of the proposed dispatching rule is conducted based on a four-machine cell, and the results are reported and analysed. The conclusions obtained are that the proposed dispatching rule produces cell's makespans, better than the CEXSPT dispatching rule, because it reduces idle time on cell's machines.     

Two-level modified simulated annealing based approach for solving facility layout problem

In this paper, we are considering the quadratic assignment model (QAP) of the facility layout problem (FLP) which is known to be NP-hard. We relax the integer constraints of the QAP and solve it on a commercially available package called LINGO 8. In the optimal solution so obtained, X_ij s take real values between zero and one. We identify promising X_ij s having a value strictly greater than 0.5 in the optimal solution and set them to one. We add the constraints (X_ij ?=?1) associated with promising X_ij s into the QAP (with integer restrictions) and resolve using LINGO 8. In all the cases attempted we obtained a superior feasible solution to the QAP which was further improved by the proposed modified simulated annealing (MSA) procedure. An encouraging comparative performance of this procedure is thus reported.     

Configuring layout in unidirectional loop manufacturing systems

This paper addresses the layout configuration problem of workstations in a unidirectional loop manufacturing system. In this popular unicyclic material handling facility, the material transporters depart from the input/output station, traverse each workstation exactly once, and then return to the input/output station. We show the important properties of this unidirectional material handling loop network. Based on these characterizations, both heuristic and branch-and-bound algorithms are proposed to solve such NP-complete layout problems. Computational experiments with problem sizes up to 100 workstations are reported. Both the problem size and the material flow density have been found to affect the solution quality and the computational efficiency. The proposed methods appear efficient and effective for solving these layout problems.     

A method for scheduling in parallel manufacturing systems with flexible resources

We address the Parallel-Machine Flexible-Resource Scheduling (PMFRS) problem of simultaneously allocating flexible resources, and sequencing jobs, in cellular manufacturing systems where the cells are configured in parallel. We present a new solution methodology for the PMFRS problem called the Nested Partitions (NP) method. This method combines global sampling of the feasible region and local search heuristics. To efficiently apply the NP method we reformulate the PMFRS problem, develop a new sampling algorithm that can be used to obtain good feasible schedules, and suggest a new improvement heuristic. Numerical examples are also presented to illustrate the new method.     

Data-driven generic simulators for flexible manufacturing systems

Despite the apparent move toward using data-driven simulators in manufacturing modelling, as opposed to simulation languages and packages that require programming, there have been few rational efforts to evaluate the development and use of these tools. As the number of tools continues to grow, such evaluation is necessary if simulation users are going to make sensible informed choices. This paper presents two specialized data-driven simulators developed to model Flexible Manufacturing Systems called RENSAM (Rensselaer Simulator for Automated Manufacturing) and RENVIS (Rensselaer Visual Interactive Simulator). Experience with these packages leads to consideration of the benefits of using such tools. Advantages include the ease with which models can be developed and the rapid pace of that development, and the enforcement of proper statistics collection; disadvantages include misplaced perception of how easy the tool is to use, weaknesses in implementation and the limitations of the simulator. It is shown that where a tool is deployed in the modelling process is of paramount importance, and guidance on deployment is provided. Other guidelines for developers and users of data-driven simulators are also developed.     

Integrated analytical models for flexible manufacturing systems

Product form queueing networks (pfqn) and generalized stochastic Petri nets (gspn) have emerged as the principal performance modelling tools for flexible manufacturing systems (fms). In this paper, we present integratedpfqn-gspn models, which combine the computational efficiency ofpfqn and representational power ofgspn by employing the principle of flow-equivalence. We show thatfms that include nonproduct form characteristics such as dynamic routing and synchronization can be evaluated efficiently and accurately using the integrated models.