A hybrid genetic algorithm for machine-part grouping

Cellular manufacturing (CM), which incorporates the flexibility of job shops and high production rate of flow lines, has been seen as a promising alternative for batch type production. Although CM provides great benefits, the design of CM is quite complex for real world problems. The main problem in the design of a CM is the formation of machine groups and corresponding part families. This paper aims at developing an approach that combines a local search heuristic (LSH) with genetic algorithm (GA). The approach has been tested on a number of problems from the literature. The results show that new approach not only converges to the best solution in the earlier generations but also produces solutions that are as accurate as any of the results reported, so far, in literature. Also, in certain cases the results produced by this technique are even better than the previously reported results.     

Simultaneous machine-part grouping approach in manufacturing cells

We present a comprehensive model including all of the operational constraints for solving a cell formation problem in cellular manufacturing systems. It is formulated as a generalized quadratic binary programming model with the objective of minimizing total moves evaluated as a weighted sum of inter- and intracell moves. Two most significant operational constraints included in the model are the sequence of operations associated with each part and the capability of assigning machines of the same type to different cells if two or more machines are considered due to workload requirements. The original model is Transformed into a linear binary programming model, and an example problem is solved using a commercial programming package. The final assignment of parts and machines to cells result in a lower total move than that evaluated from a previous study for the same problem.     

An intelligent grouping algorithm for cellular manufacturing

The methodology presented in this paper will provide a means of identifying part families/machine cells using design and manufacturing characteristics simultaneously. The technique used is a self-organizing neural network called interative-activation and competition (IAC) which acts as a content-addressable memory. This neural network is used to define a similarity index of the pairwise comparisons of parts based on a variety of design and manufacturing characteristics. A bond energy algorithm partitions the matrix of part similarity indices to create part families and inferred from the part families are machine cells. A brief example will be examined as well as discussion of the results.     

Two-stage approach for machine-part grouping and cell layout problems

Cellular manufacturing system (CMS) which is based on the concept of group technology (GT) has been recognized as an efficient and effective way to improve the productivity in a factory. In recent years, there have been continuous research efforts to study different facet of CMS. Most of them concentrated on distinguishing the part families and machine cells either simultaneously or individually with the objective of minimizing intercellular and intracellular part movements. This is known as machine-part grouping problem (MPGP) which is a crucial process while designing CMS. Nevertheless, in reality some components may not be finished within only one cell, they have to travel to another cell(s) for further operation(s). Under this circumstance, intercellular part movement will occur. Different order/sequence of machine cells allocation may result in different total intercellular movement distance unit. It should be noted that if the production volume of each part is very large, then the total number of intercellular movement will be further larger. Therefore, the sequence of machine cells is particularly important in this aspect. With this consideration, the main aim of this work is to propose two-stage approach for solving cell formation problem as well as cell layout problem. The first stage is to identify machine cells and part families, which is the essential part of MPGP. The work in second stage is to carry out a macro-approach to study the cell formation problem with consideration of machining sequence. The impact of the sequencing for allocating the machine cells on minimizing intercellular movement distance unit will be investigated in this stage. The problem scope, which is a MPGP together with the background of cell layout problem (CLP), has been identified. Two mathematical models are formulated for MPGP and CLP respectively. The primary assumption of CLP is that it is a linear layout. The CLP is considered as a quadratic assignment problem (QAP). As MPGP and QAP are NP-hard, genetic algorithm (GA) is employed as solving algorithm. GA is a popular heuristic search technique and has proved superior performance on complex optimization problem. In addition, an industrial case study of a steel member production company has been employed to evaluate the proposed MPGP and CLP models, and the computational results are presented.     

A heuristic grouping procedure for component family formation in a cellular manufacturing environment

A heuristic clustering procedure is introduced for grouping purposes in a cellular manufacturing environment. The procedure uses the concepts of “edge-cut” and “cut-set” of graph theory in combination with a similarity measure to group the objects. An experiment was conducted to compare twelve different variations of the procedure when used for component family identification. Two measures of performance are used to select the most suitable variation of the procedure and a numerical example is given for the variation.     

Integrating the grouping and layout problems in cellular manufacturing systems

In this paper, the simultaneous solution of the machine grouping and layout problems in cellular manufacturing systems is explored. A model for the combined problem is presented. Since the model is complex to solve using traditional optimization techniques, a suboptimal procedure involving the use of a simulated annealing based algorithm is suggested. Results with a numerical example are presented. An alternative formulation based on quandratic assignment problem is also presented.     

A six sigma based multi-objective optimization for machine grouping control in flexible cellular manufacturing systems with guide-path flexibility

