基于多种群蚁群算法的柔性作业车间调度研究

针对柔性作业车间调度的特点,设计了柔性作业车间调度析取图模型,结合蚁群分工组织的工作方式,给出了基于竞争规则的多种群蚁群算法求解方法。算法中不同种群的蚂蚁被放置在析取图中不同的工序节点上,通过核心种群的引导,充分发挥蚁群协作竞争的并行高效特点,满足柔性作业车间调度的要求。仿真实验表明该算法求解柔性作业车间调度具有可行性和有效性。     

基于信息素调整的蚁群算法求解JSP问题

为更好的求解作业车间调度问题,针对基本蚁群算法求解作业车间调度问题容易进入局部最优问题的情况,提出了一种基于信息素调整的蚁群算法.该算法通过判断信息素矩阵中最大值与最小值之间的比值,当该比值达到算法设定的阀值时,根据相应策略时信息素矩阵进行调整,有效地缩小了信息素之间的差距,有利于跳出局部最优状态;给出了该算法实施的具体步骤.用该算法求解作业车间调度问题,仿真实验结果表明,该算法与基本蚁群算法相比在收敛速度和计算最优解方面都有了改进.     

考虑工件移动时间的柔性作业车间调度问题研究

分析生产车间的实际生产状况,建立了考虑工件移动时间的柔性作业车间调度问题模型,该模型考虑了以往柔性作业车间调度问题模型所没有考虑的工件在加工机器间的移动时间,使柔性作业车间调度问题更贴近实际生产,让调度理论更具现实性。通过对已有的改进遗传算法的遗传操作进行重构,设计出有效求解考虑工件移动时间的柔性作业车间调度问题的改进遗传算法。最后对实际案例进行求解,得到调度甘特图和析取图,通过对甘特图和析取图的分析验证了所建考虑工件移动时间的柔性作业车间调度问题模型的可行性和有效性。     

车间作业调度问题的仿真研究

研究车间作业调度优化问题,使资源、车辆调试、交通分配等达到优化配置,因此车间作业调度问题是一个多约束条件的目标优化问题,采用多项式求解方法不能获得最优解,导致车间作业调度效率低.为了提高车间作业调度效率,提出了一种蚁群算法的车间作业调度优化算法.首先以最小加工时间作为优化目标,蚂蚁爬行路径为作业调度方案,通过蚁群中个体间互相协作和信息交流获得最优车间作业调度方案.通过车间作业调度测试案例对算法进行验证性实验,实验结果表明,蚁群算法提高了车间作业调度效率,能在最短时间找到最优调度方案,为车间作业调度优化提供了依据.     

关于肉制品加工的车间调度问题研究

本文将针对肉制品厂产品的加工流程进行相关工件车间调度问题研究。根据实例建立工件之间的加工工序,得出基于图论的车间调度析取图模型,然后结合拓扑算法的进行逐步求解,最后求出整个产品在加工过程中的线序关系析取图。该研究结果表明拓扑算法在求解该问题上是具有高效性以及可行性的。     

基于蚁群算法的车间作业调度问题研究

对基于蚁群算法的车间作业调度问题求解进行了研究,在分析了传统蚁群算法求解车间作业调度问题容易出现早熟、收敛于局部最优解以及搜索速度慢的缺陷,提出了一种改进的混合蚁群算法。该方法在信息素更新规则上利用信息素局部更新策略和全局更新策略来进行信息素的更新,并将领域搜索与蚁群算法相结合,从而求得问题的可行解。最后,基于benchmarks问题进行了实验仿真,实验结果证明该改进混合算法的有效性及可行性。     

求解柔性机器人车间调度问题的混合蚁群算法

在柔性作业车间调度问题的基础上,考虑多台搬运机器人执行不同工序在不同机床之间的搬运,形成柔性机器人作业车间调度问题,提出混合蚁群算法。用改进析取图对问题进行描述,使用混合选择策略、自适应伪随机比例规则和改进信息素更新规则优化蚁群算法,结合遗传算子完成机床选择和工序排序。使用一种多机器人排序算法完成搬运机器人分配和搬运工序排序。通过多组算例仿真测试并与其他算法进行比较,验证了算法的有效性和可靠性。     

蚁群算法在服务器集群批量任务调度中的应用

服务器集群中的负载均衡和作业调度是影响系统性能的重要因素.本文描述服务器集群批量任务的作业调度问题,对该问题建立了基于图的模型.由于使用一般的启发式算法或动态规划算法解决该问题具有局限性,本文引入蚁群算法进行求解,并针对该问题具体求解提出了启发式距离合适的计算方法.最后在仿真的基础上,讨论了算法的优化效果和收敛性,结果表明蚁群算法解决该问题具有优异的性能.     

