An integrated approach for the concurrent determination of the block layout and the input and output point locations based on the contour distance

This paper presents an integrated approach for the facilities design problem. It develops a method for the concurrent determination of the block layout, the locations of departmental input and output (I/O) points using the contour distances between the I/O points, and the material flow paths between the I/O points. The topology of block layouts is represented using two linear sequences (sequence-pair), which allows the layout to have either a slicing or a non-slicing structure. The block layout is obtained from the sequence-pair with a linear programming formulation. Three heuristic methods are then presented to determine for a given block layout the locations of the I/O points on the perimeters of the departments. The flow paths from output to input points are found by determining the shortest paths that follow the perimeters of the departments. The linear programming algorithm, the shortest path algorithm, and the I/O point location heuristics are embedded into a simulated annealing algorithm that modifies the sequence-pair to obtain a high-quality layout based on the contour distances between the I/O points. Results of computational experiments show that the performance of this integrated algorithm compares favourably with those of algorithms using a sequential approach and is capable of solving industrial-sized problems in acceptable computation time.     

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.     

Generalisation of unidirectional loop layout problem and solution by a genetic algorithm

Unidirectional loop layouts (ULLs) are the preferred layouts in manufacturing systems owing to their relative low investment costs, high material handling elasticity and routing flexibility. Existing formulations of the unidirectional loop layout problem are concentrated on the arrangement of workstations under the assumption that the number and location of loading and unloading stations are known. In this study, the unidirectional loop layout problem is generalised by consideration of potentially attachable loading/unloading equipment to each workstation and releasing of the predetermined number of loading and unloading stations. Thus, more efficient and effective loop layout designs are allowed by eliminating some artificial restrictions. The present ULL model is generalised and a genetic algorithm is developed to solve the problem. Solutions obtained by the genetic algorithm outperformed those obtained by conventional methods. Additionally, comparisons of the generalised model with existing models on randomly generated test problems yielded encouraging results.     

Tabu search based heuristics for multi-floor facility layout

A pair of two-stage heuristics, GRASP/TS and FAF/TS, for solving the multifloor facility layout problem are given. In both heuristics, the objective of the first stage is to obtain a layout with minimal inter-floor flow. Tabu search is used in the second stage to refine the initial layout based on total inter/intra-floor costs. GRASP/TS applies a GRASP to obtain the initial layout. FAF/TS uses an exact procedure FAF from the open literature to obtain an initial layout with minimal inter-floor flow. Computational tests indicate that GRASP/TS compares favourably with other heuristics that do not rely on exact algorithms. FAF/TS is shown to outperform all other heuristics in the open literature.     

The generalised machine layout problem

The Generalised MAchine Layout Problem (GMALP) is a generalisation of the integrated machine and layout problem, which is an extension of the machine layout problem. More specifically, the GMALP is the designing of a facility layout by defining the product mix, selecting the number of machines to be used, assigning these machines to the plant floor, and assigning products to machines such that total profit is maximised. Moreover, the GMALP integrates the quadratic assignment problem with a multicommodity flow problem. Therefore, the GMALP is a computationally intractable problem. Consequently, a mixed-integer nonlinear programming model was developed and used to solve small problem instances. Also, two simple construction algorithms and a tabu search (TS) heuristic were developed for solving large GMALP instances in acceptable computation times. In addition, a test dataset was used to evaluate the performances of the TS heuristic using the different construction algorithms. The results show that the TS heuristic perform slightly better with the second construction algorithm.     

A framework for the selection of idle vehicle home locations in an automated guided vehicle system

In the study of automated guided vehicles systems (AGVS), one assumption often made in the management of vehicles is the existence of either home locations or a circulatory loop to buffer or hold idle vehicles. A review of AGVS literature reveals that different researchers pursue one idle vehicle management policy or the other. In some studies, idle vehicles are assumed to circulate in some loops in the system while others assume they are routed to some dwell point locations where they are held until they are reassigned. When the dwell point option is implemented, different strategies for implementation are also available. However, what is generally lacking in references to dwell point strategies are the techniques for selecting the optimal or best dwell points for a given facility. In this study, the problem of dwell point or home location specification is addressed. The problem was modelled mathematically to determine the optimal home locations. The emphasis in the paper is on a unidirectional AGVS guide path. The criterion of optimization employed is the minimization of the system response time to vehicle demand points when dispatched from home locations. Solution methodologies are presented and example problems solved to illustrate the applications of the models presented.     

