A hybrid genetic algorithm for the job shop scheduling problems

The Job Shop Scheduling Problem (JSSP) is one of the most general and difficult of all traditional scheduling problems. The goal of this research is to develop an efficient scheduling method based on genetic algorithm to address JSSP. We design a scheduling method based on Single Genetic Algorithm (SGA) and Parallel Genetic Algorithm (PGA). In the scheduling method, the representation, which encodes the job number, is made to be always feasible, the initial population is generated through integrating representation and G&T algorithm, the new genetic operators and selection method are designed to better transmit the temporal relationships in the chromosome, and island model PGA are proposed. The scheduling methods based on genetic algorithm are tested on five standard benchmark JSSP. The results are compared with other proposed approaches. Compared to traditional genetic algorithm, the proposed approach yields significant improvement in solution quality. The superior results indicate the successful incorporation of a method to generate initial population into the genetic operators.     

A hybrid genetic algorithm for no-wait job shop scheduling problems

A no-wait job shop (NWJS) describes a situation where every job has its own processing sequence with the constraint that no waiting time is allowed between operations within any job. A NWJS problem with the objective of minimizing total completion time is a NP-hard problem and this paper proposes a hybrid genetic algorithm (HGA) to solve this complex problem. A genetic operation is defined by cutting out a section of genes from a chromosome and treated as a subproblem. This subproblem is then transformed into an asymmetric traveling salesman problem (ATSP) and solved with a heuristic algorithm. Subsequently, this section with new sequence is put back to replace the original section of chromosome. The incorporation of this problem-specific genetic operator is responsible for the hybrid adjective. By doing so, the course of the search of the proposed genetic algorithm is set to more profitable regions in the solution space. The experimental results show that this hybrid genetic algorithm can accelerate the convergence and improve solution quality as well.     

A two-stage hybrid memetic algorithm for multiobjective job shop scheduling

In this paper we address multiobjective job shop scheduling problems. After several decades of research in scheduling problems, a variety of heuristics have been developed. The proposed algorithm is a hybrid of three frequently applied ones: the dispatching rule, the shifting bottleneck procedure, and the evolutionary algorithm. It is a two-stage algorithm, which integrates a rule-based memetic algorithm in the first stage and a re-optimization procedure of shifting bottleneck in the second. We conduct experiments using benchmark instances found in the literature to assess the performance of the proposed method. The experimental results show that the proposed method is effective and efficient for multiobjective scheduling problems.     

求解车间作业调度问题的混合遗传算法

针对Job-Shop调度问题,将自适应遗传算法与改进的蚂蚁算法融合,提出了自适应遗传算法与蚂蚁算法混合的一种优化算法。首先利用自适应遗传算法产生初始信息素的分布,再运行改进的蚂蚁算法进行求解。该算法既发挥了自适应遗传算法和蚂蚁算法在寻优中的优势,又克服了各自的不足。实验结果表明,该算法在性能上明显优于遗传算法和蚂蚁算法,并且问题规模越大,优势越明显。     

A new hybrid genetic algorithm for job shop scheduling problem

Job shop scheduling problem is a typical NP-hard problem. To solve the job shop scheduling problem more effectively, some genetic operators were designed in this paper. In order to increase the diversity of the population, a mixed selection operator based on the fitness value and the concentration value was given. To make full use of the characteristics of the problem itself, new crossover operator based on the machine and mutation operator based on the critical path were specifically designed. To find the critical path, a new algorithm to find the critical path from schedule was presented. Furthermore, a local search operator was designed, which can improve the local search ability of GA greatly. Based on all these, a hybrid genetic algorithm was proposed and its convergence was proved. The computer simulations were made on a set of benchmark problems and the results demonstrated the effectiveness of the proposed algorithm.     

A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems

This paper addresses the flexible job shop scheduling problem (fJSP) with three objectives: min makespan, min maximal machine workload and min total workload. We developed a hybrid genetic algorithm (GA) for the problem. The GA uses two vectors to represent solutions. Advanced crossover and mutation operators are used to adapt to the special chromosome structure and the characteristics of the problem. In order to strengthen the search ability, individuals of GA are first improved by a variable neighborhood descent (VND), which involves two local search procedures: local search of moving one operation and local search of moving two operations. Moving an operation is to delete the operation, find an assignable time interval for it, and allocate it in the assignable interval. We developed an efficient method to find assignable time intervals for the deleted operations based on the concept of earliest and latest event time. The local optima of moving one operation are further improved by moving two operations simultaneously. An extensive computational study on 181 benchmark problems shows the performance of our approach.     

一种求解双目标job shop问题的混合进化算法

