Improved genetic algorithm for the job-shop scheduling problem

In this paper, an improved genetic algorithm, called the hybrid Taguchi-genetic algorithm (HTGA), is proposed to solve the job-shop scheduling problem (JSP). The HTGA approach is a method of combining the traditional genetic algorithm (TGA), which has a powerful global exploration capability, with the Taguchi method, which can exploit the optimal offspring. The Taguchi method is inserted between crossover and mutation operations of a TGA. Then, the systematic reasoning ability of the Taguchi method is incorporated in the crossover operations to systematically select the better genes to achieve crossover, and consequently enhance the genetic algorithm. Therefore, the proposed HTGA approach possesses the merits of global exploration and robustness. The proposed HTGA approach is effectively applied to solve the famous Fisher-Thompson benchmarks of 10 jobs to 10 machines and 20 jobs to 5 machines for the JSP. In these studied problems, there are numerous local optima so that these studied problems are challenging enough for evaluating the performances of any proposed GA-based approaches. The computational experiments show that the proposed HTGA approach can obtain both better and more robust results than other GA-based methods reported recently.     

An effective hybrid genetic algorithm for the job shop scheduling problem

From the computational point of view, the job shop scheduling problem (JSP) is one of the most notoriously intractable NP-hard optimization problems. This paper applies an effective hybrid genetic algorithm for the JSP. We proposed three novel features for this algorithm to solve the JSP. Firstly, a new full active schedule (FAS) procedure based on the operation-based representation is presented to construct a schedule. After a schedule is obtained, a local search heuristic is applied to improve the solution. Secondly, a new crossover operator, called the precedence operation crossover (POX), is proposed for the operation-based representation, which can preserve the meaningful characteristics of the previous generation. Thirdly, in order to reduce the disruptive effects of genetic operators, the approach of an improved generation alteration model is introduced. The proposed approaches are tested on some standard instances and compared with other approaches. The superior results validate the effectiveness of the proposed algorithm.     

Optimization of continuous-time production planning using hybrid genetic algorithms-simulated annealing

Evolutionary algorithms are stochastic search methods that mimic the principles of natural biological evolution to produce better and better approximations to a solution and have been used widely for optimization problems. A general problem of continuous-time aggregate production planning for a given total number of changes in production rate over the total planning horizon is considered. It is very important to identify and solve the problem of continuous-time production planning horizon with varying production rates over the interval of the planning period horizon. Some of the researchers have proposed global search methods for the continuous-time aggregate production-planning problem. So far, less work is reported to solve the problem of continuous-time production planning using local search methods like genetic algorithms (GA) and simulated annealing (SA). So in this work, we propose a modified single objective evolutionary program approach, namely GA, SA, and hybrid genetic algorithms-simulated annealing (GA-SA) for continuous-time production plan problems. The results are compared with each other and it was found that the hybrid algorithm performs better.     

求解作业车间调度问题的广义粒子群优化算法

为克服传统粒子群优化算法在解决组合优化问题上的局限性,分析了其优化机理,并在此基础上提出了广义粒子群优化模型。按照此模型提出了一种求解作业车间调度问题的广义粒子群优化算法。在本算法中,利用遗传算法中的交叉操作作为粒子间的信息交换策略,利用遗传算法中的变异操作作为粒子的随机搜索策略,而粒子的局部搜索策略则采用禁忌搜索来实现。为了控制粒子的局部搜索以及向全局最优解的收敛,迭代过程中交叉概率以及禁忌搜索的最大步长都是动态变化的。实验结果表明,本算法可有效地求解作业车间调度问题,验证了广义粒子群优化模型的合理性。     

车间作业调度问题(job-shop)的一种改进遗传算法

搜索空间适应性的遗传算法(GSA)具有这样的能力,即使在不通过修改遗传算法的某些参数(倒如交叉率和变异率)的情况下,就可适应解空间的结构、并调节全局搜索和局部搜索的相互平衡.但是这种遗传算法(GSA)需有时个体特征继承率控制能力的交叉操作.文章阐述了一种改进的搜索空间适应性的遗传算法(mGSA)用于解决车间作业调度问题(JSP);这种方法不同于GSA不需要带特征继承率调节能力的交叉操作.最后通过两个benchmark问题的数字实验,展示了这种方法的的有效性;并通过与现存的遗传算法相比较,展示了这种方法有更好的结果.     

求解车间调度问题的改进型自适应遗传算法

针对作业车间调度问题,以最小化完工时间为目标,借鉴内分泌激素调节机制,提出了一种新颖的改进型自适应遗传算法.通过引入自适应交叉概率和变异概率因子,克服了传统的遗传算法在解决生产调度问题时存在的搜索精度低和收敛性难以控制等问题,并在Microsoft Visual C++6.0中实现了该算法.通过一个10工件、10机器作...     

[车间调度]混合工作日历下作业车间调度遗传进化方法

