A biased random‐key genetic algorithm for scheduling heterogeneous multi‐round systems

A divisible load is an amount W of computational work that can be arbitrarily divided into independent chunks of load. In many divisible load applications, the load can be parallelized in a master–worker fashion, where the master distributes the load among a set P of worker processors to be processed in parallel. The master can only send load to one worker at a time, and the transmission can be done in a single round or in multiple rounds. The multi‐round divisible load scheduling problem consists in (a) selecting the subset of workers that will process the load, (b) defining the order in which load will be transmitted to each of them, (c) defining the number m of transmission rounds that will be used, and (d) deciding the amount of load that will be transmitted to each worker at each round , so as to minimize the makespan. We propose a heuristic approach that determines the transmission order, the set of the active processors and the number of rounds by a biased random‐key genetic algorithm. The amount of load transmitted to each worker is computed in polynomial time by closed‐form formulas. Computational results showed that the proposed genetic algorithm outperformed a closed‐form state‐of‐the‐art heuristic, obtaining makespans that are 11.68% smaller on average for a set of benchmark problems.     

A new hybrid parallel genetic algorithm for the job‐shop scheduling problem

The job‐shop scheduling problem (JSSP) is considered one of the most difficult NP‐hard problems. Numerous studies in the past have shown that as exact methods for the problem solution are intractable, even for small problem sizes, efficient heuristic algorithms must achieve a good balance between the well‐known themes of exploitation and exploration of the vast search space. In this paper, we propose a new hybrid parallel genetic algorithm with specialized crossover and mutation operators utilizing path‐relinking concepts from combinatorial optimization approaches and tabu search in particular. The new scheme relies also on the recently introduced concepts of solution backbones for the JSSP in order to intensify the search in promising regions. We compare the resulting algorithm with a number of state‐of‐the‐art approaches for the JSSP on a number of well‐known test‐beds; the results indicate that our proposed genetic algorithm compares fairly well with some of the best‐performing genetic algorithms for the problem.     

A biased random‐key genetic algorithm for single‐round divisible load scheduling

A divisible load is an amount W of computational work that can be arbitrarily divided into chunks and distributed among a set P of worker processors to be processed in parallel. Divisible load applications occur in many fields of science and engineering. They can be parallelized in a master‐worker fashion, but they pose several scheduling challenges. The divisible load scheduling problem consists in (a) selecting a subset of active workers, (b) defining the order in which the chunks will be transmitted to each of them, and (c) deciding the amount of load that will be transmitted to each worker , with , so as to minimize the makespan, i.e., the total elapsed time since the master began to send data to the first worker, until the last worker stops its computations. In this work, we propose a biased random‐key genetic algorithm for solving the divisible load scheduling problem. Computational results show that the proposed heuristic outperforms the best heuristic in the literature.     

A biased random‐key genetic algorithm for OSPF and DEFT routing to minimize network congestion

Interior gateway routing protocols like Open Shortest Path First (OSPF) and Distributed Exponentially Weighted Flow Splitting (DEFT) send flow through forward links toward the destination node. OSPF routes only on shortest‐weight paths, whereas DEFT sends flow on all forward links, but with an exponential penalty on longer paths. Finding suitable weights for these protocols is known as the weight setting problem (WSP). In this paper, we present a biased random‐key genetic algorithm for WSP using both protocols. The algorithm uses dynamic flow and dynamic shortest path computations. We report computational experiments that show that DEFT achieves less network congestion when compared with OSPF, while, however, yielding larger delays.     

A biased random key genetic algorithm for the field technician scheduling problem

This paper addresses a problem that service companies often face: the field technician scheduling problem. The problem considers the assignment of a set of jobs or service tasks to a group of technicians. The tasks are in different locations within a city, with different time windows, priorities, and processing times. Technicians have different skills and working hours. The main objective is to maximize the sum of priority values associated with the tasks performed each day. Due to the complexity of this problem, constructive heuristics that explore specific characteristics of the problem are developed. A customized Biased Random Key Genetic Algorithm (BRKGA) is also proposed. Computational tests with 1040 instances are presented. The constructive heuristics outperformed a heuristic of the literature in 90% of the instances. In a comparative study with optimal solutions obtained for small-sized problems, the BRKGA reached 99% of the optimal values; for medium- and large-sized problems, the BRKGA provided solutions that are on average 3.6% below the upper bounds.     

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

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

