Machine cell formation considering processing times and machine capacities: An ortho-synapse Hopfield neural network approach

The machine/part grouping problems can be classified into binary and comprehensive grouping problems depending on whether or not the processing times and the machine capacities are considered. The binary grouping problem arises if the part demands are unknown when the CMS is being developed. If the part demand can be forecast accurately, both the processing times and machine capacities have to be included in the analysis. This gives rise to comprehensive grouping. Both the binary and comprehensive grouping have been proven to be NP-complete which cannot be solved in polynomial time. Considering the large number of parts and machines involved in the industrial design problem, efficient solution methods are highly desirable. In this paper, a new neural network approach (OSHN_g) is proposed to solve the comprehensive grouping problems. The proposed approach has been tested on 28 test problems. The results show that the OSHN_g method is very efficient and its solution quality is comparable to that of a simulated annealing approach.     

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 genetic algorithm application using fuzzy processing times in non-identical parallel machine scheduling problem

There are many scheduling problems which are NP-hard in the literature. Several heuristics and dispatching rules are proposed to solve such hard combinatorial optimization problems. Genetic algorithms (GA) have shown great advantages in solving the combinatorial optimization problems in view of its characteristic that has high efficiency and that is fit for practical application [1]. Two different scale numerical examples demonstrate the genetic algorithm proposed is efficient and fit for larger scale identical parallel machine scheduling problem for minimizing the makespan. But, even though it is a common problem in the industry, only a small number of studies deal with non-identical parallel machines. In this article, a kind of genetic algorithm based on machine code for minimizing the processing times in non-identical machine scheduling problem is presented. Also triangular fuzzy processing times are used in order to adapt the GA to non-identical parallel machine scheduling problem in the paper. Fuzzy systems are excellent tools for representing heuristic, commonsense rules. That is why we try to use fuzzy systems in this study.     

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.     

多品种、小批量离散型制造企业生产车间零件/机床成组方法研究*

针对多品种、小批量离散型制造企业生产车间零件种类多、可选加工工艺路线集合空间大等特点,从零件加工工艺路线角度出发,构建车间零件加工的物流成本和时间函数模型。利用遗传算法良好的收敛性、强全局寻优能力和径向基函数神经网络(RBFNN)较高的鲁棒性、数据分类能力强的优势,提出GA-RBFNN混合算法,解决了零件在其可行加工工艺路线集合内的最佳分配和零件/机床最优分组问题。最后,结合实例验证了该模型和方法的有效性和可行性。     

Heuristics for the two‐machine scheduling problem with a single server

In this paper, the NP‐hard two‐machine scheduling problem with a single server is addressed. The problem consists of a given set of jobs to be scheduled on two identical parallel machines, where each job must be processed on one of the machines, and prior to processing, the job is set up on its machine using one server; the latter is shared between the two machines. An ant colony optimization (ACO) algorithm is introduced for the problem and its performance was assessed by comparing with an exact solution (branch and bound [B&B]), a genetic algorithm (GA), and simulated annealing (SA). The computational results reflected the superiority of “ACO” in large problems, with a performance similar to SA and GA in smaller problems, while solving the tested problems within a reasonable computational time.     

A multiple-objective grouping genetic algorithm for the cell formation problem with alternative routings

This paper addresses the cell formation problem with alternative part routings, considering machine capacity constraints. Given processes, machine capacities and quantities of parts to produce, the problem consists in defining the preferential routing for each part optimising the grouping of machines into manufacturing cells. The main objective is to minimise the inter-cellular traffic, while respecting machine capacity constraints. To solve this problem, the authors propose an integrated approach based on a multiple-objective grouping genetic algorithm for the preferential routing selection of each part (by solving an associated resource planning problem) and an integrated heuristic for the cell formation problem.     

基于改进分组遗传算法的虚拟机放置研究

为了提高云计算的资源利用率以及减少能耗,采用改进的分组遗传算法来解决虚拟机放置的效率.通过对遗传算法的交配和突变等过程进行重新设计,提高遗传算法过程中优秀基因遗传给后代的几率,并提出了相应的算法,达到快速求解虚拟机放置问题的目的.实验结果表明,该算法可以快速采用最少的物理机来放置虚拟机,有效地提高了虚拟机放置问题的求解速度.     

