基于混合人工蜂群算法的多目标柔性作业车间调度问题研究

传统的优化算法在求解面对多目标柔性作业车间调度时,往往求解效率低且难以获得最优解。为了求解多目标柔性作业车间调度问题,设计了混合人工蜂群算法。种群的初始化采用了多种方法相结合的策略。在人工蜂群算法的不同阶段采用不同的搜索机制,在雇佣蜂阶段采用开发搜索,针对跟随蜂阶段蜜蜂跟随的对象的优秀解进行小幅度的更新,从而提高了搜索的表现。禁忌搜索与改进的人工蜂群算法相结合,有效的提升了获得最优解的概率。通过相关文献中的标准实例对设计的混合人工蜂群算法进行一系列求解测试,实验的结果有效的说明了算法在求解柔性作业车间调度问题时效果显著。通过求解结果对比表明人工蜂群算法的高效性和优越性。     

考虑多目标的柔性工艺与调度集成优化算法

针对工艺规划与车间调度集成优化问题,在考虑零件的加工工序柔性、工序次序柔性及加工机器柔性的基础上,以最大完工时间、总加工成本和总拖期时间为优化目标,对多目标柔性工艺与车间调度集成问题建模,提出一种基于改进人工蜂群算法的多目标柔性工艺与车间调度集成优化策略,并提出邻域变异操作以及全局交叉操作,对种群进行更新。引入Pareto方法,通过对适应度评价、贪婪准则、Pareto最优解集构造和保存以及解得多样性维护等方面进行改进,设计了一种基于Pareto方法的多目标人工蜂群算法。最后,通过采用基本人工蜂群算法及改进人工蜂群算法对六个工件、五台机床的柔性工艺与车间调度集成问题进行优化,验证了改进算法的有效性。     

基于作业链的泊位与岸桥协同调度研究

针对泊位与岸桥协同调度问题,引入"链式优化"思路,用作业链的方法分析集装箱装卸作业过程,首先将泊位计划作为开始链单元,采用资源节点优化策略进行分析,以最小化船舶在港总成本为目标建立模型;然后将岸桥卸船作业作为结束链单元,采用任务节点优化策略进行分析,以最小化岸桥最大完工时间为目标建立模型.考虑到作业链的整体性能,设计嵌...     

云计算中基于共享机制和群体智能优化算法的任务调度方案

为了提高云计算中虚拟机(VM)的利用率并降低任务的完成时间,提出了一种融合共享机制的混合群智能优化算法,实现云任务的动态调度。首先,将虚拟机调度编码为蜜蜂、蚂蚁和遗传个体。然后,利用人工蜂群算法(ABC)、蚁群算法(ACO)和遗传算法(GA)分别在各自邻域内寻找最优解。最后,通过一个共享机制使3种算法定期交流各自搜索到的解,并将获得的最佳解作为当前最优解进行下一次迭代过程,以此来加速算法收敛并提高收敛精度。通过CloudSim进行了一个云任务调度的仿真实验,结果表明提出的混合算法能够合理有效地调度任务,在任务完成时间和稳定性方面具有优越的性能。     

Efficient meta-heuristics based on various dominance criteria for a single-machine bi-criteria scheduling problem with rejection

In this paper, we try to fill in the gap between theory and practice in production scheduling by defining a new term as “rejection” and treating the corresponding scheduling problem with multi-objective optimization approach. We study a bi-objective single machine scheduling problem with rejection. At the beginning of scheduling time horizon, scheduler needs to decide which job shall be rejected due to the resource constraints regarding two objective functions: minimization of total weighted completion time of accepted jobs and total rejection penalty of rejected jobs. We develop different algorithms to find the best estimation of Pareto-optimal front for this problem. In order to improve the quality of the solutions, on the one hand, and facilitate the process of selecting best solution for the final decision maker, on the other hand, we integrate various dominance criteria into our proposed algorithms. Finally we compare the performance of those methods by testing on a large set of instances and highlight the advantages and weak points of each one.     

Job Shop Scheduling with the Best-so-far ABC

