A new genetic algorithm for the machine/part grouping problem involving processing times and lot sizes

This paper reports a new genetic algorithm (GA) for solving a general machine/part grouping (GMPG) problem. In the GMPG problem, processing times, lot sizes and machine capacities are all explicitly considered. To evaluate the solution quality of this type of grouping problems, a generalized grouping efficacy index is used as the performance measure and fitness function of the proposed genetic algorithm. The algorithm has been applied to solving several well-cited problems with randomly assigned processing times to all the operations. To examine the effects of the four major factors, namely parent selection, population size, mutation rate, and crossover points, a large grouping problem with 50 machines and 150 parts has been generated. A multi-factor (3⁴) experimental analysis has been carried out based on 324 GA solutions. The multi-factor ANOVA test results clearly indicate that all the four factors have a significant effect on the grouping output. It is also shown that the interactions between most of the four factors are significant and hence their cross effects on the solution should be also considered in solving GMPG problems.     

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.     

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.     

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.     

Generalized machine cell formation considering material flow and plant layout using modified self-organizing feature maps

In this paper, we develop a new generalized machine cell formation technique considering production sequences, lot sizes, processing times, of machine grouping, and the plant layout via the self-organizing feature maps (SOFM). In particular, second layer node architecture is construct to reflect the above factors. From the result of SOFM learning, a generalized machine cell formation matrix is obtained such that the material flow is reduced and the spacial restriction for the layout is reasonably considered. The adopted performance measures include the recovery ratio of bond energy, the grouping efficacy, the total inter-cell movement, and the computational time. The results are compared with the ranl order clustering method (ROC), the direct clustering analysis method (DCA), and the spark clustering analysis. The experimental result shows that the proposed method performs well in the sense of material flow reduction and layout efficiency, as well as in the sense of robustness and some other functionalities.     

向量分组聚集计算技术研究

分组聚集计算是OLAP重要的操作符之一,分组聚集操作是一种数据密集型负载。在内存数据库和GPU数据库应用场景下不仅需要研究其性能优化技术,还需要研究如何优化分配分组聚集计算执行场地以最小化CPU与GPU之间的数据传输代价。针对异构计算平台的硬件特征提出了向量聚集计算技术,将位于传统流水线末端的分组聚集计算按照“早分组,晚聚集”策略进行分解与下推,实现将数据密集型的分组聚集计算从流水线中分离,将操作与处理器计算特性优化匹配,实现异构计算平台上最优的负载分配。通过将传统基于哈希分组的聚集计算转换为向量分组聚集计算,显著提升了分组聚集计算性能。实验结果表明,向量分组聚集技术相对于具有代表性的高性能内存数据库Hyper、GPU数据库MapD最大达到5~8倍的性能提升。向量聚集计算不仅提高了OLAP聚集计算性能,而且实现了将数据密集型负载从查询计划中分离的目标,使异构计算平台能够根据处理器的硬件特性优化配置计算资源,提高异构计算平台OLAP的整体性能。     

A linguistic approach to non-identical parallel processor scheduling with fuzzy processing times

This study presents an application of non-identical parallel processor scheduling under uncertain operation times. We have been motivated from a real case scheduling problem that contains some uncommon welding operations to be processed by workers in an automotive subcontract company. Here each operator may weld each job but in different processing times depending on learning effect because of operator’s ability and experience, and batch sizes. To determine the crisp operation times in such a fuzzy environment, a linguistic reasoning approach (with a 75-“If- Then” rules) considering the learning effect is proposed in the study. Since the fuzzy linguistic approach allows the representation of expert information more directly and adequately, it can be more possible to make realistic schedules under uncertainty. With the objective to balance the workload among all operators, the longest processing time heuristic algorithm is been used and measured average makespan. For evaluating the effectiveness of this approach, it is compared with the scheduling method that use the random operation times generated from a uniform distribution. Results showed that the proposed fuzzy linguistic scheduling approach has balanced the workload of operators with a standard deviation of 0.37 and improved the Cmax value as 16%. A general conclusion can be drawn the proposed approach is able to generate realistic schedules and especially useful to solve non-identical parallel processor scheduling problem under uncertainty. An important contribution of this study is that Mamdani inference method with learning effect is the first time used to obtain the crisp processing times of non-identical processors by the help of a rule base with expert knowledge.     

Lot-sizing and cyclic scheduling for multiple products in a flow shop

This paper considers a production-inventory system in which optimal batch sizes are determined for n products that are processed on m machines in a flow shop. The total cost function for this system is derived by considering three cost components: inventory cost in work-in-process, the final products inventory cost and the machine setup labor cost. In order to make the optimal solution realizable, it is assumed that all products have the same processing cycle time. The capacity constraint considered during the derivation of the optimal lot sizes acts as an additional constraint. Two heuristic algorithms are developed in order to obtain the optimal solution. An important part of these algorithms is the modeling of the recursive relations among the production waiting times and machine idle times. These algorithms are not only used in deriving the optimal solution but also in providing the production schedules. A numerical example is also demonstrated along with the conclusion and indication for future research.     

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.     