Evaluating performance advantages of grouping genetic algorithms

The genetic algorithm (GA) and a related procedure called the grouping genetic algorithm (GGA) are solution methodologies used to search for optimal solutions in constrained optimization problems. While the GA has been successfully applied to a range of problem types, the GGA was created specifically for problems involving the formation of groups. Falkenauer (JORBEL—Belg. J. Oper. Res. Stat. Comput. Sci. 33 (1992) 79), the originator of the GGA, and subsequent researchers have proposed reasons for expecting the GGA to perform more efficiently than the GA on grouping problems. Yet, there has been no research published to date which tests claims of GGA superiority. This paper describes empirical tests of the performance of GA and GGA in three domains which have substantial, practical importance, and which have been the subject of considerable academic research. Our purpose is not to determine which of these two approaches is better across an entire problem domain, but rather to begin to document practical differences between a standard off-the-shelf GA and a tailored GGA. Based on the level of solution quality desired, it may be the case that the additional time and resources required to design a tailored GGA may not be justified if the improvement in solution quality is only minor or non-existent.     

A modified genetic algorithm for the flow shop sequencing problem to minimize mean flow time

A modified genetic algorithm (MGA) is developed for solving the flow shop sequencing problem with the objective of minimizing mean flow time. To improve the general genetic algorithm (GA) procedure, two additional operations are introduced into the algorithm. One replaces the worst solutions in each generation with the best solutions found in previous generations. The other improves the most promising solution, through local search, whenever the best solution has not been updated for a certain number of generations. Computational experiments on randomly generated problems are carried out to compare the MGA with the general GA and special-purpose heuristics. The results show that the MGA is superior to general GA in solution quality with similar computation times. The MGA solutions are also better than those given by special-purpose heuristics though MGA takes longer computation time.     

A genetic algorithm with proper parameters for manufacturing cell formation problems

One fundamental problem in cellular manufacturing is the formation of product families and machine cells. Many solution methods have been developed for the cell formation problem. Since efficient grouping is the prerequisite of a successful Cellular Manufacturing installation the research in this area will likely be continued. In this paper, we consider the problem of cell formation in cellular manufacturing systems with the objective of maximizing the grouping efficacy. We propose a Genetic Algorithm (GA) to obtain machine-cells and part-families. Developed GA has three different selection and crossover operators. The proper operators and parameters of the GA were determined by design of experiments. A set of 15 test problems with various sizes drawn from the literature is used to test the performance of the proposed algorithm. The corresponding results are compared to several well-known algorithms published. The comparative study shows that the proposed GA improves the grouping efficacy for 40% of the test problems.     

A genetic algorithm approach to the multiple machine tool selection problem

A number of earlier researches have emphasized the on-the-job scheduling problems that occur with a single flexible machine. Two solutions to the problem have generally been considered; namely minimization of tool switches and minimization of tool switching instances. Methods used to solve the problems have included KTNS heuristic, dual-based relaxation heuristic, and non-LP-based branch-and-bound methods. However, scant literature has considered the case of job scheduling on multiple parallel machines which invokes another problem involving machine assignment. This paper addresses the problem of job scheduling and machine assignment on a flexible machining workstation (FMW) equipped with multiple parallel machines in a tool-sharing environment. Under these circumstances, the authors have attempted to model the problem with the objective of simultaneously minimizing both the number of tool switches and the number of tool switching instances. Furthermore, a set of realistic constraints has been included in the investigation. A novel genetic algorithm (GA) heuristic has been developed to solve the problem, and performance results show that GA is an appropriate solution.     

基于特征选择的智能化分组遗传算法

典型遗传算法在进化过程中易陷入局部收敛、过早收敛,效率低,针对这些问题,提出一种基于特征选择的智能化分组遗传算法,利用特征选择原理和分组优化思想对进化过程中的基因进行智能分组的遗传操作,在适应度函数中引入个体特征构建动态的环境适应度评价模型。算法通过分组的遗传操作,保证了父代的优秀模式遗传到下一代,加快了收敛速度,分组变异算子扩大了搜索范围,使结果容易走出局部最优解。应用实验验证表明,算法对局部最优解有较强的免疫能力,有效搜索到全局最优解的进化代数较典型遗传算法明显减少,收敛精度高,证明了算法的有效性。     

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 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.     

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 robust hybrid approach based on particle swarm optimization and genetic algorithm to minimize the total machine load on unrelated parallel machines

