A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times

This paper presents a hybrid approach based on the integration between a genetic algorithm (GA) and concepts from constraint programming, multi-objective evolutionary algorithms and ant colony optimization for solving a scheduling problem. The main contributions are the integration of these concepts in a GA crossover operator. The proposed methodology is applied to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. A sensitivity analysis of the hybrid approach is carried out to compare the performance of the GA and the hybrid genetic algorithm (HGA) approaches on different benchmarks from the literature. The numerical experiments demonstrate the HGA efficiency and effectiveness which generates solutions that approach those of the known reference sets and improves several lower bounds.     

Fuzzy multiple objective optimal system design by hybrid genetic algorithm

In this paper, we propose a method for solving fuzzy multiple objective optimal system design problems with GUB structure by hybridized genetic algorithms (HGA). This approach enables the flexible optimal system design by applying fuzzy goals and fuzzy constraints. In this genetic algorithm (GA), we propose the new chromosomes representation that represents the GUB structure simply and effectively at the same time. Also, by introducing the HGA that combine the proposed heuristic algorithm that makes use of the peculiarity of GUB structure to GA, the proposed approach is efficient than the previous method in finding solution.     

基于改进遗传算法的标签印刷生产调度技术

针对标签印刷生产过程中存在的多品种、小批量、客户定制化程度高、部分生产工序存在不确定性等问题建立了以最小化最大完工时间为目标的柔性作业车间调度模型,提出了一种改进遗传算法（GA）。首先,在标准遗传算法的基础上采用整数编码;然后,在选择操作阶段采用轮盘赌法,并通过引入精英解保留策略以确保算法收敛性;最后,提出动态自适应交叉和变异概率,从而保证算法在前期进行较大范围寻优,以避免早熟,而后期尽快收敛,以保证前期获得的优良个体不被破坏。为了验证所提改进遗传算法的可行性,首先采用Ft06基准算例把所提算法与标准遗传算法（GA）进行比较,结果显示改进遗传算法的最优解（55 s）优于标准遗传算法的最优解（56 s）,且改进遗传算法的迭代次数明显优于标准遗传算法;然后通过柔性作业车间调度问题（FJSP）的8×8、10×10和15×10标准算例进一步验证了算法的稳定性和寻优性能,在3个标准测试算例上改进遗传算法均在较短时间内取得了最优解;最后,将该算法用于求解标签印刷车间的排产问题时,使得加工效率比原来提高了50.3%。因此,提出的改进遗传算法可以有效应用于求解标签印刷车间的排产问题。     

A heuristic algorithm for the distributed and flexible job-shop scheduling problem

The distributed manufacturing takes place in a multi-factory environment including several factories, which may be geographically distributed in different locations, or in a multi-cell environment including several independent manufacturing cells located in the same plant. Each factory/cell is capable of manufacturing a variety of product types. An important issue in dealing with the production in this decentralized manner is the scheduling of manufacturing operations of products (jobs) in the distributed manufacturing system. In this paper, we study the distributed and flexible job-shop scheduling problem (DFJSP) which involves the scheduling of jobs (products) in a distributed manufacturing environment, under the assumption that the shop floor of each factory/cell is configured as a flexible job shop. A fast heuristic algorithm based on a constructive procedure is developed to obtain good quality schedules very quickly. The algorithm is tested on benchmark instances from the literature in order to evaluate its performance. Computational results show that, despite its simplicity, the proposed heuristic is computationally efficient and promising for practical problems.     

An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem

An improved adaptive genetic algorithm (IAGA) for solving the minimum makespan problem of job-shop scheduling problem (JSP) is presented. Though the traditional genetic algorithm (GA) exhibits implicit parallelism and can retain useful redundant information about what is learned from previous searches by its representation in individuals in the population, yet GA may lose solutions and substructures due to the disruptive effects of genetic operators and is not easy to regulate GA’s convergence. The proposed IAGA is inspired from hormone modulation mechanism, and then the adaptive crossover probability and adaptive mutation probability are designed. The proposed IAGA is characterized by simplifying operations, high search precision, overcoming premature phenomenon and slow evolution. The proposed method by employing operation-based encoding is effectively applied to solve a dynamic job-shop scheduling problem (DJSP) and a complicated contrastive experiment of JSP in manufacturing system. Meanwhile, in order to ensure to create a feasible solution, a new method for crossover operation is adopted, named, partheno-genetic operation (PGO). The computational results validate the effectiveness of the proposed IAGA, which can not only find optimal or close-to-optimal solutions but can also obtain both better and more robust results than the existing genetic algorithms reported recently in the literature. By employing IAGA, machines can be used more efficiently, which means that tasks can be allocated appropriately, production efficiency can be improved, and the production cycle can be shortened efficiently.     