基于遗传和禁忌搜索算法求解车间调度优化问题

针对柔性生产环境下的车间调度问题,在考虑遗传算法早熟收敛问题和禁忌搜索法自适应优点的基础上,将遗传算法和禁忌搜索法结合起来,提出了基于遗传和禁忌搜索的混合动态优化调度算法,并用实例对该算法进行了仿真研究。结果表明,此算法有很好收敛精度,是可行的,并且能够在扰动发生后提供新的调度计划,与传统的调度算法相比较,体现了明显的优越性。     

面向多目标流水车间调度的多种群多目标遗传算法

针对制造型企业普遍存在的流水车间调度问题,建立了以最小化最迟完成时间和总延迟时间为目标的多目标调度模型,并提出一种基于分解方法的多种群多目标遗传算法进行求解.该算法将多目标流水车间调度问题分解为多个单目标子问题,并分阶段地将这些子问题引入到算法迭代过程进行求解.算法在每次迭代时,依据种群的分布情况选择各子问题的最好解及与其相似的个体分别为当前求解的子问题构造子种群,通过多种群的进化完成对多个子问题最优解的并行搜索.通过对标准测试算例进行仿真实验,结果表明所提出的算法在求解该问题上能够获得较好的非支配解集.     

相关工件车间调度问题的拓扑算法

针对加工装配型离散制造企业实际生产的特点,提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题,设计了一种拓扑算法,该算法能够将工序之间的偏序关系转化为线序关系,将相关工件车间调度问题转化为传统的车间调度问题,通过实证研究,结果表明了拓扑算法是可行和高效的。     

An effective hybrid genetic algorithm for flow shop scheduling with limited buffers

As a typical manufacturing and scheduling problem with strong industrial background, flow shop scheduling with limited buffers has gained wide attention both in academic and engineering fields. With the objective to minimize the total completion time (or makespan), such an issue is very hard to solve effectively due to the NP-hardness and the constraint on the intermediate buffer. In this paper, an effective hybrid genetic algorithm (HGA) is proposed for permutation flow shop scheduling with limited buffers. In the HGA, not only multiple genetic operators based on evolutionary mechanism are used simultaneously in hybrid sense, but also a neighborhood structure based on graph model is employed to enhance the local search, so that the exploration and exploitation abilities can be well balanced. Moreover, a decision probability is used to control the utilization of genetic mutation operation and local search based on problem-specific information so as to prevent the premature convergence and concentrate computing effort on promising neighbor solutions. Simulation results and comparisons based on benchmarks demonstrate the effectiveness of the HGA. Meanwhile, the effects of buffer size and decision probability on optimization performances are discussed.     

Job_Shop调度的图表示模型与改进GA求解

通过把调度方案表示成基于约束的图模型,在遗传算法求解过程中,采用了基于约束的二维数组编码方式,使算法的通用性得到提高。借助拓扑排序来判断个体的合法性及进行适应度的求解,在交叉和变异算子中引入关键工序的指导,缩小搜索空间从而提高了算法求解的效率和质量。最后给出相应实例,并与其它文献中的方法比较验证了本算法的可行性和有效性。     

柔性作业调度的串并行模型对比与求解

作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。     

多目标柔性车间调度的二级精选算法

多目标柔性车间调度问题与实际更加符合,是典型的多目标组合优化问题,运用传统算法求解会产生大量的解空间,找到最优解是非常棘手的问题.基于此,提出了二阶优化方法,即基于遗传算法的初级单目标优化和基于多目标决策体系的高级精选优化的组合优化算法.初级优化阶段,采用改进的遗传算法,选用企业最关心的单目标选出一组Pareto解集;...     

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.     

基于新型帝国竞争算法的高维多目标柔性作业车间调度