Effective design of automatic material handling devices is one of the most important decisions in flexible cellular manufacturing systems. Minimization of material handling operations could lead to optimization of overall operational costs. An automated guided vehicle (AGV) is a driverless vehicle used for the transportation of materials within a production plant partitioned into cells. The tandem layout is according to dividing workstations to some non-overlapping closed zones to which a tandem automated guided vehicle (TAGV) is allocated for internal transfers. This paper illustrates a non-linear multi-objective problem for minimizing the material flow intra and inter-loops and minimization of maximum amount of inter cell flow, considering the limitation of TAGV work-loading. For reducing variability of material flow and establishing balanced zone layout, some new constraints have been added to the problem based on six sigma approach. Due to the complexity of the machine grouping control problem, a modified ant colony optimization algorithm is used for solving this model. Finally, to validate the efficacy of the proposed model, numerical illustrations have been worked out.     

A genetic algorithm approach to cellular manufacturing systems

A genetic algorithm (GA) metaheuristic-based cell formation procedure is presented in this paper. The cell formation problem solved here is to simultaneously group machines and part-families into cells so that intercellular movements are minimized. An option for considering the minimization of cell load variation is included and another, which combines minimization of intercellular movements and cell load-variation, exists. The algorithm solves this problem through improving a cell configuration using the GA metaheuristic. The designer is allowed to specify the number of cells required a priori and impose lower and upper bounds on cell size. This makes the GA scheme flexible for solving the cell formation problems. The solution procedure was found to perform well on tested large-scale problems and published data sets. Moreover, the proposed procedure compares very favorably to a well-known algorithm, and another TSP-based heuristic available in the literature. The results of computational tests presented are very encouraging.     

A dynamic programming based heuristic for machine grouping in manufacturing cell formation

This paper presents a two stage heuristic for solving the machine grouping problem encountered in the identification and formation of flexible manufacturing cells. A new similarity measure, called Cell Bond Strength, is introduced which exploits similarity in processing for pairs of machines. The Cell Bond Strengths values are calculated based upon part routing and production requirements data. In the first stage of the heuristic, a Dynamic Programming procedure is used to determine an optimum “chain” of machines in which the sum of the bonds between machines is maximized. The second stage of this heuristic partitions the chain to form machine cells, subject to cell size restrictions. An example is given to illustrate the heuristic procedure. A summary of computational results when the heuristic is applied to several examples from the literature is also presented.     

基于优先级分组的防碰撞算法

针对在标签数量较多、运动较快的场合,常存在识别效率低且标签漏读率高的问题,提出一种先分组再处理的防碰撞算法——PAJS。该算法按照到达顺序对标签进行分组,以减小漏读率;根据标签识别过程中时隙状况自适应调整帧长度,提高算法的搜索效率;采用跳跃式动态搜索算法处理冲突时隙,从而减少搜索次数和系统传输量。Matlab仿真结果表明,该算法通信复杂度明显小于其他常用算法,吞吐率可达0.59~0.6。在待识别标签较多的场合,该算法优越性更加明显。     

基于信息预处理的分组动态二进制防碰撞算法

针对现有二进制防碰撞算法通信数据量大、存在冗余信息的缺点,提出了一种新二进制防碰撞算法。新算法在阅读器与标签的首次通信中首先进行信息预处理,后继识别过程中只处理冲突位,然后利用每次探测得到的碰撞位信息构造二叉树。最高碰撞位之前的部分后接一个“0”为左子树,最高碰撞位之前的部分后接一个“1”+两个最高碰撞位之间的部分为右子树,在叶子结点实现标签的识别。该算法从阅读器和标签两方面同时进行改进,减少了通信量,提高了识别效率。     

A part-machine assignment algorithm for cellular manufacturing with machine capacity constraints

Many researchers have attempted to solve the cellular manufacturing problem using various clustering techniques; however, few have considered the effect of production constraints. In this paper an algorithm for the assignment of parts to machines to solve the group technology problem which takes into consideration the effect of machine capacity constraints is discussed. The effect of this constraint is demonstrated by an example.     

基于分组的启发式SAT新算法——DC&DS算法

目前提高求解SAT问题完全算法的计算效率问题已成为挑战性研究问题。提出了一种基于启发式分组的SAT完备算法。启发式分组策略将一个全局搜索问题,转为局部搜索问题。并将该策略引入到结合BDD与SAT算法的形式验证中,与一般的启发式SAT算法相比,该算法在求解速度和求解问题的规模等方面都明显地改进了,实验结果表明了该算法的可行性和有效性。     