基于深度强化学习求解作业车间机器与 AGV联合调度问题

针对作业车间中自动引导运输车(automated guided vehicle, AGV)与机器联合调度问题,以完工时间最小化为目标,提出一种基于卷积神经网络和深度强化学习的集成算法框架.首先,对含AGV的作业车间调度析取图进行分析,将问题转化为一个序列决策问题,并将其表述为马尔可夫决策过程.接着,针对问题的求解特点,设计一种基于析取图的空间状态与5个直接状态特征;在动作空间的设置上,设计包含工序选择和AGV指派的二维动作空间;根据作业车间中加工时间与有效运输时间为定值这一特点,构造奖励函数来引导智能体进行学习.最后,设计针对二维动作空间的2D-PPO算法进行训练和学习,以快速响应AGV与机器的联合调度决策.通过实例验证,基于2D-PPO算法的调度算法具有较好的学习性能和可扩展性效果.     

基于自适应蚁群算法的作业车间模糊调度研究

在研究不确定生产调度问题的基础上,针对具有模糊加工时间和模糊交货期的调度问题给出了作业车间模糊调度模型,用三角模糊数表示模糊加工时间,梯形模糊数表示模糊交货期,以交货期平均满意度最大作为调度目标.针对模糊调度问题对基本蚁群算法作了改进,并给出了新的状态转移规则,同时采用自适应信息素更新策略使算法能快速跳出局部收敛,进行仿真结果验证了自适应蚁群算法求解作业车间模糊调度的有效性.     

基于滑动窗口和蚁群优化算法的二次路径规划算法

针对蚁群优化(ACO)算法在复杂环境下规划能力较弱的问题,提出了一种基于滑动窗口和蚁群优化算法的二次路径规划(QACO)算法.对回退蚁群优化(ACOFS)算法的回退策略进行改进,通过降低回退路径上的信息素量,减少回退次数.第一次规划中,使用改进后的ACO算法对栅格环境进行全局路径规划;第二次规划中,滑动窗口沿着全局路径滑动,通过ACO算法规划出滑动窗口中的局部路径,并使用局部路径对全局路径进行优化,直至滑动窗口中包含目标位置.仿真实验表明:相比ACO、ACOFS算法,QACO算法的平均规划时间分别下降了26.21%、52.03%,平均路径长度下降了47.82%、42.28%,因此在复杂环境下QACO算法具有将强的路径规划能力.     

An efficient memetic algorithm for solving the job shop scheduling problem

The job shop scheduling problem (JSP) is well known as one of the most complicated combinatorial optimization problems, and it is a NP-hard problem. Memetic algorithm (MA) which combines the global search and local search is a hybrid evolutionary algorithm. In this paper, an efficient MA with a novel local search is proposed to solve the JSP. Within the local search, a systematic change of the neighborhood is carried out to avoid trapping into local optimal. And two neighborhood structures are designed by exchanging and inserting based on the critical path. The objective of minimizing makespan is considered while satisfying a number of hard constraints. The computational results obtained in experiments demonstrate that the efficiency of the proposed MA is significantly superior to the other reported approaches in the literature.     

改进麻雀搜索算法求解作业车间调度问题

针对最小化完工时间的作业车间调度问题(JSP),提出改进麻雀搜索算法(ISSA).首先设计有效的编码转换方式,形成JSP离散决策空间与麻雀搜索算法(SSA)连续搜索空间的对应关系.然后,针对SSA在求解后期易陷入局部最优,利用量子计算、正余弦搜索和警戒者数量递减策略对SSA进行改进,同时引入多邻域搜索和高斯扰动策略以弥补SSA在求解离散问题时深度发掘能力不足的弊端.最后,进行FT、LA系列10个测试问题、6种算法和2个应用实例的对比实验.结果表明,ISSA在求解JSP时,能获得更好的最小值、平均值和寻优成功率,验证了ISSA求解JSP的有效性.     

路径和下界公式及其在调度问题中的应用

主要是研究以makespan为目标的多机器置换flow shop调度问题.由于它NP-困难,无法用多项式时间算法求解.而路径和关键路径是研究该问题的一个有力工具,对其进行深入分析可以帮助进一步理解问题最基本的特?挖掘其在更多优化算法中的应用,增加该算法的效率.在研究了原有的关键路径基础上,借助于有向栅格图和重新定义的路径及关键路径公式,直观地给出了对工件排列进行插入移动后的新排列的下界公式.另外,在遗传算法和禁忌搜索之外,还给出了下界公式在NEH启发式算法中的应用,并通过实验验证了它在排除没有希望的排列、减少有效搜索空间的强大能力.     

网格环境中基于负载均衡的工作流调度算法