提出一种求解双目标job shop排序问题的混合进化算法．该算法采用改进的精英复制策略,降低了计算复杂性;通过引入递进进化模式,避免了算法的早熟;通过递进过程中的非劣解邻域搜索,增强了算法局部搜索性能．采用该算法和代表性算法NSGA-Ⅱ,MOGLS对82个标准双目标job shop算例进行优化对比,所得结果验证了该算法求解双目标job shop排序问题的有效性．     

An efficient search method for multi-objective flexible job shop scheduling problems

Flexible job shop scheduling is very important in both fields of production management and combinatorial optimization. Owing to the high computational complexity, it is quite difficult to achieve an optimal solution to this problem with traditional optimization approaches. Motivated by some empirical knowledge, we propose an efficient search method for the multi-objective flexible job shop scheduling problems in this paper. Through the work presented in this work, we hope to move a step closer to the ultimate vision of an automated system for generating optimal or near-optimal production schedules. The final experimental results have shown that the proposed algorithm is a feasible and effective approach for the multi-objective flexible job shop scheduling problems.     

The hybrid heuristic genetic algorithm for job shop scheduling

Scheduling for the job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization methods owing to the high computational complexity (NP-hard). Genetic algorithms (GA) have been proved to be effective for a variety of situations, including scheduling and sequencing. Unfortunately, its efficiency is not satisfactory. In order to make GA more efficient and practical, the knowledge relevant to the problem to be solved is helpful. In this paper, a kind of hybrid heuristic GA is proposed for problem n/m/G/C_max, where the scheduling rules, such as shortest processing time (SPT) and MWKR, are integrated into the process of genetic evolution. In addition, the neighborhood search technique (NST) is adopted as an auxiliary procedure to improve the solution performance. The new algorithm is proved to be effective and efficient by comparing it with some popular methods, i.e. the heuristic of neighborhood search, simulated annealing (SA), and traditional GA.     

Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling

Fuzzy flexible job shop scheduling problem (FfJSP) is the combination of fuzzy scheduling and flexible scheduling in job shop environment, which is seldom investigated for its high complexity. We developed an effective co-evolutionary genetic algorithm (CGA) for the minimization of fuzzy makespan. In CGA, the chromosome of a novel representation consists of ordered operation list and machine assignment string, a new crossover operator and a modified tournament selection are proposed, and the population of job sequencing and the population of machine assignment independently evolve and cooperate for converging to the best solutions of the problem. CGA is finally applied and compared with other algorithms. Computational results show that CGA outperforms those algorithms compared.     

An improved intelligent water drops algorithm for solving multi-objective job shop scheduling

Multi-objective job shop scheduling (MOJSS) problems can be found in various application areas. The efficient solution of MOJSS problems has received continuous attention. In this research, a new meta-heuristic algorithm, namely the Intelligent Water Drops (IWD) algorithm is customized for solving the MOJSS problem. The optimization objective of MOJSS in this research is to find the best compromising solutions (Pareto non-dominance set) considering multiple criteria, namely makespan, tardiness and mean flow time of the schedules. MOJSS-IWD, which is a modified version of the original IWD algorithm, is proposed to solve the MOJSS problem. A scoring function which gives each schedule a score based on its multiple criteria values is embedded into the MOJSS-IWD’s local search process. Experimental evaluation shows that the customized IWD algorithm can identify the Pareto non-dominance schedules efficiently.     

A hybrid genetic tabu search algorithm for solving job shop scheduling problems: a case study

In recent decades many attempts have been made at the solution of Job Shop Scheduling Problem using a varied range of tools and techniques such as Branch and Bound at one end of the spectrum and Heuristics at the other end. However, the literature reviews suggest that none of these techniques are sufficient on their own to solve this stubborn NP-hard problem. Hence, it is postulated that a suitable solution method will have to exploit the key features of several strategies. We present here one such solution method incorporating Genetic Algorithm and Tabu Search. The rationale behind using such a hybrid method as in the case of other systems which use GA and TS is to combine the diversified global search and intensified local search capabilities of GA and TS respectively. The hybrid model proposed here surpasses most similar systems in solving many more traditional benchmark problems and real-life problems. This, the system achieves by the combined impact of several small but important features such as powerful chromosome representation, effective genetic operators, restricted neighbourhood strategies and efficient search strategies along with innovative initial solutions. These features combined with the hybrid strategy employed enabled the system to solve several benchmark problems optimally, which has been discussed elsewhere in Meeran and Morshed (8th Asia Pacific industrial engineering and management science conference, Kaohsiung, Taiwan, 2007). In this paper we bring out the system’s practical usage aspect and demonstrate that the system is equally capable of solving real life Job Shop problems.     