The Job Shop Scheduling Problem (JSSP) is known as one of the most difficult scheduling problems. It is an important practical problem in the fields of production management and combinatorial optimization. Since JSSP is NP-complete, meaning that the selection of the best scheduling solution is not polynomially bounded, heuristic approaches are often considered. Inspired by the decision making capability of bee swarms in the nature, this paper proposes an effective scheduling method based on Best-so-far Artificial Bee Colony (Best-so-far ABC) for solving the JSSP. In this method, we bias the solution direction toward the Best-so-far solution rather a neighboring solution as proposed in the original ABC method. We also use the set theory to describe the mapping of our proposed method to the problem in the combinatorial optimization domain. The performance of the proposed method is then empirically assessed using 62 benchmark problems taken from the Operations Research Library (OR-Library). The solution quality is measured based on “Best”, “Average”, “Standard Deviation (S.D.)”, and “Relative Percent Error (RPE)” of the objective value. The results demonstrate that the proposed method is able to produce higher quality solutions than the current state-of-the-art heuristic-based algorithms.     

基于混合人工蜂群算法的并行测试任务优化研究

并行测试技术可以同时进行多个任务的测试,提高资源利用率,节约测试成本;并行测试调度问题是一种复杂的组合优化问题,是并行测试技术的核心要素;并行测试系统作为并行测试技术的载体,自身的性能和求解效率尤其重要;对并行测试完成时间极限定理进行了研究,建立了并行测试任务调度的数学模型,分析了传统元启发式算法求解并行测试问题的不足,提出了基于动态规划的递归搜索技术和人工蜂群算法相结合的混合人工蜂群算法,并采用整数规划精确算法和遗传算法对混合人工蜂群算法进行验证;得出结论采用混合人工蜂群算法进行并行测试任务的调度节约了接近50%的时间,降低了约20%的硬件资源占用,提高了测试效率,可以满足工程实际的应用。     

基于ABC-SA混合算法的群控电梯优化调度

为解决电梯群控系统（Elevator group control system,EGCS）时间和能耗性能不理想的问题,提出一种基于改进人工蜂群的电梯群控多目标优化调度算法。首先,针对EGCS控制目标复杂性,建立具有多评价指标的群控电梯调度模型,依据该模型的适应度值进行合理派梯选择;其次,引入模拟退火准则优化基本人工蜂群算法结构以解决算法易陷入局部最优解的问题,使用混合改进的人工蜂群算法进行多目标优化调度。仿真结果表明,所提算法在侯梯时间、乘梯时间和停靠次数三个性能指标上对比基本人工蜂群算法均有所提高,有效说明该方法在求解柔性多目标群控电梯优化调度时具有一定的优越性。     

雾计算平台的任务调度算法研究

雾计算平台中的任务调度问题是无法在多项式时间复杂度内求取精确解的NP-问题。本文在根据雾计算任务调度流程,构建雾计算平台任务调度数学模型基础上,采用改进人工蜂群算法,将任务调度映射为蜂群寻找蜜源的过程,在种群初始化阶段过引入混沌思想,改善了人工蜂群算法缺陷,扩大了蜂群搜索范围,避免陷入局部最优解。实验结果表明,改进后的人工蜂群算法具有更快的算法收敛速度,算法解析所对应的任务调度策略,也具有更高的任务处理总性能,表明本文所研究的改进人工蜂群算法,达到了提高雾计算资源利用率,提高雾计算任务处理效率的目的。     

安全服务链中虚拟网络功能分配与调度算法研究

安全服务链中的虚拟网络功能（virtual network function,VNF）将传统网络安全功能与硬件设备解耦,使得服务功能的部署更具动态性和可扩展性。然而,VNF向节点的合理分配以及节点上VNF的高效调度问题仍亟待解决。为此,基于软件定义网络（software defined network,SDN）和网络功能虚拟化（network function virtualization,NFV）环境,提出基于优化算法的解决方案。首先,对资源分配与调度问题进行举例并形式化定义问题的优化目标;其次,提出基于贪心算法的资源分配方案和基于混合蜂群算法的资源调度方案,统一协调解决VNF的资源分配与调度问题。最后,设计仿真实验,验证所提算法的时间复杂性和在总资源成本和总服务收益方面的提升;同时,对比混合蜂群算法和传统蜂群算法,结果显示前者具有更快的收敛速度。     

The continuous artificial bee colony algorithm for binary optimization

