A tutorial survey of job-shop scheduling problems using genetic algorithms-I. representation

Job-shop scheduling problem (abbreviated to JSP) is one of the well-known hardest combinatorial optimization problems. During the last three decades, the problem has captured the interest of a significant number of researchers and a lot of literature has been published, but no efficient solution algorithm has been found yet for solving it to optimality in polynomial time. This has led to recent interest in using genetic algorithms (GAs) to address it. The purpose of this paper and its companion (Part II: Hybrid Genetic Search Strategies) is to give a tutorial survey of recent works on solving classical JSP using genetic algorithms. In Part I, we devote our attention to the representation schemes proposed for JSP. In Part II, we will discuss various hybrid approaches of genetic algorithms and conventional heuristics. The research works on GA/JSP provide very rich experiences for the constrained combinatorial optimization problems. All of the techniques developed for JSP may be useful for other scheduling problems in modern flexible manufacturing systems and other combinatorial optimization problems.     

A genetic algorithm-based solution methodology for modular design

Combinatorial optimization problems usually have a finite number of feasible solutions. However, the process of solving these types of problems can be a very long and tedious task. Moreover, the cost and time for getting accurate and acceptable results is usually quite large. As the complexity and size of these problems grow, the current methods for solving problems such as the scheduling problem or the classification problem have become obsolete, and the need for an efficient method that will ensure good solutions for these complicated problems has increased. This paper presents a genetic algorithm (GA)-based method used in the solution of a set of combinatorial optimization problems. A definition of a combinatorial optimization problem is first given. The definition is followed by an introduction to genetic algorithms and an explanation of their role in solving combinatorial optimization problems such as the traveling salesman problem. A heuristic GA is then developed and used as a tool for solving various combinatorial optimization problems such as the modular design problem. A modularity case study is used to test and measure the performance of the developed algorithm.     

A new evolutionary approach to cutting stock problems with and without contiguity

Evolutionary algorithms (EAs) have been applied to many optimization problems successfully in recent years. The genetic algorithm (GAs) and evolutionary programming (EP) are two different types of EAs. GAs use crossover as the primary search operator and mutation as a background operator, while EP uses mutation as the primary search operator and does not employ any crossover. This paper proposes a novel EP algorithm for cutting stock problems with and without contiguity. Two new mutation operators are proposed. Experimental studies have been carried out to examine the effectiveness of the EP algorithm. They show that EP can provide a simple yet more effective alternative to GAs in solving cutting stock problems with and without contiguity. The solutions found by EP are significantly better (in most cases) than or comparable to those found by GAs.Scope and purposeThe one-dimensional cutting stock problem (CSP) is one of the classical combinatorial optimization problems. While most previous work only considered minimizing trim loss, this paper considers CSPs with two objectives. One is the minimization of trim loss (i.e., wastage). The other is the minimization of the number of stocks with wastage, or the number of partially finished items (pattern sequencing or contiguity problem). Although some traditional OR techniques (e.g., programming based approaches) can find the global optimum for small CSPs, they are impractical to find the exact global optimum for large problems due to combinatorial explosion. Heuristic techniques (such as various hill-climbing algorithms) need to be used for large CSPs. One of the heuristic algorithms which have been applied to CSPs recently with success is the genetic algorithm (GA). This paper proposes a much simpler evolutionary algorithm than the GA, based on evolutionary programming (EP). The EP algorithm has been shown to perform significantly better than the GA for most benchmark problems we used and to be comparable to the GA for other problems.     

Bacterial Foraging Optimization Approach to Portfolio Optimization

In this paper we propose a heuristic approach based on bacterial foraging optimization (BFO) in order to find the efficient frontier associated with the portfolio optimization (PO) problem. The PO model with cardinality and bounding constraints is a mixed quadratic and integer programming problem for which no exact algorithms can solve in an efficient way. Consequently, various heuristic algorithms, such as genetic algorithms and particle swarm optimization, have been proposed in the past. This paper aims to examine the potential of a BFO algorithm in solving the PO problem. BFO is a new swarm intelligence technique that has been successfully applied to several real world problems. Through three operations, chemotaxis, reproduction, and elimination-dispersal, the proposed BFO algorithm can effectively solve a PO problem. The performance of the proposed approach was evaluated in computational tests on five benchmark data sets, and the results were compared to those obtained from existing heuristic algorithms. The proposed BFO algorithm is found to be superior to previous heuristic algorithms in terms of solution quality and time.     

基于遗传算法的多用户检测技术分析

CDMA移动通信系统中的最优多用户检测问题是一个NP完备组合优化问题,遗传算法是求解这类问题的有效方法。通过分析CDMA系统多用户检测模型,对几种基于不同遗传算法的多用户检测方法的检测性能进行了实验仿真。仿真结果表明：基于多种群并行进化的分布式遗传算法更适合于多用户检测技术,具有较低的误码率和较强的抗远近效应能力。     

