Clustering algorithm for solving group technology problem with multiple process routings

Cell formation is an important problem in the design of a cellular manufacturing system. Most of the cell formation methods in the literature assume that each part has a single process plan. However, there may be many alternative process plans for making a specific part, specially when the part is complex. Considering part multiple process routings in the formation of machine-part families in addition to other production data is more realistic and can produce more independent manufacturing cells with less intercellular moves between them. A new comprehensive similarity coefficient that incorporates multiple process routings in addition to operations sequence, production volumes, duplicate machines, and machines capacity is developed. Also, a clustering algorithm for machine cell formation is proposed. The algorithm uses the developed similarity coefficient to calculate the similarity between machine groups. The developed similarity coefficient showed more sensitivity to the intercellular moves and produced better machine grouping.     

Design of robust cellular manufacturing system for dynamic part population considering multiple processing routes using genetic algorithm

In this paper, a comprehensive mathematical model is proposed for designing robust machine cells for dynamic part production. The proposed model incorporates machine cell configuration design problem bridged with the machines allocation problem, the dynamic production problem and the part routing problem. Multiple process plans for each part and alternatives process routes for each of those plans are considered. The design of robust cell configurations is based on the selected best part process route from user specified multiple process routes for each part type considering average product demand during the planning horizon. The dynamic part demand can be satisfied from internal production having limited capacity and/or through subcontracting part operation without affecting the machine cell configuration in successive period segments of the planning horizon. A genetic algorithm based heuristic is proposed to solve the model for minimization of the overall cost considering various manufacturing aspects such as production volume, multiple process route, machine capacity, material handling and subcontracting part operation.     

Grouping efficiency measures and their impact on factory measures for the machine-part cell formation problem: A simulation study

Over the past 25 years, the machine-part cell formation problem has been the subject of numerous studies. Researchers have applied various methodologies to the problem in an effort to determine optimal clusterings of machines and optimal groupings of parts into families. The quality of these machine and part groupings have been evaluated using various objective functions, including grouping efficacy, grouping index, grouping capability index, and doubly weighted grouping efficiency, among others. In this study, we investigate how appropriate these grouping quality measures are in determining cell formations that optimize factory performance. Through the application of a grouping genetic algorithm, we determine machine/part cell formations for several problems from the literature. These cell formations are then simulated to determine their impact on various factory measures, such as flow time, wait time, throughput, and machine utilization, among others. Results indicate that it is not always the case that a “more efficient” machine/part cell formation leads to significant changes or improvements in factory measures over a “less efficient” cell formation. In other words, although researchers are working to optimize cell formations using efficiency measures, cells formed this way do not always demonstrate optimized factory measures.     

A genetic-algorithm-based heuristic for the GT cell formation problem

This paper presents a heuristic for the machine-part grouping problem which incorporates relevant production requirements such as routing sequence, production volume, unit handling size, unit processing time and cell size. The heuristic consists of two phases. The first phase is developed based on a genetic algorithm and greedy heuristic to solve the machine grouping problem. Once machine cells are identified, the second phase is employed to identify the associated part families. The performance of the heuristic is examined through a comparative study with some existing solution methods. Global efficiency, group efficiency, intercell move factor and grouping effectiveness are adopted as comparative measures.     

Development of bacteria foraging optimization algorithm for cell formation in cellular manufacturing system considering cell load variations

The cellular manufacturing system (CMS) is considered as an efficient production strategy for batch type production. The CMS relies on the principle of grouping machines into machine cells and grouping machine parts into part families on the basis of pertinent similarity measures. The bacteria foraging optimization (BFO) algorithm is a modern evolutionary computation technique derived from the social foraging behavior of Escherichia coli bacteria. Ever since Kevin M. Passino invented the BFO, one of the main challenges has been the employment of the algorithm to problem areas other than those of which the algorithm was proposed. This paper investigates the first applications of this emerging novel optimization algorithm to the cell formation (CF) problem. In addition, for this purpose matrix-based bacteria foraging optimization algorithm traced constraints handling (MBATCH) is developed. In this paper, an attempt is made to solve the cell formation problem while considering cell load variations and a number of exceptional elements. The BFO algorithm is used to create machine cells and part families. The performance of the proposed algorithm is compared with a number of algorithms that are most commonly used and reported in the corresponding scientific literature such as K-means clustering, the C-link clustering and genetic algorithm using a well-known performance measure that combined cell load variations and a number of exceptional elements. The results lie in favor of better performance of the proposed algorithm.     