A decision support tool to facilitate the design of cellular manufacturing layouts

This paper presents a decision support tool that can be used by practitioners and industrialists to solve practical cell formation problems. The tool is based on a cell formation algorithm that employs a set of heuristic rules to obtain a quasi-optimal solution from both component routing information and other significant production data. The algorithm has been tested on a number of data sets obtained from the literature. The test results have demonstrated that in many cases the algorithm has produced an exceptional performance in terms of the grouping efficiency, grouping efficacy and quality index measures. The algorithm, to an extent, overcomes common problems in existing cell formation methods such as in dealing with ill-structured matrices and achieving rational cell sizes.     

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

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.     

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

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

Large machine-part family formation utilizing a parallel ART1 neural network

The binary adaptive resonance (ART1) neural network algorithm has been successfully implemented in the past for the classifying and grouping of similar vectors from a machine-part matrix. A modified ART1 paradigm which reorders the input vectors, along with a modified procedure for storing a group's representation vectors, has proven successful in both speed and functionality in comparison to former techniques. This paradigm has been adapted and implemented on a neuro-computer utilizing 256 processors which allows the computer to take advantage of the inherent parallelism of the ART1 algorithm. The parallel implementation results in tremendous improvements in the speed of the machine-part matrix optimization. The machine-part matrix was initially limited to 65,536 elements (256×256) which is a consequence of the maximum number of processors within the parallel computer. The restructuring and modification of the parallel implementation has allowed the number of matrix elements to increase well beyond their previous limits. Comparisons of the modified structure with both the serial algorithm and the initial parallel implementation are made. The advantages of using a neural network approach in this case are discussed.     

A GRASP approach for makespan minimization on parallel batch processing machines

In this paper we consider the problem of scheduling a set of identical batch processing machines arranged in parallel. A Greedy Randomized Adaptive Search Procedure (GRASP) approach is proposed to minimize the makespan under the assumption of non-zero job ready times, arbitrary job sizes and arbitrary processing times. Each machine can process simultaneously several jobs as a batch as long as the machine capacity is not violated. The batch processing time is equal to the largest processing time among those jobs in the batch. Similarly, the batch ready time is equal to the largest ready time among those jobs in the batch. The performance of the proposed GRASP approach was evaluated by comparing its results to a lower bound and heuristics published in the literature. Experimental study suggests that the solution obtained from the GRASP approach is superior compared to other heuristics.     

Feature Selection Using Grey Wolf Optimization with Random Differential Grouping

Big data are regarded as a tremendous technology for processing a huge variety of data in a short time and with a large storage capacity. The user’s access over the internet creates massive data processing over the internet. Big data require an intelligent feature selection model by addressing huge varieties of data. Traditional feature selection techniques are only applicable to simple data mining. Intelligent techniques are needed in big data processing and machine learning for an efficient classification. Major feature selection algorithms read the input features as they are. Then, the features are preprocessed and classified. Here, an algorithm does not consider the relatedness. During feature selection, all features are misread as outputs. Accordingly, a less optimal solution is achieved. In our proposed research, we focus on the feature selection by using supervised learning techniques called grey wolf optimization (GWO) with decomposed random differential grouping (DrnDG-GWO). First, decomposition of features into subsets based on relatedness in variables is performed. Random differential grouping is performed using a fitness value of two variables. Now, every subset is regarded as a population in GWO techniques. The combination of supervised machine learning with swarm intelligence techniques produces best feature optimization results in this research. Once the features are optimized, we classify using advanced kNN process for accurate data classification. The result of DrnDG-GWO is compared with those of the standard GWO and GWO with PSO for feature selection to compare the efficiency of the proposed algorithm. The accuracy and time complexity of the proposed algorithm are 98% and 5 s, which are better than the existing techniques.     

CLSP问题的周期调度方法及其PSO求解

采用分解思想考虑多阶段CLSP问题,从多阶段生产系统抽象出单阶段生产环节,提出以周期方式对该生产环节进行生产批量调度。在对CLSP周期调度问题进行描述和界定的基础上,建立了相应的数学模型,讨论了周期调度方法中的周期上界以及周期长度与物料批量大小之间的关系等性质,采用基于三层编码的粒子群优化算法进行问题求解。源于冷轧生产实际的计算实例表明周期方法能够大大降低问题的规模且所得设备调整费用比人工方法减少约16%。     

Performance comparison of two-dimensional clustering algorithms in group technology

In this study, seven two-dimensional clustering algorithms are programmed and tested under various sizes of the machine-part incidence matrix. The evaluation of the algorithm is done on the basis of six performance criteria. As a result, well-known algorithms such as the Direct Clustering Algorithm and P-median method perform better than other selected algorithms.     

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

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