PBIL算法在组合优化问题中的应用研究

基于群体的增量学习(PBIL)算法有效结合了遗传算法和竞争学习的优点,运行过程简单,解决问题快速准确。本文提出将PBIL算法应用于求解CMN组合优化问题,以物流中心选址优化问题为例,介绍了基于PBIL求解CMN组合优化问题的一般方法,提出了针对此类问题的个体产生算法。为了提高算法的收敛速度和寻优能力,提出了基于当代最优解与历代最优解比较结果的概率学习加速方法。最后,通过实验仿真验证了上述改进的有效性。     

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.     

An evolutionary tabu search for cell image segmentation

Many engineering problems can be formulated as optimization problems. It has become more and more important to develop an efficient global optimization technique for solving these problems. In this paper, we propose an evolutionary tabu search (ETS) for cell image segmentation. The advantages of genetic algorithms (GA) and TS algorithms are incorporated into the proposed method. More precisely, we incorporate "the survival of the fittest" from evolutionary algorithms into TS. The method has been applied to the segmentation of several kinds of cell images. The experimental results show that the new algorithm is a practical and effective one for global optimization; it can yield good, near-optimal solutions and has better convergence and robustness than other global optimization approaches.     

求解混杂生产调度问题的嵌套混合蚁群算法

蚁群算法作为解决优化问题的有力工具,它的有效性已经得到了证明.由于其生物学背 景,基本蚁群算法被设计来求解复杂的排序类型组合优化问题,在连续空间优化问题的求解方面 研究很少.本文提出一种嵌套混合蚁群算法,用于解决具有混杂变量类型的复杂生产调度问题, 在一种新的最佳路径信息素更新算法的基础上,提高了搜索效率.计算机仿真结果表明,本文提 出的方法在求解此类问题上性能优于另一种基于进化计算的有效方法--遗传算法.     

A new hybrid GA solution to combinatorial optimization problems— an application to the multiprocessor scheduling problem

The multiprocessor scheduling problem is one of the classic examples of NP-hard combinatorial optimization problems. Several polynomial time optimization algorithms have been proposed for approximating the multiprocessor scheduling problem. In this paper, we suggest a geneticizedknowledge genetic algorithm (gkGA) as an efficient heuristic approach for solving the multiprocessor scheduling and other combinatorial optimization problems. The basic idea behind the gkGA approach is that knowledge of the heuristics to be used in the GA is also geneticized alongiside the genetic chromosomes. We start by providing four conversion schemes based on heuristics for converting chromosomes into priority lists. Through experimental evaluation, we observe that the performance of our GA based on each of these schemes is instance-dependent. However, if we simultaneously incorporate these schemes into our GA through the gkGA approach, simulation results show that the approach is not problem-dependent, and that the approach outperforms that of the previous GA. We also show the effectiveness of the gkGA approach compared with other conventional schemes through experimental evaluation. This work was presented, in part, at the Second International Symposium on Artifiical Life and Robotics, Oita, Japan, February 18–20, 1997     

玻璃排版优化中遗传算法的应用

研究了应用遗传算法求解非线性多目标组合优化问题———玻璃排版优化问题 ,详细讲解了如何设计求解该优化系统中三个典型组合优化子问题的遗传算法 ,并对三个子问题的求解关系进行了分析 ,总结出遗传算法的不同构造方法对系统优化结果的影响。     

Genetic algorithms to solve the cover printing problem

Inspired by successful application of evolutionary algorithms to solving difficult optimization problems, we explore in this paper, the applicability of genetic algorithms (GAs) to the cover printing problem, which consists in the grouping of book covers on offset plates in order to minimize the total production cost. We combine GAs with a linear programming solver and we propose some innovative features such as the “unfixed two-point crossover operator” and the “binary stochastic sampling with replacement” for selection. Two approaches are proposed: an adapted genetic algorithm and a multiobjective genetic algorithm using the Pareto fitness genetic algorithm. The resulting solutions are compared. Some computational experiments have also been done to analyze the effects of different genetic operators on both algorithms.     

求解多维0—1背包问题的混合遗传算法

文章研究一类典型的组合优化问题——多维０－１背包问题,提出了在简单遗传算法（ＳＧＡ）中加入局部搜索机制的混合遗传算法（ＨＧＡ）来求解该类问题,并在大量数值实验的基础上,将ＨＧＡ与传统的求解方法及ＳＧＡ进行了比较,实验的结果表明,该算法具有一定的优越性。     

Local Search-based Hybrid Algorithms for Finding Golomb Rulers