基于标签分组的RFID防碰撞算法

针对无线射频识别技术中的读写碰撞问题提出了一种新的标签防碰撞算法。该算法利用陪集分解理论将电子标签分组,限定每组标签在规定的时隙响应。根据查询码和碰撞特征位,阅读器可在一个时隙内识别出一组标签。Matlab仿真结果表明,在多标签时该算法的时隙利用率和吞吐率优于二进制搜索算法和动态帧时隙算法。     

基于两阶段调度的制造单元协同调度算法研究

针对单元制造问题,提出了一种基于两阶段的调度算法,通过过程分解和算法优化两方面实现问题求解。调度过程分为“预调度”和“整体调度”两个阶段,对大规模调度进行调度,不仅有效地降低了问题规模,同时制造单元调度结果对实际生产具有现实意义;调度算法采用了“精确”计算和“近似”求解相结合的方式,既提高计算效率又兼顾了全局优化目标。数值实验结果表明了的这一设计思路的有效性。     

一种基于点集自适应分组构建Voronoi 图的并行算法

论文提出一种基于点集自适应分组构建Voronoi 图的并行算法,其基本思 路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成 Voronoi 图,称为Voronoi 子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi 图,称为边界点Voronoi 图;最后,针对每个边界点,提取其位于Voronoi 子图和边界点Voronoi 图内所对应的两个多边形,进行Voronoi 多边形的合并,最终实现子网的合并。考虑到算法 耗时主要在分组点集的Voronoi 图生成,而各分组的算法实现不受其他分组影响,采用并行 计算技术加速分组点集的Voronoi 图生成。理论分析和测试表明,该算法是一个效率较高的 Voronoi 图生成并行算法。     

An improved algorithm for layout design in cellular manufacturing systems

Layout has a significant role on the efficiency of manufacturing systems, but it has not received attention of researchers in comparison to cell formation in cellular manufacturing systems. In this paper, a mathematical model for facility layout in a cellular manufacturing system is proposed that minimizes both inter-cell and intra-cell material handling costs. A variant of simulated annealing algorithm is developed to solve the model. The developed algorithm produces solutions with better quality and less computation time in comparison with the benchmarked algorithm. The superiority of the algorithm in computation time is considerable especially when the size of the problem increases.     

基于Raft分组的实用拜占庭共识算法

针对现有应用于联盟链的拜占庭容错共识机制可扩展性不足、难以支持大规模网络节点下高效安全共识等问题,采用节点分组策略,提出一种基于Raft聚类分组的实用拜占庭容错共识算法H-PBFT。首先使用混合蛙跳算法结合K-medoids聚类分组策略,将系统中节点聚类形成多个分组;参与主共识集群PBFT共识的节点均为各分组聚类中心节点,各聚类小组内则使用引入监督节点改进的Raft算法进行共识;组内共识机制监督节点的引入使Raft算法具有抗拜占庭的能力。实验研究结果表明,在大规模网络节点环境下,相比于PBFT和Raft,H-PBFT算法提高了容错性能,同时还能够快速高效对节点聚类分组,提高共识效率,降低共识通信开销与复杂度,具有较优的可扩展性,能够更好的在联盟链场景中应用。     

基于预分类的标签传播分组算法

针对已有正则表达式分组算法的分组效果与分组时间难以平衡的问题,本文提出了基于预分类的标签传播分组算法。该算法首先分析了规则间膨胀特征,基于此对正则表达式集合进行预分类;然后借鉴标签传播思想对包含克林闭包的正则表达式集合分组,通过改进初始标签分配和传播过程实现快速聚敛。仿真实验证明,该算法与当前的正则表达式分组算法相比,在相同分组数情况下,有着较少的状态数和更短的分组时间。     

基于散列的频繁项集分组算法

Apriori算法是频繁项集挖掘的经典算法。针对Apriori算法的剪枝操作和多次扫描数据集的缺点,提出了基于散列的频繁项集分组(HFG)算法。证明了2-项集剪枝性质,采用散列技术存储频繁2-项集,将Apriori算法剪枝操作的时间复杂度从O(k×|Lk|)降低到O(1);定义了首项的子项集概念,将数据集划分为以Ii为首项的数据子集并采用分组索引表存储,在求以Ii为首项的频繁项集时,只扫描以Ii为首项的数据子集,减少了对数据集扫描的时间代价。实验结果表明,由于HFG算法的剪枝操作产生了累积效益,以及分组扫描排除了无效的项集和元组,使得HFG算法在时间性能方面与Apriori算法相比有较大提高。