针对高维多目标柔性作业车间调度问题(MaOFJSP),提出了一种新型帝国竞争算法(ICA)以同时最小化最大完成时间、最大拖期、最大机器负荷和总能耗,该算法采用新方法构建初始帝国使得大多数殖民国家分配数量相近的殖民地,引入殖民国家的同化,并应用新的革命策略和帝国竞争方法以获得高质量解.最后通过大量实验测试ICA新策略对其性能的影响并将ICA与其他算法对比,实验结果表明新型ICA在求解MaOFJSP方面具有较强的优势.     

最优子种群遗传算法求解柔性流水车间调度问题

为了验证最优子种群遗传算法在解决柔性流水车间调度问题时相比于传统遗传算法的优越性,分析了柔性流水车间调度问题的特点,并运用一种新的编码方法和新的遗传算法求解了该问题。考虑到最优个体保护策略法对复杂问题容易使种群收敛陷入局部最优解,为了提高精度、加快较优个体的产生并避免陷入局部最优解,首先提出了一种合理、全面的编码方法,并运用最优子种群遗传算法来求解柔性流水车间调度问题。最后运用实例验证了最优子种群遗传算法的有效性、优越性和编码方式的合理性。     

求解有限产能作业车间调度的改进蚂蚁算法

通过对有限产能车间调度问题的分析,提出了基于蚂蚁算法求解该问题的方法。在模型的构建中增加了成本和机器负荷约束。通过产品的BOM表采用蚂蚁算法搜寻节点,做各阶层工序安排,将各阶层工序安排组合成一完整解。对蚂蚁算法进行了改进,在基本蚂蚁算法的基础上,通过修改信息素局域更新规则和全局更新规则,引入自适应信息素挥发系数来提高算法的收敛速度和全局最优解搜索能力。算例分析表明,蚂蚁的正向反馈及探索功能对求解较大工件数的生产计划非常有效。而且在有限产能的环境中根据产能负荷状况产生不同的外包组合,将满足交货期的各种外包组合成本做敏感性分析,供决策者参考。     

A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling

Finding feasible scheduling that optimize all objective functions for flexible job shop scheduling problem (FJSP) is considered by many researchers. In this paper, the novel hybrid genetic algorithm and simulated annealing (NHGASA) is introduced to solve FJSP. The NHGASA is a combination of genetic algorithm and simulated annealing to propose the algorithm that is more efficient than others. The three objective functions in this paper are: minimize the maximum completion time of all the operations (makespan), minimize the workload of the most loaded machine and minimize the total workload of all machines. Pareto optimal solution approach is used in NHGASA for solving FJSP. Contrary to the other methods that assign weights to all objective functions to reduce them to one objective function, in the NHGASA and during all steps, problems are solved by three objectives. Experimental results prove that the NHGASA that uses Pareto optimal solutions for solving multi-objective FJSP overcome previous methods for solving the same benchmarks in the shorter computational time and higher quality.     

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

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

An effective asexual genetic algorithm for solving the job shop scheduling problem

By using the notion of elite pool, this paper presents an effective asexual genetic algorithm for solving the job shop scheduling problem. Based on mutation operations, the algorithm selectively picks the solution with the highest quality from the pool and after its modification, it can replace the solution with the lowest quality with such a modified solution. The elite pool is initially filled with a number of non-delay schedules, and then, in each iteration, the best solution of the elite pool is removed and mutated in a biased fashion through running a limited tabu search procedure. A decision strategy which balances exploitation versus exploration determines (i) whether any intermediate solution along the run of tabu search should join the elite pool, and (ii) whether upon joining a new solution to the pool, the worst solution should leave the pool. The genetic algorithm procedure is repeated until either a time limit is reached or the elite pool becomes empty. The results of extensive computational experiments on the benchmark instances indicate that the success of the procedure significantly depends on the employed mechanism of updating the elite pool. In these experiments, the optimal value of the well-known 10 × 10 instance, ft10, is obtained in 0.06 s. Moreover, for larger problems, solutions with the precision of less than one percent from the best known solutions are achieved within several seconds.