针对一类混合工作日历下的作业车间调度问题,提出了一种遗传进化方法。构建了混合工作日历下以生产周期最短为优化目标的作业车间调度优化模型;提出了基于工作日历的时间推算方法,设计了遗传算法对这类问题进行求解。算法采用基于工序的编码方式;遗传操作中采用遗传算子改进策略保证子代个体的可行性,降低了计算量;解码操作中采用了基于工作日历的时间推算方法来准确计算工序的起止时刻,并采用两种技术缩短生产周期。通过案例分析验证了所提方法的有效性。     

基于HCI-SA/GA的演化设计方法及其在布局中的应用

“人机结合”是解决复杂工程系统方案设计的重要方法。为实现这种“人机结合”给出了一种基于人机交互的混合模拟退火遗传算法(简称HCI—SA/GA算法)。该算法实现了人工方案(人工个体)与算法方案(算法个体)在基因层面的结合并共同参加算法操作(交叉、复制、变异),进而构成基于HCI—SA/GA的演化设计方法。本方法既具演化算法的特点又融合了人的经验和智慧,可用于复杂工程系统布局方案设计。最后给出以卫星舱布局设计为背景的两个数值算例,验证了本方法的可行性与有效性。     

基于遗传算法的贴片机贴装顺序优化

元件贴装顺序是决定贴片机生产效率的关键问题。针对拱架型贴片机,采用了一种遗传算法。该遗传算法有其独特的染色体编码解码方式和交叉算子。算法中的染色体根据被贴装的印刷电路板由一条或多条子链组成,染色体的一个基因代表一个取贴循环。实验结果表明,该算法可以有效解决元件贴装顺序问题。同时,分析比较了三种传统交叉算子和该交叉算子的优化结果,表明这些传统交叉算子不能有效解决该问题。     

基于混合遗传算法的车间调度问题的研究

作业车间调度问题是最困难的组合优化问题之一，也是计算机集成制造系统中的一个关键环节，在实际生产中具有广泛应用。为此，提出了实现车间调度的混合遗传算法的设计方案，把遗传算法与模拟退火算法相结合，充分发挥遗传算法良好的全局搜索能力和模拟退火算法有效避免陷入局部极小的特性。通过实验验证了基于GASA混合算法的作业车间调度方法显著提高了搜索效率，改进了收敛性能。     

A Multi-Objective Genetic Algorithm for Solving Assembly Line Balancing Problem

In this paper, a multi-objective genetic agorithm to solve assembly line balancing problems is proposed. The performance criteria considered are the number of workstations, the line efficiency, the smoothness index before trade and transfer, and the smoothness index after trade and transfer. The developed genetic algorithm is compared with six popular heuristic algorithms, namely, ranked positional weight, Kilbridge and Wester, Moodie and Young, Hoffmann precedence matrix, immediate update first fit, and rank and assign heuristic methods. For comparative evaluation, 20 networks are collected from open literature, and are used with five different cycle times. All the six heuristics and the genetic algorithm are coded in C++ language. It is found that the proposed genetic algorithm performs better in all the performance measures than the heuristics. However, the execution time for the GA is longer, because the GA searches for global optimal solutions with more iterations.     

Genetic algorithm with new encoding scheme for job shop scheduling

In so many combinatorial optimization problems, job shop scheduling problems have earned a reputation for being difficult to solve. Genetic algorithm has demonstrated considerable success in providing efficient solutions to many nonpolynomial-hard optimization problems. In the field of job shop scheduling, genetic algorithm has been intensively researched, and nine methods were proposed to encode a chromosome to represent a solution. In this paper, we proposed a novel genetic chromosome-encoding approach; in this encoding method, the operation of crossover and mutation was done in three-dimensional coded space. Some big benchmark problems were tried with the proposed three-dimensional encoding genetic algorithm for validation and the results are encouraging.     

Concept optimization for mechanical product using Genetic Algorithm

Conceptual design is the first step in the overall process of product design. Its intrinsic uncertainty, imprecision, and lack of information lead to the fact that current conceptual design activities in engineering have not been computerized and very few CAD systems are available to support conceptual design. In most of the current intelligent design systems, approach of principle synthesis, such as morphology matrix, bond graphic, or design catalogues, is usually adopted to deal with the concept generation, in which optional concepts are generally combined and enumerated through function analysis. However, as a large number of concepts are generated, it is difficult to evaluate and optimize these design candidates using regular algorithm. It is necessary to develop a new approach or a tool to solve the concept generation. Generally speaking, concept generation is a problem of concept synthesis. In substance, this process of developing design candidate is a combinatorial optimization process, viz., the process of concept generation can be regarded as a solution for a state-place composed of multi-concepts. In this paper, genetic algorithm is utilized as a feasible tool to solve the problem of combinatorial optimizalion in concept generation, in which the encoding method of morphology matrix based on function analysis is applied, and a sequence of optimal concepts are generated through the search and iterative process which is controlled by genetic operators, including selection, crossover, mutation, and reproduction in GA. Several crucial problems on GA are discussed in this paper, such as the calculation of fitness value and the criteria for heredity termination, which have a heavy effect on selection of better concepts. The feasibility and intellectualization of the proposed approach are demonstrated with an engineering case. In this work concept generation is implemented using GA, which can facilitate not only generating several better concepts, but also selecting the best concept. Thus optimal concepts can be conveniently developed and design efficiency can be greatly improved.     