由于网格工作流任务之间存在时序和数据依赖等关系,使得网格环境中工作流的调度问题成为一个NP完全问题。针对有向无环图(DAG)类型工作流提出一种调度算法,先确定关键路径,从而优先调度关键路径成员节点,该算法追求在最优时间跨度下的系统均衡负载,最后通过实验验证了该算法的有效性。     

An efficient list-based task scheduling algorithm for heterogeneous distributed computing environment

The task scheduling in heterogeneous distributed computing systems plays a crucial role in reducing the makespan and maximizing resource utilization. The diverse nature of the devices in heterogeneous distributed computing systems intensifies the complexity of scheduling the tasks. To overcome this problem, a new list-based static task scheduling algorithm namely Deadline-Aware-Longest-Path-of-all-Predecessors (DA-LPP) is being proposed in this article. In the prioritization phase of the DA-LPP algorithm, the path length of the current task from all its predecessors at each level is computed and among them, the longest path length value is assigned as the rank of the task. This strategy emphasizes the tasks in the critical path. This well-optimized prioritization phase leads to an observable minimization in the makespan of the applications. In the processor selection phase, the DA-LPP algorithm implements the improved insertion-based policy which effectively utilizes the unoccupied leftover free time slots of the processors which improve resource utilization, further least computation cost allocation approach is followed to minimize the overall computation cost of the processors and parental prioritization policy is incorporated to further reduce the scheduling length. To demonstrate the robustness of the proposed algorithm, a synthetic graph generator is used in this experiment to generate a huge variety of graphs. Apart from the synthetic graphs, real-world application graphs like Montage, LIGO, Cybershake, and Epigenomic are also considered to grade the performance of the DA-LPP algorithm. Experimental results of the DA-LPP algorithm show improvement in performance in terms of scheduling length ratio, makespan reduction rate , and resource reduction rate when compared with other algorithms like DQWS, DUCO, DCO and EPRD. The results reveal that for 1000 task set with deadline equals to two times of the critical path, the scheduling length ratio of the DA-LPP algorithm is better than DQWS by 35%, DUCO by 23%, DCO by 26 %, and EPRD by 17%.     

新型教与同伴学习粒子群算法求解作业车间调度问题

针对最小化最大完工时间的单目标作业车间调度问题,提出了新型教与同伴学习粒子群算法。通过教学阶段融合多邻域搜索,采用多样性变异策略以及同伴学习阶段采用混合学习策略三个方面的改进操作,扩大了种群的多样性,避免算法陷入局部最优,算法收敛速度和寻优性能有了显著提高。通过作业车间调度问题FT、LA系列测试实例的对比实验,验证了新型教与同伴学习粒子群算法是解决单目标作业车间调度问题的有效方法。     

一种柔性车间快速启发式调度算法

柔性作业车间调度问题比传统的Job-shop问题更复杂也更符合实际生产实际.为了快速有效地求解这类问题,设计出一种基于综合分派规则的快速启发式调度算法.基于综合分派规则的调度算法,以一批工件总完工时间最短为目标,在调度过程中通过动态调整工件的加工优先级并为每道工序分配最适合的机器进行加工,可迅速求得满意的较优解.与其他方法进行对比实验结果证实了算法的有效性,在实际调度系统的应用中也证明了算法的实用性.     

A tabu search/path relinking algorithm to solve the job shop scheduling problem

We present an algorithm that incorporates a tabu search procedure into the framework of path relinking to generate solutions to the job shop scheduling problem (JSP). This tabu search/path relinking (TS/PR) algorithm comprises several distinguishing features, such as a specific relinking procedure to effectively construct a path linking the initiating solution and the guiding solution, and a reference solution determination mechanism based on two kinds of improvement methods. We evaluate the performance of TS/PR on almost all of the benchmark JSP instances available in the literature. The test results show that TS/PR obtains competitive results compared with state-of-the-art algorithms for JSP in the literature, demonstrating its efficacy in terms of both solution quality and computational efficiency. In particular, TS/PR is able to improve the upper bounds for 49 out of the 205 tested instances and it solves a challenging instance that has remained unsolved for over 20 years.     

Worst-case performance of critical path type algorithms

The critical path method remains one of the most popular approaches in practical scheduling. Being developed for the makespan problem this method can also be generalized to the maximum lateness problem. For the unit execution time task system and parallel processors this generalization is known as the Brucker–Garey–Johnson algorithm. We characterize this algorithm by introducing an upper bound on the deviation of the criterion from its optimal value. The bound is stated in terms of parameters characterizing the problem, namely number of processors, the length of the longest path, and the total required processing time. We also derive a similar bound for the preemptive version of the Brucker– Garey–Johnson algorithm.