A comparison between genetic algorithms and the RAND method for solving the joint replenishment problem

The purpose of this paper is to compare the performance of genetic algorithms (GAs) and the best available heuristic, known as the RAND, for solving the joint replenishment problem (JRP). An important feature of the JRP which makes it suitable for GAs is that it can be formulated as a problem having one continuous decision variable and a number of integer decision variables equal to the number of products being produced or ordered. Experiments on randomly generated problems indicate that GAs can provide better solutions to the JRP than the RAND for some problems, and at worst can almost match the performance of the RAND from a practical point of view for the rest of the problems. GAs never converged to solution with a total cost of more than 0.08% of the total cost of the RAND for 1600 randomly generated problems. In addition, GAs have the advantages of: (i) being easy to implement (e.g. less than 200 lines of code); (ii) having a code which is easy to understand and modify; and (iii) dealing easily with constrained JRPs which are neglected by most of the available methods including the RAND, in spite of their importance in practice.     

基于多目标多元学习细菌觅食优化算法的混合数据聚类

针对混合属性数据聚类问题,本文提出一种基于多目标多元学习细菌觅食优化算法。首先,基于改进的细菌觅食优化算法,提出多目标优化算法框架。然后,提出多元学习策略来提高算法性能。具体地,对于细菌个体,细菌之间采用环形拓扑学习策略,每个细菌只能向其邻域最优个体学习;细菌个体还可以向外部档案非支配个体学习。通过该学习策略,不仅可以保持种群的多样性,也可以加快算法收敛速度。对于外部档案非支配个体,记录其变化趋势,当非支配个体的变化处于停滞状态时,采用精英学习策略对非支配个体进行微扰动,提高非支配解的多样性。最后,为解决混合属性数据聚类问题,设计了一种具有属性权重的混合属性转换策略。为了验证所提算法的性能,将该算法与两个多目标进化算法和三个经典聚类算法在六个标准数据集上进行对比实验。实验结果表明,所提算法在解决数值、分类和混合属性数据聚类问题上具有显著优势。同时,以金融领域信用卡申请客户数据为例,进一步证实了所提算法的可行性,也表明了所提算法在涉及混合属性数据集的医疗、管理、工程等领域有一定的应用前景。     

Two new robust genetic algorithms for the flowshop scheduling problem

The flowshop scheduling problem (FSP) has been widely studied in the literature and many techniques for its solution have been proposed. Some authors have concluded that genetic algorithms are not suitable for this hard, combinatorial problem unless hybridization is used. This work proposes new genetic algorithms for solving the permutation FSP that prove to be competitive when compared to many other well known algorithms. The optimization criterion considered is the minimization of the total completion time or makespan (_Cmax$C_{\max }$). We show a robust genetic algorithm and a fast hybrid implementation. These algorithms use new genetic operators, advanced techniques like hybridization with local search and an efficient population initialization as well as a new generational scheme. A complete evaluation of the different parameters and operators of the algorithms by means of a Design of Experiments approach is also given. The algorithm's effectiveness is compared against 11 other methods, including genetic algorithms, tabu search, simulated annealing and other advanced and recent techniques. For the evaluations we use Taillard's well known standard benchmark. The results show that the proposed algorithms are very effective and at the same time are easy to implement.     

A hybrid genetic algorithm for the batch sequencing problem on identical parallel machines

The batch sequencing problem (BSP) has been the focus of much research thanks to its practical applicability and NP-hard nature. This study aims to solve an extension of the problem from single machine case to parallel machine case. A dispatching rule called the EDD (Earliest Due Date)-Greedy heuristic and a pure genetic algorithm (GA) are proposed, and then combine them through an insertion method called the Gene Bank Strategy. Several test cases of up to 12 machines and 60 jobs are randomly generated and solved. Those experiments show that the introduced hybrid GA can provide far better results than its two component algorithms that can also independently solve the problem.     

A hybrid approach to constrained evolutionary computing: Case of product synthesis

Evolutionary computing (EC) is comprised of techniques involving evolutionary programming, evolution strategies, genetic algorithms (GA), and genetic programming. It has been widely used to solve optimization problems for large scale and complex systems. However, when insufficient knowledge is incorporated, EC is less efficient in terms of searching for an optimal solution. In addition, the GA employed in previous literature is modeled to solve one problem exactly. The GA needs to be redesigned, at a cost, for it to be applied to another problem. Due to these two reasons, this paper develops a generic GA incorporating knowledge extracted from the rough set theory. The advantages of the proposed solution approach include: (i) solving problems that can be decomposed into functional requirements, and (ii) improving the performance of the GA by reducing the domain range of initial population and constraining crossover using the rough set theory. The solution approach is exemplified by solving the problem of product synthesis, where there is a conflict between performance and cost. Manufacturing or assembling a product of high performance and quality at a low cost is critical for a company to maximize its advantages. Based on our experimental results, this approach has shown great promise and has reduced costs when the GA is in processing.     