Artificial bee colony (ABC) algorithm, one of the swarm intelligence algorithms, has been proposed for continuous optimization, inspired intelligent behaviors of real honey bee colony. For the optimization problems having binary structured solution space, the basic ABC algorithm should be modified because its basic version is proposed for solving continuous optimization problems. In this study, an adapted version of ABC, ABC_bin for short, is proposed for binary optimization. In the proposed model for solving binary optimization problems, despite the fact that artificial agents in the algorithm works on the continuous solution space, the food source position obtained by the artificial agents is converted to binary values, before the objective function specific for the problem is evaluated. The accuracy and performance of the proposed approach have been examined on well-known 15 benchmark instances of uncapacitated facility location problem, and the results obtained by ABC_bin are compared with the results of continuous particle swarm optimization (CPSO), binary particle swarm optimization (BPSO), improved binary particle swarm optimization (IBPSO), binary artificial bee colony algorithm (binABC) and discrete artificial bee colony algorithm (DisABC). The performance of ABC_bin is also analyzed under the change of control parameter values. The experimental results and comparisons show that proposed ABC_bin is an alternative and simple binary optimization tool in terms of solution quality and robustness.     

A bio-inspired distributed algorithm to improve scheduling performance of multi-broker grids

The scheduling in grids is known to be a NP-hard problem. The distributed deployment of nodes, their heterogeneity and their fluctuations in terms of workload and availability make the design of an effective scheduling algorithm a very complex issue. The scientific literature has proposed several heuristics able to tackle this kind of optimization problem using techniques and strategies inspired by nature. The algorithms belonging to ant colony optimization (ACO) paradigm represent an example of these techniques: each one of these algorithms uses strategies inspired by the self-organization ability of real ants for building effective grid schedulers. In this paper, the authors propose an on line, non-clairvoyant, distributed scheduling solution for multi-broker grid based on the alienated ant algorithm (AAA), a new ACO inspired technique exploiting a “non natural” behavior of ants and an inverse interpretation of pheromone trails. The paper introduces the proposed algorithm, explains the differences with other classical ACO approaches, and compares AAA with two different algorithms. The results of simulations show that the AAA guarantees good performance in terms of makespan, average queue waiting time and load balancing capability.     

Cilk: An Efficient Multithreaded Runtime System

Cilk (pronounced “silk”) is a C-based runtime system for multithreaded parallel programming. In this paper, we document the efficiency of the Cilk work-stealing scheduler, both empirically and analytically. We show that on real and synthetic applications, the “work” and “critical-path length” of a Cilk computation can be used to model performance accurately. Consequently, a Cilk programmer can focus on reducing the computation's work and critical-path length, insulated from load balancing and other runtime scheduling issues. We also prove that for the class of “fully strict” (well-structured) programs, the Cilk scheduler achieves space, time, and communication bounds all within a constant factor of optimal. The Cilk runtime system currently runs on the Connection Machine CM5 MPP, the Intel Paragon MPP, the Sun Sparcstation SMP, and the Cilk-NOW network of workstations. Applications written in Cilk include protein folding, graphic rendering, backtrack search, and the Socrates chess program, which won second prize in the 1995 ICCA World Computer Chess Championship.     

Optimal job scheduling in grid computing using efficient binary artificial bee colony optimization

The artificial bee colony has the advantage of employing fewer control parameters compared with other population-based optimization algorithms. In this paper a binary artificial bee colony (BABC) algorithm is developed for binary integer job scheduling problems in grid computing. We further propose an efficient binary artificial bee colony extension of BABC that incorporates a flexible ranking strategy (FRS) to improve the balance between exploration and exploitation. The FRS is introduced to generate and use new solutions for diversified search in early generations and to speed up convergence in latter generations. Two variants are introduced to minimize the makepsan. In the first a fixed number of best solutions is employed with the FRS while in the second the number of the best solutions is reduced with each new generation. Simulation results for benchmark job scheduling problems show that the performance of our proposed methods is better than those alternatives such as genetic algorithms, simulated annealing and particle swarm optimization.     

云计算调度粒子群改进算法