A new approach for loop machine layout problem integrating proximity constraints

This paper focuses on the machine arrangement problem on common loop network in a flexible manufacturing system. Existing studies aim to place machines at pre-fixed positions around a loop network. This problem is considered as a permutation problem that aims to find the best combination to reduce generated costs. In this work, we try to add more complexity to this problem by respecting the proximity constraints, defined by the experts, between the machines. To do this, we propose an algorithm based on direct distance measure. Logically, proximity constraints are checked using direct distances but costs are calculated using travelled distances. Throughout this study, we seek the best machine layout in four transport system configuration types to minimise the sum of flow time distances. Comparing our algorithm results with two hybrid genetic algorithms, the empirical results show that the proposed algorithm provides the most suitable solutions.     

Guide path design and location of load pick-up/drop-off points for an automated guided vehicle system

The guide path layout for an automated guided vehicle system (AGVS) is a critical component in the overall design of a flexible manufacturing system (FMS) that utilizes AGVs for materials handling. Not only does it affect the total distance travelled by the vehicles but it also affects vehicle requirements and space utilization. In this study, the problem of selecting the guide path as well as the location of pick-up and drop-off points for outward and inward bound parts to departments is addressed. The problem is modelled and solved as a linear integer program with the objective of minimizing the total distance travelled.     

Experiences with applying a genetic algorithm to determine an information systems architecture

While determining information systems architectures (ISA), business systems planning (BSP) is a well-known method to join processes and data classes to subsystems. BSP matrices have generally been rearranged without describing the underlying methods. Meanwhile, various techniques have been developed for solving the ISA problem. Since exact optimization methods often fail to provide results for large ISA problems, different heuristics have been applied. A new heuristic for solving the ISA problem is the application of genetic algorithms (GA). This paper examines the application of a simple GA to the ISA problem and compares the results of applying the GA with those obtained by exact methods.     

Scheduling operations of a rail crane and container deliveries between rail and port terminals

This article addresses the problem of scheduling container transfer operations in rail terminals. The overall problem can be divided into three smaller problems: constructing a dual-cycle delivery task by matching inbound and outbound containers; determining parking positions for trucks; and sequencing the delivery tasks for transfer by the rail crane. This article provides a mathematical model to obtain the optimal solutions to these problems, and suggests genetic and heuristic algorithms to reduce computational time when solving larger problems. Numerical experiments are conducted to validate the performance of the suggested heuristic algorithms.     

A machine-to-loop assignment and layout design methodology for tandem AGV systems with multiple-load vehicles

In this paper, we propose a design methodology for tandem Automated Guided Vehicle (AGV) systems with multiple-load vehicles. Our goal is to devise a design methodology that can achieve the following objectives in multiple-load tandem AGV designs. The first objective is to achieve the workload-balance between vehicles of different loops. The second objective is to minimize the inter-loop flow. The final objective is to minimize the flow distance. To achieve these objectives, the following problems are studied. First, we conduct simulations to study the relationship between a vehicle's load-carrying capacity and work capacity. This relationship is then considered in the second problem, i.e. the problem of determining the machine content of each loop. A two-stage machine-to-loop assignment method is proposed for solving this problem. At the first stage, an initial machine-to-loop assignment is generated. This initial assignment is then improved at the second stage using Simulated Annealing (SA). The third problem is the problem of determining the layout of machines in each loop. A flow-line design method and SA are adopted for solving this problem. The fourth problem is the layout problem of guide-path loops. To solve this problem, a famous layout method found in the literature is adopted. The last problem includes the problem of determining the best orientation of each loop and the problem of finding the best places to set up transfer stations between adjacent loops. A mathematical programming model that can solve them simultaneously is proposed. Simulations are then conducted to verify the design, and to show that the proposed design methodology is indeed capable of producing good and satisfactory tandem AGV designs with multiple-load AGVs. Finally, it is our hope that the knowledge learned from this study can help us have a better understanding of multiple-load AGV systems and allow us to have successful implementations of similar systems in practice.     