The Golomb ruler problem is a very hard combinatorial optimization problem that has been tackled with many different approaches, such as constraint programming (CP), local search (LS), and evolutionary algorithms (EAs), among other techniques. This paper describes several local search-based hybrid algorithms to find optimal or near-optimal Golomb rulers. These algorithms are based on both stochastic methods and systematic techniques. More specifically, the algorithms combine ideas from greedy randomized adaptive search procedures (GRASP), scatter search (SS), tabu search (TS), clustering techniques, and constraint programming (CP). Each new algorithm is, in essence, born from the conclusions extracted after the observation of the previous one. With these algorithms we are capable of solving large rulers with a reasonable efficiency. In particular, we can now find optimal Golomb rulers for up to 16 marks. In addition, the paper also provides an empirical study of the fitness landscape of the problem with the aim of shedding some light about the question of what makes the Golomb ruler problem hard for certain classes of algorithm.     

Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms

The well-known one-dimensional Bin Packing Problem (BPP) of whose variants arise in many real life situations is a challenging NP-Hard combinatorial optimization problem. Metaheuristics are widely used optimization tools to find (near-) optimal solutions for solving large problem instances of BPP in reasonable running times. With this study, we propose a set of robust and scalable hybrid parallel algorithms that take advantage of parallel computation techniques, evolutionary grouping genetic metaheuristics, and bin-oriented heuristics to obtain solutions for large scale one-dimensional BPP instances. A total number of 1318 benchmark problems are examined with the proposed algorithms and it is shown that optimal solutions for 88.5% of these instances can be obtained with practical optimization times while solving the rest of the problems with no more than one extra bin. When the results are compared with the existing state-of-the-art heuristics, the developed parallel hybrid grouping genetic algorithms can be considered as one of the best one-dimensional BPP algorithms in terms of computation time and solution quality.     

Approximated set-valued mapping approach for handling multiobjective bilevel problems

A significant amount of research has been done on bilevel optimization problems both in the realm of classical and evolutionary optimization. However, the multiobjective extensions of bilevel programming have received relatively little attention from researchers in both the domains. The existing algorithms are mostly brute-force nested strategies, and therefore computationally demanding. In this paper, we develop insights into multiobjective bilevel optimization through theoretical progress made in the direction of parametric multiobjective programming. We introduce an approximated set-valued mapping procedure that would be helpful in the development of efficient evolutionary approaches for solving these problems. The utility of the procedure has been emphasized by incorporating it in a hierarchical evolutionary framework and assessing the improvements. Test problems with varying levels of complexity have been used in the experiments.     

基于基因表达式编程的TSP问题求解

利用遗传算法求解组合优化问题时,需要特有的遗传算子,才能在候选解空间中有效搜索和进化。基因表达式编程（GEP）是进化计算家族的新成员。旅游商问题（TSP）是典型的组合优化问题,得到了广泛的研究,它的研究成果将对求解NP类问题产生重要影响。基于基因表达式编程（GEP）来解决TSP问题,引入适用组合优化的遗传算子：逆串,基因串的删/插等,最后进行了实验,展示GEP解决TSP问题的方法。实验表明GEP能有效解决TSP问题,设计的系统是强壮健康,其求解速度快且解的质量好。     

基于单亲遗传算法的RoboCup动态角色分配

RoboCup的机器人动态角色分配问题是一个典型的组合优化问题。解决这一问题的传统方法是贪心法,但贪心法易陷入局部最优解。提出用针对组合优化问题而构造的序号编码单亲遗传算法解决RoboCup的机器人动态角色分配问题。单亲遗传算法借鉴了传统遗传算法“优胜劣汰”的自然选择机制,但只通过单个体繁殖后代,在解决组合优化问题和复杂工程优化问题方面具有明显的优越性。试验结果显示这种方法的在解决RoboCup机器人动态角色分配问题时的有效性。     

A hybrid heuristic to solve the parallel machines job-shop scheduling problem

This paper presents an advanced software system for solving the flexible manufacturing systems (FMS) scheduling in a job-shop environment with routing flexibility, where the assignment of operations to identical parallel machines has to be managed, in addition to the traditional sequencing problem. Two of the most promising heuristics from nature for a wide class of combinatorial optimization problems, genetic algorithms (GA) and ant colony optimization (ACO), share data structures and co-evolve in parallel in order to improve the performance of the constituent algorithms. A modular approach is also adopted in order to obtain an easy scalable parallel evolutionary-ant colony framework. The performance of the proposed framework on properly designed benchmark problems is compared with effective GA and ACO approaches taken as algorithm components.     

A review of the current applications of genetic algorithms in assembly line balancing

Most of the problems involving the design and plan of manufacturing systems are combinatorial and NP-hard. A well-known manufacturing optimization problem is the assembly line balancing problem (ALBP). Due to the complexity of the problem, in recent years, a growing number of researchers have employed genetic algorithms. In this article, a survey has been conducted from the recent published literature on assembly line balancing including genetic algorithms. In particular, we have summarized the main specifications of the problems studied, the genetic algorithms suggested and the objective functions used in evaluating the performance of the genetic algorithms. Moreover, future research directions have been identified and are suggested.