A chaotic non-dominated sorting genetic algorithm for the multi-objective automatic test task scheduling problem

Solving a task scheduling problem is a key challenge for automatic test technology to improve throughput, reduce test time, and operate the necessary instruments at their maximum capacity. Therefore, this paper attempts to solve the automatic test task scheduling problem (TTSP) with the objectives of minimizing the maximal test completion time (makespan) and the mean workload of the instruments. In this paper, the formal formulation and the constraints of the TTSP are established to describe this problem. Then, a new encoding method called the integrated encoding scheme (IES) is proposed. This encoding scheme is able to transform a combinatorial optimization problem into a continuous optimization problem, thus improving the encoding efficiency and reducing the complexity of the genetic manipulations. More importantly, because the TTSP has many local optima, a chaotic non-dominated sorting genetic algorithm (CNSGA) is presented to avoid becoming trapped in local optima and to obtain high quality solutions. This approach introduces a chaotic initial population, a crossover operator, and a mutation operator into the non-dominated sorting genetic algorithm II (NSGA-II) to enhance the local searching ability. Both the logistic map and the cat map are used to design the chaotic operators, and their performances are compared. To identify a good approach for hybridizing NSGA-II and chaos, and indicate the effectiveness of IES, several experiments are performed based on the following: (1) a small-scale TTSP and a large-scale TTSP in real-world applications and (2) a TTSP used in other research. Computational simulations and comparisons show that CNSGA improves the local searching ability and is suitable for solving the TTSP.     

Multi-objective hybrid genetic algorithm for task scheduling problem in cloud computing

Neural Computing and Applications - The cloud computing systems are sorts of shared collateral structure which has been in demand from its inception. In these systems, clients are able to access...     

解并行机模糊调度问题的自适应遗传算法

针对家纺企业车间调度的实际情况,建立了一种产品优先级约束的模糊车间调度模型。在模型中,完工时间和交货期都是模糊的,交货期平均满意度最大为调度目标。基于此模型,提出了一种自适应的遗传算法,该算法通过比例选择及局部搜索保证种群的优良特性,并通过自动调节变异率和交叉率的方式保证种群的多样性,有效跳出局部收敛。仿真结果表明,自适应遗传算法能有效求解,并优于免疫遗传算法。     

改进蚁群算法求解同型机任务调度问题

针对并行与分布式系统中的同型机调度问题,提出了一种改进蚁群算法。结合问题具体特点,给出了蚂蚁分配方案的生成策略,设计了一种新颖的基于任务适合度的信息素表示方法,以实现信息素的有效累积;改进了状态转移规则,通过对阈值的自适应调整使算法能根据搜索进度确定查找区域;在对信息素全局更新前,对每轮迭代获得的最好解进行变邻域搜索,避免算法陷入局部最优,提高收敛速度。仿真结果表明,改进算法有较强的寻优能力和稳定的求解质量。     

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.     

解不同交货期并行机调度问题的并行遗传算法

为有效地解决不同交货期窗口下的非等同并行多机提前/拖后调度问题,设计了一种分段编码的混合遗传算法。此编码方式能反映工件的分配序列,并利用调度优先级规则和最好适应值规则相结合的启发式算法对其顺序进行了调整,加快了收敛速度。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于遗传算法,有着较高的并行性,并能适用于大规模不同交货期窗口下非等同并行多机提前/拖后调度问题。     

改进遗传算法的并行任务调度

并行任务调度是一个NP完全问题,它关注资源的分配和并行任务调度,要求具有高性能的调度算法,且能求解出高质量的解。提出了一种基于改进遗传算法的并行任务调度算法,在算法初始化种群产生时引入任务向量矩阵来表示任务、资源以及调度的关系,并采用启发式方法得到初始化种群,提高种群质量;采用规则约束的交叉和变异操作,提高个体的质量;提出了加速进化策略,有效地避免了早熟。仿真实验结果表明,该改进算法能更有效地求解并行任务调度问题。     

Amended hybrid multi-verse optimizer with genetic algorithm for solving task scheduling problem in cloud computing

The Journal of Supercomputing - The central cloud facilities based on virtual machines offer many benefits to reduce the scheduling costs and improve service availability and accessibility. The...     

Real-time task scheduling by multiobjective genetic algorithm

Real-time tasks are characterized by computational activities with timing constraints and classified into two categories: a hard real-time task and a soft real-time task. In hard real-time tasks, tardiness can be catastrophic. The goal of hard real-time tasks scheduling algorithms is to meet all tasks’ deadlines, in other words, to keep the feasibility of scheduling through admission control. However, in the case of soft real-time tasks, slight violation of deadlines is not so critical.In this paper, we propose a new scheduling algorithm for soft real-time tasks using multiobjective genetic algorithm (moGA) on multiprocessors system. It is assumed that tasks have precedence relations among them and are executed on homogeneous multiprocessor environment.The objective of the proposed scheduling algorithm is to minimize the total tardiness and total number of processors used. For these objectives, this paper combines adaptive weight approach (AWA) that utilizes some useful information from the current population to readjust weights for obtaining a search pressure toward a positive ideal point. The effectiveness of the proposed algorithm is shown through simulation studies.     

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

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