Two-sided assembly line balancing: A genetic algorithm approach

A two-sided assembly line balancing problem is typically found in plants producing large-sized high-volume products, e.g. buses and trucks. The features specific to the assembly line are described in this paper, which are associated with those of: (i) two-sided assembly lines; (ii) positional constraints; and (iii) balancing at the operational time. There exists a large amount of literature in the area of line balancing, whereby it has mostly dealt with one-sided assembly lines. A new genetic algorithm is developed to solve the problem, and its applicability and extensibility are discussed. A genetic encoding and decoding scheme, and genetic operators suitable for the problem are devised. This is particularly emphasized using problem-specific information to enhance the performance of the genetic algorithm (GA). The proposed GA has a strength that it is flexible in solving various types of assembly line balancing problems. An experiment is carried out to verify the performance of the GA, and the results are reported.     

Assembly Line Balancing Using Genetic Algorithms with Heuristic-Generated Initial Populations and Multiple Evaluation Criteria*

We use genetic algorithms (GA) to solve the assembly line balancing (ALB) problem. Inparticular, we show how this technique can be used to generate feasible line balances, improve upon solutions obtained by other heuristics reported in the literature, and utilizeany one or more evaluation criteria that can be expressed in functional form. The procedure is demonstrated with two examples: (1) intimating the improvement of heuristic-generated ALB solutions by including them in the GA initial population, and (2) the possibility of balancing assembly lines with multiple criteria and side constraints. These examples suggest that GA can be a powerful tool in ALB. To investigate the utility of GA on single-criterion problems, an experiment is conducted that compares both the GA approach and conventional heuristics. Results indicate that the GA solutions are significantly improved over the heuristic solutions under the conditions studied. It is also found that the presence of heuristic-generated conventional solutions in the GA initial population leads to statistically preferred results.     

TSP in spreadsheets—A fast and flexible tool

The traveling salesman problem (TSP) is well-known and many specially developed solution procedures have been constructed to solve particular variants of it. This paper considers several different variants of TSP. However, developing tailored solution procedures for each is impractical. These problems are non-deterministic polynomial-time hard (NP hard). Solving them using standard linear programming/mixed integer programming (LP/MIP) solvers has therefore only been regarded to be feasible for very small problems. A careful consideration of the problem formulation may facilitate efficient software utilization, and for real-world problems this can have a considerable impact. Problems that were previously regarded as large and unwieldy are now easily solvable using spreadsheets, thanks to the recent advancement in general optimization software.     

基于杂合遗传算法的工艺路线可变Job Shop调度研究

提出一种将遗传算法与启发式规则、模拟退火法等搜索方法结合在一起的杂合遗传算法,用于求解工艺路线可变的JobShop调度问题。通过对某双极型集成电路封装企业的JobShop调度仿真,结果表明算法是有效和可行的。     

The role of advanced start and dominance rules in simulated annealing for parallel processor scheduling problems

Simulated annealing (SA) has been widely used to solve hard combinatorial optimization problems during the last decade. The application of SA requires the initialization of certain parameters and an initial solution to start the search with. An emphasis in the application of SA has been on the determination of the best initial values of the parameters, however, the starting solution has traditionally been randomly generated. In this paper, we study the effects of the quality of the starting solution and the use of dominance rules on the performance of SA. We show that the better the initial solution used by the SA, the better the final solution produced by it, i.e. the level of improvement achieved by the SA is dependent on the quality of the initial solution. This is demonstrated using various parallel processor scheduling problems. We have also found that dominance rules (applied in conjunction with SA) may in some cases lead to further improved solutions, but their inclusion in an SA scheme must be determined during the preliminary experimentation, in parallel to the determination of the best SA-parameter values. These findings have a long-term impact, as they suggest that the performance of SA schemes that are currently available in the literature can be further improved by starting from a good solution, if available, or by implementing SA in a sequential manner, i.e. several times, by starting from the best solution found in the previous run.     

An empirical study of design and testing of hybrid evolutionary–neural approach for classification

We propose a hybrid evolutionary–neural approach for binary classification that incorporates a special training data over-fitting minimizing selection procedure for improving the prediction accuracy on holdout sample. Our approach integrates parallel global search capability of genetic algorithms (GAs) and local gradient-descent search of the back-propagation algorithm. Using a set of simulated and real life data sets, we illustrate that the proposed hybrid approach fares well, both in training and holdout samples, when compared to the traditional back-propagation artificial neural network (ANN) and a genetic algorithm-based artificial neural network (GA-ANN).     

Some graph optimization problems with weights satisfying linear constraints