云计算资源调度是云计算中一个关键且复杂的调度问题,需要考虑众多的因素.为减少任务完成时间,本文提出了一种云资源调度粒子群改进算法.首先,本文在惯性权重线性递减的基础上,加入了混沌随机数扰动,使惯性权重有概率的适度增加,以便于跳出局部搜索,进行全局搜索;其次,针对粒子群算法和蚁群算法都容易陷入局部最优的缺点,结合粒子群算法和蚁群算法的优化策略,提出了一种改进的混合优化策略.其仿真结果及实际算例测试结果表明,在相同条件下改进算法能够寻到更精确的解.     

A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops

Obtaining an optimal solution for a permutation flowshop scheduling problem with the total flowtime criterion in a reasonable computational timeframe using traditional approaches and optimization tools has been a challenge. This paper presents a discrete artificial bee colony algorithm hybridized with a variant of iterated greedy algorithms to find the permutation that gives the smallest total flowtime. Iterated greedy algorithms are comprised of local search procedures based on insertion and swap neighborhood structures. In the same context, we also consider a discrete differential evolution algorithm from our previous work. The performance of the proposed algorithms is tested on the well-known benchmark suite of Taillard. The highly effective performance of the discrete artificial bee colony and hybrid differential evolution algorithms is compared against the best performing algorithms from the existing literature in terms of both solution quality and CPU times. Ultimately, 44 out of the 90 best known solutions provided very recently by the best performing estimation of distribution and genetic local search algorithms are further improved by the proposed algorithms with short-term searches. The solutions known to be the best to date are reported for the benchmark suite of Taillard with long-term searches, as well.     

解决复杂优化问题的一个有效工具——蜂群优化算法*

蜂群的某些群智能行为在昆虫中是很独特的,因此来源于蜂群智能行为的各种优化算法在解决某些实际问题时是很有效的。较之其他的优化算法,目前国内关于蜂群优化算法的文献相对较少。简要介绍了若干蜂群优化算法的发展概况,并探讨了一些未来可做的工作。     

Optimum structural design of spatial steel frames via biogeography-based optimization

Metaheuristic algorithms have provided an efficient tool for designers by which discrete optimum design of real-size steel space frames under design code requirements can be obtained. In this study, the optimum sizing design of steel space frames is formulated according to provisions of Load and Resistance Factor Design—American Institute of Steel Construction. The weight of the steel frame is taken as objective function. The design algorithm selects the appropriate W sections for members of the steel frame such that the frame weight is the minimum and design code limitations are satisfied. The biogeography-based optimization algorithm is utilized to find out the optimum solution of the discrete programming problem. This algorithm is one of the recent additions to metaheuristic techniques which are based on theory of island biogeography where each habitat is assumed to be potential solution for the design problem. The performance of the biogeography-based optimization algorithm is compared with other recent metaheuristic algorithms such as adaptive firefly algorithm, teaching and learning-based optimization, artificial bee colony optimization, dynamic harmony search algorithm, and ant colony algorithm. It is shown that biogeography-based optimization algorithm outperforms other metaheuristic techniques in the design examples considered.

     

物流配送中心配载车辆调度问题研究

物流配载车辆调度目标就是针对特定任务调配车辆资源以降低成本费用。分析了车辆和特定运输任务的相关约束条件,提出了物流中心配载车辆调度问题数学模型。重点研究了基于任务时间窗逻辑顺序约束求取可行解的“分组”算法、以及基于时间窗约束冲突概率对可行解基因实施交叉的优化算法。实验结果表明在多任务、多约束条件下采用该算法可快速求取物流配载调度问题的最优解。     

反向人工蜂群算法求解混合流水车间调度问题

针对以最小化最大完工时间为优化目标的混合流水车间调度问题,提出一种融合反向学习策略的反向人工蜂群算法求解该问题。首先,根据混合流水车间调度问题的特点,建立了对应的数学模型和仿真优化模型;其次,在寻优过程中为了避免陷入局部最优,分别在种群初始化、雇佣蜂和观察蜂三个阶段引入了反向学习策略,采用两点间逆序策略和元素交换策略加快寻优速度,并采用精英保优策略保留最优解;最后,选取2个实例和21个不同规模的benchmark算例进行仿真实验,通过与相关算法的实验结果进行对比分析,验证了所提算法能有效求解此类问题。