This paper dealt with an unrelated parallel machines scheduling problem with past-sequence-dependent setup times, release dates, deteriorating jobs and learning effects, in which the actual processing time of a job on each machine is given as a function of its starting time, release time and position on the corresponding machine. In addition, the setup time of a job on each machine is proportional to the actual processing times of the already processed jobs on the corresponding machine, i.e., the setup times are past-sequence-dependent (p-s-d). The objective is to determine jointly the jobs assigned to each machine and the order of jobs such that the total machine load is minimized. Since the problem is NP-hard, optimal solution for the instances of realistic size cannot be obtained within a reasonable amount of computational time using exact solution approaches. Hence, an efficient method based on the hybrid particle swarm optimization (PSO) and genetic algorithm (GA), denoted by HPSOGA, is proposed to solve the given problem. In view of the fact that efficiency of the meta-heuristic algorithms is significantly depends on the appropriate design of parameters, the Taguchi method is employed to calibrate and select the optimal levels of parameters. The performance of the proposed method is appraised by comparing its results with GA and PSO with and without local search through computational experiments. The computational results for small sized problems show that the mentioned algorithms are fully effective and viable to generate optimal/near optimal solutions, but when the size of the problem is increased, the HPSOGA obtains better results in comparison with other algorithms.     

Solving facilities location problem in the presence of alternative processing routes using a genetic algorithm

Facilities location problem deals with the optimization of location of manufacturing facilities like machines, departments, etc. in the shop floor. This problem greatly affects performance of a manufacturing system. It is assumed in this paper that there are multiple products to be produced on several machines. Alternative processing routes are considered for each product and the problem is to determine the processing route of each product and the location of each machine to minimize the total distance traveled by the materials within the shop floor. This paper presents a mixed-integer non-linear mathematical programming formulation to find optimal solution of this problem. A technique is used to linearize the formulated non-linear model. However, due to the NP-hardness of this problem, even the linearized model cannot be optimally solved by the conventional mathematical programming methods in a reasonable time. Therefore, a genetic algorithm is proposed to solve the linearized model. The effectiveness of the GA approach is evaluated with numerical examples. The results show that the proposed GA is both effective and efficient in solving the attempted problem.     

An adaptive hybrid genetic algorithm for the three-matching problem

This paper presents a hybrid genetic algorithm (GA) with an adaptive application of genetic operators for solving the 3-matching problem (3MP), an NP-complete graph problem. In the 3MP, we search for the partition of a point set into minimal total cost triplets, where the cost of a triplet is the Euclidean length of the minimal spanning tree of the three points. The problem is a special case of grouping and facility location problems. One common problem with GA applied to hard combinatorial optimization, like the 3MP, is to incorporate problem-dependent local search operators into the GA efficiently in order to find high-quality solutions. Small instances of the problem can be solved exactly, but for large problems, we use local optimization. We introduce several general heuristic crossover and local hill-climbing operators, and apply adaptation to choose among them. Our GA combines these operators to form an effective problem solver. It is hybridized as it incorporates local search heuristics, and it is adaptive as the individual recombination/improvement operators are fired according to their online performance. Test results show that this approach gives approximately the same or even slightly better results than our previous, fine tuned GA without adaptation. It is better than a grouping GA for the partitioning considered. The adaptive combination of operators eliminates a large set of parameters, making the method more robust, and it presents a convenient way to build a hybrid problem solver     

A differential evolution algorithm for joint replenishment problem using direct grouping and its application

There has been much work in establishing joint replenishment model and designing effective and robust algorithms. Little research has been done by direct grouping methods. In this paper, we present a differential evolution (DE) algorithm that uses direct grouping to solve joint replenishment problem (JRP). Extensive computational experiments are performed to compare the performances of the DE algorithm with results of evolutionary algorithm (GA). The experimental results indicate that the DE algorithm can find a replenishment policy that incurs a lower total cost than the GA. We also conducted a case study to test the proposed DE algorithm for the JRP. The findings suggest that the proposed model is successful in decreasing spare parts ordering costs and holding costs significantly in a power plant.