Machine cell/part family formation considering processing times and machine capacities: a simulated annealing approach

Binary machine-part matrices have been widely used to identify machine groups and part families. The methods based on binary machine-part matrices mostly focus on the reduction of setup times and material handling costs. However, some other objectives such as the maximization of within-cell utilization and minimization of workload imbalance may not be achieved without considering other important factors such as processing times, lot sizes and machine capacities. Ignoring the processing times may violate the capacity constraints, and thus lead to an infeasible solution. This paper proposes a generalized grouping efficiency considering processing times and lot sizes. A simulated annealing algorithm is developed to solve the grouping problem and a neural network approach is used to provide a seed solution. Our computational experience indicates that the proposed algorithm is able to find a near optimum solution with less number of duplicated machines and better workload balance as compared to the approach reported in the literature.     

A hybrid grouping genetic algorithm for the cell formation problem

The machine-part cell formation problem consists of constructing a set of machine cells and their corresponding product families with the objective of minimizing the inter-cell movement of the products while maximizing machine utilization. This paper presents a hybrid grouping genetic algorithm for the cell formation problem that combines a local search with a standard grouping genetic algorithm to form machine-part cells. Computational results using the grouping efficacy measure for a set of cell formation problems from the literature are presented. The hybrid grouping genetic algorithm is shown to outperform the standard grouping genetic algorithm by exceeding the solution quality on all test problems and by reducing the variability among the solutions found. The algorithm developed performs well on all test problems, exceeding or matching the solution quality of the results presented in previous literature for most problems.     

A bacteria foraging algorithm based cell formation considering operation time

The cellular manufacturing system (CMS) is considered as an efficient production strategy for batch type production. The CMS relies on the principle of grouping machines into machine cells and grouping machine parts into part families based on pertinent similarity measures. The bacteria foraging algorithm (BFA) is a new in development computation technique extracted from the social foraging behavior of Escherichia coli (E. coli) bacteria. Ever since Kevin M. Passino invented the BFA, one of the main challenges has been employment of the algorithm to problem areas other than those for which the algorithm was proposed. This research work inquires the first applications of this emerging novel optimization algorithm to the cell formation (CF) problem. In addition, a newly developed BFA-based optimization algorithm for CF is discussed. In this paper, an attempt is made to solve the cell formation problem meanwhile taking into consideration number of voids in cells and a number of exceptional elements based on operational time of the parts required for processing in the machines. The BFA is suggested to create machine cells and part families. The performance of the proposed algorithm is compared with a number of algorithms that are most commonly used and reported in the corresponding scientific literature such as similarity coefficients methods (SCM), rank order clustering (ROC), ZODIAC, GRAFICS, MST, GATSP, GP, K-harmonic clustering (KHM), K-means clustering, C-link clustering, modified ART1, GA (genetic algorithm), evolutionary algorithm (EA), and simulated annealing (SA) using defined performance measures known as modified grouping efficiency and grouping efficacy. The results lie in favor of better performance of the proposed algorithm.     

A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem

The integrated aircraft routing and crew scheduling problem consists in determining a minimum-cost set of aircraft routes and crew pairings such that each flight leg is covered by one aircraft and one crew, and side constraints are satisfied. While some side constraints involve only crews or aircraft, linking constraints impose minimum connection times for crews that depend on aircraft connections. We propose an enhanced model incorporating robustness to handle these linking constraints and compare two Benders decomposition methods—one with the aircraft routing problem as the master problem and one with the crew pairing problem. We also study the impact of generating Pareto-optimal cuts on the speed of convergence of these methods. Computational experiments performed on test instances provided by two major airlines show that the proposed approach yields high-quality solutions in reasonable computing times.     

Cell formation using multiple process plans