遗传算法求解柔性job shop 调度问题

在分析柔性job shop调度问题特点的基础上，提出一种新的求解该问题的遗传算法，即利用编码方法表示各工序的优先调度顺序及工序的加工机器，由此产生可行的调度方案，使得问题的约束条件在染色体中得以体现．所设计的遗传算子不仅能避免非法调度解的出现，保证后代的多样性，而且可使算法具有记忆功能．仿真结果证明了该算法的有效性．     

A Pareto-based two-stage evolutionary algorithm for flexible job shop scheduling problem with worker cooperation flexibility

The previous studies on the flexible job shop scheduling problems (FJSP) with machine flexibility and worker flexibility normally assume that each machine is operated by one worker at any time. However, it is not accurate in many cases because many workers may be required for machines in processing complex operations. Hence, this paper studies a universal version, i.e., FJSP with worker cooperation flexibility (FJSPWC), which defines that each machine can be used only if their required workers are prepared. A mixed-integer linear programming model tuned by CPLEX is established for the problem aiming to collaboratively minimize the makespan, maximum workload of machines and maximum workload of workers. To solve the problem efficiently, a Pareto-based two-stage evolutionary algorithm (PTEA) is proposed. In the PTEA, a well-tailored initialization operator and the NSGA-II structure are designed for global exploration in the first stage, and a competitive objective-based local search operator is developed to improve its local search ability and accelerate the convergence in the second stage. Extensive experiments based on fifty-eight newly formulated benchmarks are carried out to validate the effectiveness of the well-designed initialization operator and two-stage architecture. Comprehensive experiments are performed to evaluate the proposed PTEA, and the results reveal that the PTEA is superior to four comparison algorithms concerning the distribution, convergence, and overall performance.     

超启发式遗传算法求解模糊柔性作业车间调度

本文提出一种混合超启发式遗传算法(HHGA),用于求解一类采用三角模糊数表示工件加工时间的模糊柔性作业车间调度问题(FFJSP),优化目标为最小化最大模糊完工时间(即makespan).首先,详细分析现有三角模糊数排序准则性质,并充分考虑取大操作的近似误差和模糊度,设计一种更为准确的三角模糊数排序准则,可合理计算FFJSP和其他各类调度问题解的目标函数值.其次,为实现对FFJSP解空间不同区域的有效搜索, HHGA将求解过程分为两层,高层利用带自适应变异算子的遗传算法对6种特定操作(即6种有效邻域操作)的排列进行优化;低层将高层所得的每种排列作为一种启发式算法,用于对低层相应个体进行操作来执行紧凑的变邻域局部搜索并生成新个体,同时加入模拟退火机制来避免搜索陷入局部极小.最后,仿真实验和算法比较验证了所提排序准则和HHGA的有效性.     

A Pareto archive particle swarm optimization for multi-objective job shop scheduling

In this paper, we present a particle swarm optimization for multi-objective job shop scheduling problem. The objective is to simultaneously minimize makespan and total tardiness of jobs. By constructing the corresponding relation between real vector and the chromosome obtained by using priority rule-based representation method, job shop scheduling is converted into a continuous optimization problem. We then design a Pareto archive particle swarm optimization, in which the global best position selection is combined with the crowding measure-based archive maintenance. The proposed algorithm is evaluated on a set of benchmark problems and the computational results show that the proposed particle swarm optimization is capable of producing a number of high-quality Pareto optimal scheduling plans.     

A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem

In this paper, a novel competitive co-evolutionary quantum genetic algorithm (CCQGA) is proposed for a stochastic job shop scheduling problem (SJSSP) with the objective to minimize the expected value of makespan. Three new strategies named as competitive hunter, cooperative surviving and the big fish eating small fish are developed in population growth process. Based on improved co-evolution idea of multi-population and concepts of quantum theory, this algorithm could not only adjust population size dynamically to increase the diversity of genes and avoid premature convergence, but also accelerate the convergence speed with Q-bit representation and quantum rotation gate. FT benchmark-based problems where the processing times are subjected to independent normal distributions are solved effectively by CCQGA. The experiment results achieved by CCQGA are compared with quantum-inspired genetic algorithm (QGA) and standard genetic algorithm (GA), which shows that CCQGA has better feasibility and effectiveness.     

基于工件位置交叉算子的车间作业调度算法

交叉算子是遗传算法中最主要的遗传算子,对种群的搜索性能起着重要的作用。基于操作编码的遗传算法多采用两点交叉算子,研究发现这种交叉算子收敛速度慢,容易陷入局部最优解,为此设计了一种基于工件位置的交叉算子,通过试验仿真验证了该算子在收敛速度和求全局最优解上有显著优势。