In this paper, we study several graph optimization problems in which the weights of vertices or edges are variables determined by several linear constraints, including maximum matching problem under linear constraints (max-MLC), minimum perfect matching problem under linear constraints (min-PMLC), shortest path problem under linear constraints (SPLC) and vertex cover problem under linear constraints (VCLC). The objective of these problems is to decide the weights that are feasible to the linear constraints, and find the optimal solutions of corresponding graph optimization problems among all feasible choices of weights. We find that these problems are NP-hard and are hard to be approximated in general. These findings suggest us to explore various special cases of them. In particular, we show that when the number of constraints is a fixed constant, all these problems are polynomially solvable. Moreover, if the total number of distinct weights is a fixed constant, then max-MLC, min-PMLC and SPLC are polynomially solvable, and VCLC has a 2-approximation algorithm. In addition, we propose approximation algorithms for various cases of max-MLC.

     

A simulated annealing algorithm for job shop scheduling

In this paper, the job shop scheduling problem is considered with the objective of minimization of makespan time. We first reviewed the literature on job shop scheduling using meta-heuristics. Then a simulated annealing algorithm is presented for scheduling in a job shop. To create neighbourhoods, three perturbation schemes, viz. pairwise exchange, insertion, and random insertion are used, and the effect of them on the final schedule is also compared. The proposed simulated annealing algorithm is compared with existing genetic algorithms and the comparative results are presented. For comparative evaluation, a wide variety of data sets are used. The proposed algorithm is found to perform well for scheduling in the job shop.     

工程项目资源均衡的遗传算法及其MATLAB实现

本文采用基于生物进化理论的遗传算法进行工程项目的资源均衡研究,克服了传统资源平衡算法的不足,并利用MATLAB语言进行编程实现,根据目标函数的具体要求,有效解出单资源和多资源平衡问题的最优解,同时得到每项作业的最优开始时间,通过实例分析,验证了算法的有效性和可靠性,取得了良好的效果。     

Simplicial Pivoting Algorithms for a Tractable Class of Integer Programs

We present a tractable class of integer feasibility problems. This class of max-closed IP problems was studied in somewhat restricted form by Glover, Pnueli, Hochbaum and Chandrasekaran and has a logic counterpart known as the class of Horn formulas. First we modify the existing algorithms in order to avoid the related recognition problem. Then we show that in order to solve these max-closed IP problems, simplicial path following methods can be used. This is important because these methods are flexible with respect to starting conditions, which make them more suitable than the top-down truncation algorithms that have been suggested.     

一种求解双目标flow shop排序问题的进化算法

提出一种求解双目标flow shop排序的递进多目标进化算法.算法采用改进的精英复制策略,在实现精英保留的前提下降低了计算复杂性;通过递进进化模式增加群体多样性,改善了算法收敛性;通过群体进化过程中对非劣解集进行竞争型可变邻域启发式搜索,增强了算法局部搜索性能.采用新算法和参照算法NSGA-II对31个标准双目标flow shop算例进行优化.研究结果表明,新算法在所有算例的求解中均获得了优于NSGA-II的非劣解集,验证了算法的有效性.     

Kanban optimization by simulation and evolution

The problem of the optimal design of multistage systems with Kanban control mechanism is investigated. The optimization problem generalizes those from literature by considering a general criterion function and including the lot sizes as decision variables. Since no analytical solutions can be expected simulation combined with a genetic algorithm is used. The simulator KaSimIR as well as the optimization tool LEO are briefly described. Some examples demonstrate the usability of the approach.     

基于求解TSP问题的双向扩展差额算法

旅行商(TSP)问题是典型的组合优化中的NP-hard难题.本文在最近城市搜索法和两端延伸最近城市搜索法基础上提出了双向扩展差额求解算法,并分析了算法的复杂度.采用以上三种算法求解了TSPLIB标准库中多个算例,比较结果表明本算法能够更快的找到更优的方案,具有更好的综合性能.     

A hybrid genetic algorithm for production and distribution

This paper develops a hybrid genetic algorithm for production and distribution problems in multi-factory supply chain models. Supply chain problems usually may involve multi-criterion decision-making, for example operating cost, service level, resources utilization, etc. These criteria are numerous and interrelated. To organize them, analytic hierarchy process (AHP) will be utilized. It provides a systematic approach for decision makers to assign weightings and relate them. Meanwhile, genetic algorithms (GAs) will be utilized to determine jobs allocation into suitable production plants. Genetic operators adopted to improve the genetic search algorithm will be introduced and discussed. Finally, a hypothetical production–distribution problem will be solved by the proposed algorithm. The optimization results show that it is reliable and robust.     

A genetic algorithm for scheduling on a single machine with set-up times and due dates

This paper presents a genetic algorithm for a single machine-scheduling problem with the objective of minimizing total tardiness. Each job has its own due date and the set-up times are sequence dependent. The parameters of the genetic algorithm are determined by a statistical method. For small problems, the solutions given by the proposed method are compared with solutions provided by a commercial package, and for larger problems, with those obtained by a heuristic proposed in the literature.