Cell formation (CF) consists of identifying machine groups and part families. Many CF procedures use a part machine matrix as an input and attempt to obtain a block diagonal form. But perfect block diagonalization of parts and machines is not possible is many cases. In this paper we consider a generalized cellular manufacturing (CM) problem, in which each part can have alternate process plans and each operation can be performed on alternate machines. Under these conditions the CF problem of assigning parts and machines to each manufacturing cell can be considered as a two stage process. The first stage deals with the problem of determining a unique process plan for each part. The second stage determines the part families and machine cells. In this research a model for forming part families and machine cells is presented considering alternate process plans. The objective is to analyze how alternate process plans influence and enhance the CM process giving better flexibility to the designer while designing cells for CM.     

The sustainable cell formation problem: manufacturing cell creation with machine modification costs

An approach for manufacturing cell formation with machine modification is presented. In cell formation it is often important in practice to be able to reassign parts to additional machine types in order to create better cell configurations. This involves extending the set of parts that certain individual machines can process. Such extensions may be cheaper than simply purchasing additional machines. Thus, there is the possibility of machine modification to reduce inter-cell travel. The cost of such modifications must be balanced by the consequent reduction in inter-cell travel cost. The extended machine cell formation problem to be described involves the specification of which individual machines should be modified to enable them to process additional part types, part-machine assignment, and the grouping of individual machines for cell formation. The objective is to minimize the sum of the machine modification costs and the inter-cell travel. We call this the sustainable cell formation problem (SCFP). As far as the authors are aware, there have not been any solution procedures for this important problem reported in the open literature. It is our purpose to fill this gap by presenting a mixed integer programming model of the SCFP. We also propose and analyze greedy and tabu search heuristics for the design of large-scale systems related to the SCFP. Computational experience with the solution procedures indicates that they are likely to be useful additions to the production engineer's toolkit.     

支持时延-带宽约束的动态层次组播路由

层次网络及层次路由成为解决大规模网络QoS路由可扩展性问题的一个主要手段.文中对PNNI层次网络模型下的时延-带宽多QoS约束的动态组播路由问题进行了全面研究:在已提出支持时延-带宽约束的拓扑聚集算法(Stair)的基础上,进一步对组播树节点需维护的组播树状态信息及其聚集问题进行研究,并提出"伪树上边界节点"模式的域内组播树状态信息的聚集方法,最后设计了基于聚集拓扑信息和组播树状态信息的动态层次组播路由算法.仿真结果显示,该路由不仅大量压缩了存储和扩散的拓扑信息和组播树状态信息,同时还保持了与平面网络近似的路由效率,实现了大规模网络情况下组播路由的扩展.     

带时间窗和服务顺序约束的多需求车辆路径问题

研究顾客具有多种需求,分别需要由不同类型车辆提供服务,且同一顾客多种需求的服务时间具有固定先后顺序的车辆路径问题.在考虑各个顾客需求的服务时间窗,同一顾客不同需求的服务顺序、服务时间间隔,以及各种车型的车容量及最大行驶时间等约束的前提下,以满足顾客多种需求的车辆运行成本和等待成本之和极小化为目标,建立混合整数规划模型.进一步设计求解模型的联合优化遗传算法,并利用车辆路径问题的标准测试集构造具有两种需求的测试算例,分别利用所提出的联合优化遗传算法与文献中的两阶段遗传算法进行模拟计算与分析,验证所提出算法的有效性.将经典的单一需求车辆路径问题推广到多种需求的情形,建立带约束的多需求车辆路径问题的数学模型并设计求解模型的有效算法,为解决实际问题提供了决策依据.     

A two-stage model for cost effective part family and machine cell formation

This research presents, implements and tests a two-stage procedure for cost effective part family and machine cell formation. First, the problem is formulated as a mixed integer mathematical model for simultaneous machine grouping and part family assignment. This model, which we refer to as the single-stage model, considers the cost trade-offs of cell configuration, machine procurement and salvage, subcontracting, inter-cell movement, and capital investment, all of which reflect the significance of real life planning aspects. To alleviate the computational burden of this single-stage model, we decompose it into two stages: the first stage is a heuristic for machine cell and part family formations; the second stage integrates the heuristic method with a mathematical program to optimize the various cost aspects. The efficacy of the proposed models is shown through a number of example problems. The results show that the two-stage procedure is powerful in the planing stages of large-size problems where the cost aspects are crucial.     