AGVS循环死锁搜索算法的改进设计及其实现

为了解决国内AGVS在循环死锁搜索算法研究中存在的搜索循环死锁类型不全的问题,利用任务\|资源图(task-resource graph,T-R图)提出一个改进算法。改进算法如下：首先,根据AGV的相对位置变化和执行任务的情况,利用T-R图对AGVS进行建模,然后根据循环死锁的T-R图特征,在每一个状态时刻下,使用图的强连通分支理论搜索循环死锁。当访问完所有状态时刻下的T-R图,也就找到了AGVS中的所有循环死锁。算例验证与理论分析均说明改进算法可以搜索到全部类型的循环死锁,解决了原算法存在的不足。根据改进算法开发的控制规则,可以有效避免新循环死锁的产生。同时指出,对改进算法稍加修改,可以找到AGVS中所有的循环死锁和非循环死锁。     

Research on Vehicle Routing Problem with Soft Time Windows Based on Hybrid Tabu Search and Scatter Search Algorithm

With the expansion of the application scope of social computing problems, many path problems in real life have evolved from pure path optimization problems to social computing problems that take into account various social attributes, cultures, and the emotional needs of customers. The actual soft time window vehicle routing problem, speeding up the response of customer needs, improving distribution efficiency, and reducing operating costs is the focus of current social computing problems. Therefore, designing fast and effective algorithms to solve this problem has certain theoretical and practical significance. In this paper, considering the time delay problem of customer demand, the compensation problem is given, and the mathematical model of vehicle path problem with soft time window is given. This paper proposes a hybrid tabu search (TS) & scatter search (SS) algorithm for vehicle routing problem with soft time windows (VRPSTW), which mainly embeds the TS dynamic tabu mechanism into the SS algorithm framework. TS uses the scattering of SS to avoid the dependence on the quality of the initial solution, and SS uses the climbing ability of TS improves the ability of optimizing, so that the quality of search for the optimal solution can be significantly improved. The hybrid algorithm is still based on the basic framework of SS. In particular, TS is mainly used for solution improvement and combination to generate new solutions. In the solution process, both the quality and the dispersion of the solution are considered. A simulation experiments verify the influence of the number of vehicles and maximum value of tabu length on solution, parameters’ control over the degree of convergence, and the influence of the number of diverse solutions on algorithm performance. Based on the determined parameters, simulation experiment is carried out in this paper to further prove the algorithm feasibility and effectiveness. The results of this paper provide further ideas for solving vehicle routing problems with time windows and improving the efficiency of vehicle routing problems and have strong applicability.     

Exact topology discovery algorithm for the capacity and delay constrained loop network

We have developed an exact model and algorithm for the delay-constrained minimum cost loop problem (DC-MCLP) of finding broadcast loops from a source node. While the traditional minimum cost loop problem (MCLP) deals with only the traffic capacity constraint served by a port of source node, the DC-MCLP deals with the mean network delay and traffic capacity constraints simultaneously. The DC-MCLP consists of finding a set of minimum cost loops to link end-user nodes to a source node satisfying the traffic requirements at end-nodes and the required mean delay of the network. In the DC-MCLP, the objective function is to minimise the total link cost. We have formulated the DC-MCLP and proposed an exact algorithm for its solution. The proposed algorithm is composed of two phases: in the first phase, it generates feasible paths to satisfy the traffic capacity constraint; in the second phase it finds the exact loop topology through matching and allocating optimal link capacity to satisfy the mean delay constraint. In addition, we have derived several properties including the memory and time complexity of the proposed algorithm. Performance evaluation shows that the proposed algorithm has good efficiency for networks with less than thirty nodes and light traffic. Our proposed algorithm can be applied to find the broadcast loops for real-time multimedia traffic     