精英进化策略求解柔性作业车间调度问题

柔性作业车间调度问题允许一道工序可以在多个可选机器上进行加工,减少了机器约束,增加了求解难度,是典型的NP难问题。结合其特点,设计了一种精英进化策略遗传算法求解柔性作业车间调度问题。提出了解阀值的指标,使得外部精英库中不仅保留算法每次迭代过程中的最优解,而且保留最优值相等而调度方案不同的解,为调度人员提供更多选择。通过制造企业中的实际案例和其它文献中的案例对提出的精英进化策略遗传算法进行了测试,结果证明提出方法的有效性。     

基于模糊物元模型的高维多目标FJSP研究*

为解决高维多目标柔性作业车间调度问题,提出了一种基于模糊物元模型与粒子群算法的模糊粒子群算法（Fuzzy Particle Swarm Optimization,FPSO）。该算法以模糊物元分析理论为依据,采用复合模糊物元与基准模糊物元之间的欧式贴近度作为适应度值引导粒子群算法的进化,并引入具有容量限制的外部存储器保留较优的Pareto非支配解以供决策者选择。此外,构建了优化目标为最大完工时间、设备总负荷、加工成本、最大设备负荷与加工质量的高维多目标优化模型,并以Kacem基准问题与实际生产数据为例进行仿真模拟与对比分析。结果表明,该算法具有良好的收敛性且搜索到的非支配解分布性较好,能够有效地应用于求解高维多目标柔性作业车间调度问题。     

Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling

The expanded job-shop scheduling problem (EJSSP) is a practical production scheduling problem with processing constraints that are more restrictive and a scheduling objective that is more general than those of the standard job-shop scheduling problem (JSSP). A hybrid approach involving neural networks and genetic algorithm (GA) is presented to solve the problem in this paper. The GA is used for optimization of sequence and a neural network (NN) is used for optimization of operation start times with a fixed sequence.

After detailed analysis of an expanded job shop, new types of neurons are defined to construct a constraint neural network (CNN). The neurons can represent processing restrictions and resolve constraint conflicts. CNN with a gradient search algorithm, gradient CNN in short, is applied to the optimization of operation start times with a fixed processing sequence. It is shown that CNN is a general framework representing scheduling problems and gradient CNN can work in parallel for optimization of operation start times of the expanded job shop.

Combining gradient CNN with a GA for sequence optimization, a hybrid approach is put forward. The approach has been tested by a large number of simulation cases and practical applications. It has been shown that the hybrid approach is powerful for complex EJSSP.     

求解柔性作业车间调度问题的鸟群算法

柔性作业车间调度问题是生产调度领域中非常重要的一类带约束优化问题。根据其求解特性,提出一种基于改进的鸟群算法求解以最小化最大完工时间为目标的柔性作业车间调度问题的方法。该方法采用随机黑洞策略改进鸟群的觅食方式,自适应的动态调整策略改善鸟群的迁移步长,从而提高种群的多样性并加速算法的收敛速度;通过对关键路径上工序的领域搜索加强算法的局部搜索能力。最后利用实际制造企业的生产加工数据以及标准测试实例进行仿真实验,实验结果表明,该算法在问题的求解精度和收敛速度上具有一定的优势,是一种有效的求解柔性作业车间调度问题的新方法。     

Genetic algorithm with fuzzy logic controller for preemptive and non-preemptive job-shop scheduling problems

In this paper, we propose a new genetic algorithm (GA) with fuzzy logic controller (FLC) for dealing with preemptive job-shop scheduling problems (p-JSP) and non-preemptive job-shop scheduling problems (np-JSP). The proposed algorithm considers the preemptive cases of activities among jobs under single machine scheduling problems. For these preemptive cases, we first use constraint programming and secondly develop a new gene representation method, a new crossover and mutation operators in the proposed algorithm.However, the proposed algorithm, as conventional GA, also has a weakness that takes so much time for the fine-tuning of genetic parameters. FLC can be used for regulating these parameters.In this paper, FLC is used to adaptively regulate the crossover ratio and the mutation ratio of the proposed algorithm. To prove the performance of the proposed FLC, we divide the proposed algorithm into two cases: the GA with the FLC (pro-fGA) and the GA without the FLC (pro-GA).In numerical examples, we apply the proposed algorithms to several job-shop scheduling problems and the results applied are analyzed and compared. Various experiments show that the results of pro-fGA outperform those of pro-GA.     