An effective hybrid graph and genetic algorithm approach to process planning optimization for prismatic parts

Computer-aided process planning is an important interface between computer-aided design and computer-aided manufacturing in computer-integrated manufacturing environments. In this paper, the complicated process planning is modeled as a combinatorial optimization problem with constraints, and a hybrid graph and genetic algorithm (GA) approach has been developed. The approach deals with process planning problems in a concurrent manner by simultaneously considering activities such as sequencing operations, selecting manufacturing resources, and determining setup plans to achieve the global optimal objective. Graph theory accompanied with matrix theory, as the basic mathematical tool for operation sequencing, is embedded into the main frame of GA. The precedence constraints between operations are formulated in an operation precedence graph (OPG). The initial population composed of all feasible solutions is generated by an elaborately designed topologic sort algorithm to the OPG. A modified crossover operator guaranteeing only feasible offspring generated is used, two types of mutation strategies are adopted, and a heuristic algorithm is applied to adjust the infeasible plan generated by the mutation operator to the feasible domain. A case study has been carried out to demonstrate the feasibility and efficiency of the proposed approach.     

大型产品结构优化问题的病毒进化遗传算法

针对一种大型产品结构的质量－成本优化问题，设计了一种病毒进化遗传算法，提出了相应的编码解码方案和适应度的计算。病毒进化遗传算法是一种协同进化算法，既实现了遗传操作在父子代群体间纵向继承进化信息进行全局搜索的功能，也实现了病毒感染操作在同一代群体中横向传播进化信息进行局部搜索的功能，从而可以比遗传算法较快获得问题的满意解。最后给出了病毒进化遗传算法的试验仿真结果。     

Hybrid evolutionary algorithm with marriage of genetic algorithm and extremal optimization for production scheduling

This paper presents a hybrid evolutionary algorithm with marriage of genetic algorithm (GA) and extremal optimization (EO) for solving a class of production scheduling problems in manufacturing. The scheduling problem, which is derived from hot rolling production in steel industry, is characterized by two major requirements: (i) selecting a subset of orders from manufacturing orders to be processed; (ii) determining the optimal production sequence under multiple constraints, such as sequence-dependant transition costs, non-execution penalties, earliness/tardiness (E/T) penalties, etc. A combinatorial optimization model is proposed to formulate it mathematically. For its NP-hard complexity, an effective hybrid evolutionary algorithm is developed to solve the scheduling problem through combining the population-based search capacity of GA and the fine-grained local search efficacy of EO. The experimental results with production scale data demonstrate that the proposed hybrid evolutionary algorithm can provide superior performances in scheduling quality and computation efficiency.     

基于并行协同进化遗传算法的多协作车间计划调度

为求解多协作车间的计划调度问题,提出了并行协同进化遗传算法。该算法采用基于工序的染色体编码方案。在遗传操作过程中,首先利用提出的基于工序约束的基因调整算法进行交叉操作和变异操作,保证了新个体满足工序约束。在解码操作过程中,采用考虑设备能力空间的解码算法,使得解码产生的调度为活动调度。此外,运用协同进化的思想,提出了协同适应值计算的算法,使协作环境的变化能灵敏地反映在个体的适应值上,从而有效地指导种群的进化。实例表明,该算法能够满足多协作车间并行协同调度的要求。     

贪心遗传算法求解组合优化问题

许多问题最终可以归结为求解一个组合优化问题,GA是求解组合优化问题的一个强有力的工具,但遗传算法在应用中常出现收敛过慢和封闭竞争问题,本文提出贪心遗传算法。该算法的初始种群建立、交叉和变异等过程,都引入贪心选择策略指导搜索;移民操作向种群引进新的遗传物质,克服了封闭竞争缺点。贪心遗传算法可以避免早熟收敛并改进算法的性能,算法搜索起步阶段的效率是非常高的,本文通过TSP问题仿真试验证明了算法的有效性,在较少的计算量下,得到令人满意的结果。     

RESEARCH ON THE MINIMUM ZONE CYLINDRICITY EVALUATION BASED ON GENETIC ALGORITHMS

A genetic algorithm (GA)-based method is proposed to solve the nonlinear optimization problem of minimum zone cylindricity evaluation. First, the background of the problem is introduced. Then the mathematical model and the fitness function are derived from the mathematical definition of dimensioning and tolerancing principles. Thirdly with the least squares solution as the initial values, the whole implementation process of the algorithm is realized in which some key techniques, for example, variables representing, population initializing and such basic operations as selection, crossover and mutation, are discussed in detail. Finally, examples are quoted to verify the proposed algorithm. The computation results indicate that the GA-based optimization method performs well on cylindricity evaluation. The outstanding advantages conclude high accuracy, high efficiency and capabilities of solving complicated nonlinear and large space problems.