A hybrid method based on genetic algorithm and dynamic programming for solving a bi-objective cell formation problem considering alternative process routings and machine duplication

Cell formation is one of the first and most important steps in designing a cellular manufacturing system. It consist of grouping parts with similar design features or processing requirements into part families and associated machines into machine cells. In this study, a bi-objective cell formation problem considering alternative process routings and machine duplication is presented. Manufacturing factors such as part demands, processing times and machine capacities are incorporated in the problem. The objectives of the problem include the minimization of the total dissimilarity between the parts and the minimization of the total investment needed for the acquisition of machines. A normalized weighted sum method is applied to unify the objective functions. Due to the computational complexity of the problem, a hybrid method combining genetic algorithm and dynamic programming is developed to solve it. In the proposed method, the dynamic programming is implemented to evaluate the fitness value of chromosomes in the genetic algorithm. Computational experiments are conducted to examine the performance of the hybrid method. The computations showed promising results in terms of both solution quality and computation time.     

Operations planning and scheduling problems in an FMS: An integrated approach

Operations planning and scheduling (OPS) problems in advanced manufacturing systems, such as flexible manufacturing systems, are composed of a set of interrelated problems, such as part-type batching, machine grouping, tool loading, routing, part input sequencing and on-line scheduling. In this paper, an integrated, simulation-based approach to the OPS problems is discussed. A detailed simulation model is developed using FORTRAN and SLAM II which integrates loading, part inputting, routeing and dispatching issues of the OPS. An experimental frame is developed which provides statistical analysis of the simulation output by developing an experimental design. Statistical analyses concerning a number of system parameters (e.g. loading strategies and scheduling rules) are performed on a set of performance measures.     

Artificial intelligence heuristics in solving vehicle routing problems with time window constraints

This paper describes the authors’ research on various heuristics in solving vehicle routing problem with time window constraints (VRPTW) to near optimal solutions. VRPTW is NP-hard problem and best solved to near optimum by heuristics. In the vehicle routing problem, a set of geographically dispersed customers with known demands and predefined time windows are to be served by a fleet of vehicles with limited capacity. The optimized routines for each vehicle are scheduled as to achieve the minimal total cost without violating the capacity and time window constraints. In this paper, we explore different hybridizations of artificial intelligence based techniques including simulated annealing, tabu search and genetic algorithm for better performance in VRPTW. All the implemented hybrid heuristics are applied to solve the Solomon's 56 VRPTW with 100-customer instances, and yield 23 solutions competitive to the best solutions published in literature according to the authors’ best knowledge.     

Knowledge based approach to machine cell layout

In this paper, the machine cell layout problem is examined. A new methodology for solving the problem is proposed. The methodology involves three stages. In the first stage, an algorithm suitable for solving the machine grouping problem is utilized. In the second and third stages, mathematical programming models of the machine cell and machine layout problems are formulated and solved using suitable algorithms. The development of a knowledge based system which uses models and algorithms for solving the machine grouping and layout problems, is also outlined.     

Multi-period part selection and loading problems in flexible manufacturing systems

We consider multi-period part selection and loading problems in flexible manufacturing systems with the objective of minimizing subcontracting costs. The part selection problem is to select sets of part types and to determine their quantities to be produced during the upcoming planning horizon while satisfying due dates of all orders for the parts, and the loading problem involves allocation of operations and required tools to machines. Production demands should be satisfied for periods through subcontracting if production demands cannot be satisfied by the system due to machine capacity or tool magazine capacity constraints. For the part selection and loading problems, we develop three iterative algorithms, called the forward algorithm, the backward algorithm and the capacity approximation algorithm, that solve the part selection and loading problems iteratively for each period. To compare the three algorithms, a series of computational experiments is done on randomly generated test problems.     

Integrated topology control and routing in wireless optical mesh networks

We study the problem of integrated topology control and routing in Free Space Optical (FSO) mesh backbone networks. FSO links are high-bandwidth, low interference links that can be set-up very fast, making them suitable for mesh networking. FSO networks are highly constrained by interface constraints, i.e., constraints on the number of FSO links a node can establish. We prove the problem to be NP-Hard and propose efficient algorithms for integrated topology control and single-path or multi-path routing.