An effective evolutionary algorithm for the practical capacitated vehicle routing problems

The evolutionary algorithms are extensively adopted to resolve complex optimization problem. Genetic algorithm (GA), an evolutionary algorithm, has been proved capable of solving vehicle routing problems (VRPs). However, the resolution effectiveness of GA decreases with the increase of nodes within VRPs. Normally, a hybrid GA outperforms pure GA. This study attempts to solve a capacitated vehicle routing problem (CVRP) by applying a novel hybrid genetic algorithm (HGA) that is practical for use by manufacturers. The proposed HGA involves three stages. First, a diverse and well-structured initial chromosome population was constructed. Second, response surface methodology (RSM) experiments were conducted to optimize the crossover and mutation probabilities in performing GA. Finally, a combined heuristics containing improved insertion algorithm and random insertion mutation operator was established to stir over gene permutations and enhance the exploration capability of GA diversely. Furthermore, an elitism conservation strategy was implemented that replace inferior chromosomes with superior ones. As the proposed HGA is primarily used to solve practical problems, benchmark problems involving fewer than 100 nodes from an Internet website were utilized to confirm the feasibility of the proposed HGA. Two real cases one for locally active distribution and another for arms part transportation at a combined maintenance facility, both involving the Taiwanese armed forces are used to detail the analytical process and demonstrate the practicability of the proposed HGA for optimizing the CVRP.     

A modified genetic algorithm for distributed scheduling problems

Genetic algorithms (GAs) have been widely applied to the scheduling and sequencing problems due to its applicability to different domains and the capability in obtaining near-optimal results. Many investigated GAs are mainly concentrated on the traditional single factory or single job-shop scheduling problems. However, with the increasing popularity of distributed, or globalized production, the previously used GAs are required to be further explored in order to deal with the newly emerged distributed scheduling problems. In this paper, a modified GA is presented, which is capable of solving traditional scheduling problems as well as distributed scheduling problems. Various scheduling objectives can be achieved including minimizing makespan, cost and weighted multiple criteria. The proposed algorithm has been evaluated with satisfactory results through several classical scheduling benchmarks. Furthermore, the capability of the modified GA was also tested for handling the distributed scheduling problems.     

An effective genetic algorithm for the flexible job-shop scheduling problem

In this paper, we proposed an effective genetic algorithm for solving the flexible job-shop scheduling problem (FJSP) to minimize makespan time. In the proposed algorithm, Global Selection (GS) and Local Selection (LS) are designed to generate high-quality initial population in the initialization stage. An improved chromosome representation is used to conveniently represent a solution of the FJSP, and different strategies for crossover and mutation operator are adopted. Various benchmark data taken from literature are tested. Computational results prove the proposed genetic algorithm effective and efficient for solving flexible job-shop scheduling problem.     

自适应Jaya算法求解多目标柔性车间绿色调度问题

针对多目标柔性作业车间绿色调度问题(MO-FJGSP),建立优化目标为最大完工时间、机器总负荷和能耗最小的多目标数学模型,并设计一种基于Pareto最优解的自适应多目标Jaya算法(SAMO-Jaya)对该问题进行优化求解.算法采用两级实数编码方式实现工序排序与机器分配的编码表示,并设计一种转换机制实现将Jaya连续解空间映射至FJSP离散解空间;然后设计一种混沌序列与均匀分布相结合的混合策略以提高初始种群的质量与全局分散性;此外,在Jaya算法中嵌入自适应调整种群规模的方法以提高算法求解速度.通过10个单目标与3个多目标基准算例测试,并与7个已有算法进行对比分析,结果表明SAMO-Jaya算法能够对MO-FJGSP进行有效求解.     

改进人工蜂群算法求解分布式柔性作业车间调度问题