Optimally Locating Multiple Dwell Points in a Single Loop Guide Path System

Dwell points for idle vehicles affect the performance of automated guided vehicle systems. An exact polynomial-time algorithm to solve idle vehicle positioning problems in both unidirectional and bidirectional single loop systems is developed to minimize the maximum response time. The proposed algorithm considers several potential locations for the first dwell point and applies a dynamic programming procedure to obtain the remaining dwell points for each initial location. The algorithm is streamlined by applying certain optimality properties. Computational results show that the algorithm can solve large-scale problems in reasonable time.     

Deterministic oscillatory search: a new meta-heuristic optimization algorithm

The paper proposes a new optimization algorithm that is extremely robust in solving mathematical and engineering problems. The algorithm combines the deterministic nature of classical methods of optimization and global converging characteristics of meta-heuristic algorithms. Common traits of nature-inspired algorithms like randomness and tuning parameters (other than population size) are eliminated. The proposed algorithm is tested with mathematical benchmark functions and compared to other popular optimization algorithms. The results show that the proposed algorithm is superior in terms of robustness and problem solving capabilities to other algorithms. The paradigm is also applied to an engineering problem to prove its practicality. It is applied to find the optimal location of multi-type FACTS devices in a power system and tested in the IEEE 39 bus system and UPSEB 75 bus system. Results show better performance over other standard algorithms in terms of voltage stability, real power loss and sizing and cost of FACTS devices.     

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.     

Mathematical modelling of container transfers and storage locations at seaport terminals

This paper models the seaport system with the objective of determining the optimal storage strategy and container-handling schedule. It presents an iterative search algorithm that integrates a container-transfer model with a container-location model in a cyclic fashion to determine both optimal locations and corresponding handling schedule. A genetic algorithm (GA), a tabu search (TS) and a tabu search/genetic algorithm hybrid are used to solve the problem. The implementation of these models and algorithms are capable of handling the very large problems that arise in container terminal operations. Different resource levels are analysed and a comparison with current practise at an Australian port is done.     

A three-phase heuristic algorithm for fixed-charge capacitated material flow network design with input/output points location

In this paper, we consider the material flow network design problem in which locations of input and output points of departments and flow paths are determined concurrently on a given block layout. The objective of the problem is to minimize the sum of transportation cost, flow paths construction cost and penalty cost for non-smooth material flows, i.e., flows with turns. A mixed integer programming model is given for the problem and a three-phase heuristic algorithm is developed to solve the problem. In the suggested algorithm, we generate an initial flow network by determining locations of input/output points and flow paths sequentially in the first and second phases, respectively, and then improve it by changing locations of input/output points and flow paths iteratively in the third phase. To evaluate the performance of the suggested algorithms, a series of computational experiments are performed on well-known problem instances as well as randomly generated test problems. Results of computational experiments show that the suggested algorithm gives good solutions in a short computation time.     

Solution of facility layout problems with pickup/drop-off locations using random search techniques

Due to non-polynomial hardness, the facility layout problem (FLP) becomes more critical when pickup/drop-off (P/D) locations are considered in the design of an open field layout under a manufacturing environment. This paper proposes an indigenous model of the facility layout problem based on random search techniques and its solution methodology using a genetic algorithm (GA), simulated annealing (SA) and a hybrid algorithm (HA). The paper illustrates the performance of different random search operating parameters in solving the facility layout problem considering P/D locations along the periphery of rectangular machine blocks. The preliminary experiments were carried out on three facility layout test problems having six, eight and ten machines in order to fix the different operating parameters such as crossover operator, crossover rate, initial temperature, temperature reduction factor, number of generations, population size, etc. The results of extensive preliminary experimentation were utilized to solve facility layout problems having 12 and 18 machines and, finally, were compared with the existing procedures in the literature. The experimental tables and related analysis performed via the solution methods by applying GA, SA and HA revealed that random-search-based modeling of FLP considering P/D and its solution as suggested in this paper is worth pursuing.