Non-identical parallel machine scheduling using genetic algorithm

Most of the scheduling problems are NP-hard. In the literature, several heuristics and dispatching rules are proposed to solve such hard combinatorial optimization problems and genetic algorithm (GA) ranks among the most preferred ones in view of its characteristics such as high adaptability, near optimization and easy realization. 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 paper, the authors propose a new “crossover operator” and a new “optimality criterion” in order to adapt the GA to non-identical parallel machine scheduling problem. New algorithm is tested on a numerical example by implementing it in a simulation software and computational results are compared to those obtained with LPT (Longest Processing Time) dispatching rule; results were promising. Findings show that, in addition to its high computational speed for larger scale problem, the GA proposed here fits the non-identical parallel machine scheduling problem of minimizing the maximum completion time (makespan).     

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.     

求解置换Flow-shop调度问题的改进遗传算法

提出一种求解置换Flow-shop调度问题的改进遗传算法。该算法采用多个体交叉方式,对交叉过程和变异过程分别进行阈值设置,实现了在优化过程中扩大解空间的搜索范围和保持种群的多样性,从而增大了获得最优解的几率。最后对一系列典型的Benchmark问题进行仿真测试,实验结果证实了该改进遗传算法的有效性。     

柔性作业车间调度中的组合遗传优化研究

针对柔性作业车间调度问题,提出一种组合遗传算法。该算法在种群初始化、选择、交叉、变异各阶段,组合使用各种不同的策略。针对机器编码部分的交叉,提出一种基于工件的机器交叉算子,用以改进机器分配部分随机交叉引起的对父代优秀基因继承不足的缺陷。通过对典型算例的计算以及与其他文献的研究成果比较,证明该算法的优良性能。     

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

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

Maximizing availability for task scheduling in computational grid using genetic algorithm

Computational grid provides a wide distributed platform for high‐end compute intensive applications. Grid scheduling is often carried out to schedule the submitted jobs on the nodes of the grid so that some characteristic parameter is optimized. Availability of the computational nodes is one of the important characteristic parameters and measures the probability of the node availability for job execution. This paper addresses the availability of the grid computational nodes for the job execution and proposes a model to maximize it. As such, the task scheduling problem in grid is nondeterministic polynomial‐time hard, and often, metaheuristics techniques are applied to solve it. Genetic algorithm, a metaheuristic technique based on evolutionary computation, has been used to solve such complex optimization problem. This work proposes a technique for the grid scheduling problem using genetic algorithm with the objective to maximize availability. Simulation experiment, to evaluate the performance of the proposed algorithm, is conducted, and results reveal the effectiveness of the model. A comparative study has also been performed. Copyright © 2014 John Wiley & Sons, Ltd.     

A new polynomial algorithm for a paralle identical scheduling problem

A precedence order is defined based on the release dates of jobs' direct successors. Using the defined precedence order and Heap Sort, a new polynomial algorithm is provided which aims to solve the parallel scheduling problem P|p = 1, r ,outtree|∑C . The new algorithm is shown to be more compact and easier to implement.     

并行机实时调度问题的LR&CG算法

研究了目标函数为最小化总加权完成时间的并行机实时调度问题.建立该问题混合整数规划模型,并提出融合拉格朗日松弛(LR)和列生成(CG)的 LR & CG 混合算法.该算法包含双重迭代,在内环以次梯度法作为下界求解器和列生成器,在外环通过求解限制主问题来获得影子价格以调节拉格朗日乘子.计算实验结果表明,在相同的计算时间内, LR & CG 能够比常规的 LR 算法获得更好的上界和下界,表明了前者具有更好的收敛性能.     

A new polynomial algorithm for a parallel identical scheduling problem

A precedence order is defined based on the release dates of jobs' direct successors. Using the defined precedence order and Heap Sort, a new polynomial algorithm is provided which aims to solve the parallel scheduling problem P|p = 1, r ,outtree|∑C . The new algorithm is shown to be more compact and easier to implement.     

基于递阶遗传算法的并行多机调度优化

针对最小化完工时间的等同和非等同并行多机调度一类问题，提出了一种递阶遗传算法。该算法根据问题的特点，采用一种递阶编码方案，此编码与调度方案一一对应。用递阶遗传算法优化并行多机调度不需设计专门的遗传算子，操作简单。计算结果表明，递阶遗传算法是有效的，能适用于大规模等同和非等同并行多机调度问题。