针对分布式柔性作业车间调度问题的特点,提出一种改进人工蜂群算法.首先,建立以最小化最大完工时间为优化目标的分布式柔性作业车间调度优化模型;然后,改进基本人工蜂群算法以使其适用于求解分布式柔性作业车间调度问题,具体的改进包括设计一种包含三维向量的编码方案,结合问题特点针对性地设计多种策略用于种群初始化,在雇佣蜂改良搜索操作中设计多种有效的进化操作算子,并在跟随蜂搜索操作中引入基于关键路径的局部搜索算子以提升算法的局部搜索能力;最后,利用扩展柔性作业车间通用测试集得到的测试数据设计实验验证算法性能,使用正交试验法优化算法参数设置.仿真实验结果表明,改进后的人工蜂群算法能有效求解分布式柔性作业车间调度问题.     

一种求解模糊柔性Job-shop调度问题的多智能体免疫算法

结合实际纸盆车间的生产特点,考虑了模具、机器和操作人员等多种资源约束,以及加工时间和交货日期的不确定性等因素,建立了批量可变的模糊柔性Job-shop调度问题模型。同时结合多智能体系统以及生命科学中免疫系统的免疫信息处理机制,构造了一种用于求解实际Job-shop调度问题的多智能体免疫算法。该方法通过智能体与其邻居间的竞争操作以及自学习操作,并结合自适应疫苗接种、交叉、变异和模拟退火操作,来更新每个智能体在解空间的位置,使其能够更精确地收敛到全局最优解。最后对某纸盆车间的调度实例进行了求解,实验结果验证了算法的有效性。     

A three-fold approach for job shop problems: A divide-and-integrate strategy with immune algorithm

This paper presents a novel divide-and-integrate strategy based approach for solving large scale job-shop scheduling problems. The proposed approach works in three phases. First, in contrast to traditional job-shop scheduling approaches where optimization algorithms are used directly regardless of problem size, priority rules are deployed to decrease problem scale. These priority rules are developed with slack due dates and mean processing time of jobs. Thereafter, immune algorithm is applied to solve each small individual scheduling module. In last phase, integration scheme is employed to amalgamate the small modules to get gross schedule with minimum makespan. This integration is carried out in dynamic fashion by continuously checking the preceding module's machine ideal time and feasible slots (satisfying all the constraint). In this way, the proposed approach will increase the machine utilization and decrease the makespan of gross schedule. Efficacy of the proposed approach has been tested with extremely hard standard test instances of job-shop scheduling problems. Implementation results clearly show effectiveness of the proposed approach.     

An Effective PSO and AIS-Based Hybrid Intelligent Algorithm for Job-Shop Scheduling

The optimization of job-shop scheduling is very important because of its theoretical and practical significance. In this paper, a computationally effective algorithm of combining PSO with AIS for solving the minimum makespan problem of job-shop scheduling is proposed. In the particle swarm system, a novel concept for the distance and velocity of a particle is presented to pave the way for the job-shop scheduling problem. In the artificial immune system, the models of vaccination and receptor editing are designed to improve the immune performance. The proposed algorithm effectively exploits the capabilities of distributed and parallel computing of swarm intelligence approaches. The algorithm is examined by using a set of benchmark instances with various sizes and levels of hardness and is compared with other approaches reported in some existing literature works. The computational results validate the effectiveness of the proposed approach.     

基于遗传算法的Job Shop调度问题研究

在多平行工作站环境下,为使限定资源分配下的车间调度问题(Job Shop problem,JSP)具有最小总延迟时间;同时又可设定各订单具有不同的开工日(release date)及到期日,提出以可开工时间与结束时间为基础的分解解法,并在遗传算法的基础上构造混合遗传算法(hybrid genetic algorithm,HGA)来实现目标设定。实验结果表明,HGA在问题求解质量与Lingo解的最佳解差异在15%以内,并具备较基本型遗传算法更佳的稳定性。结果显示该算法可帮助管理人员实现智能资源配置与订单调度。     

柔性作业车间调度问题的集成启发式算法

柔性作业车间调度问题,包括路径分配和加工排序2大子问题,是组合优化理论和实际生产管理的重要研究方向。作为传统作业车间调度的扩展,柔性作业车间调度问题的内在复杂性(强NP-Hard)使得传统的最优化方法难以有效求解。文章针对以多目标权重和最优为目标的柔性作业车间调度问题,提出基于过滤定向搜索的集成启发式算法,设计改进了节点分枝策略和局部/全局评价函数,能同时解决2大子问题。通过实例仿真,对算法性能进行比较分析和评价,结果表明了算法的可行性和有效性。