基于总空闲时间增量的无等待流水调度混合遗传算法

将NP-难的最小化最大完工时间无等待流水调度问题等价转化为最小化总空闲时间的问题,改变传统求解调度序列目标函数的模式,通过目标函数变化量判断新解的优劣,大大降低算法所需计算时间.分析启发式算法基本操作和进化算子的总空闲时间增量性质,设计基本总空闲时间增量法以快速评估新产生解的质量.提出混合遗传算法IHGA(increment based hybrid genetic algorithm)求解该问题,构造相应初始种群生成方法和进化算子,提出进化概率动态更新策略和种群收敛判断与再生机制;算法混合了迭代改进局部搜索以进一步提高解的质量,基于120个经典Benchmark实例,将IHGA与目前求解该问题的有效算法RAJ,GR,SA2,TSM和FCH进行比较,实验结果表明:IHGA在性能方面优于其他,计算效率方面优于SA2和TSM,略逊于GR,RAJ和FCH.     

基于目标增量的无等待流水调度快速迭代贪婪算法

最小化总完工时间无等待流水调度是典型的NP-完全问题,广泛存在于实际生产系统.改变传统求解调度序列目标函数的模式,提出目标增量法,通过目标函数变化量判断新解的优劣,大大降低算法所需计算时间;通过证明启发式算法基本操作的目标增量性质,设计两种基本目标增量法以快速评估新产生解的质量.提出快速迭代贪婪算法FIG(Fast Iterative Greedy algorithm)求解该问题,构造初始解生成算法,提出分段式重构局部搜索方法和迭代改进全局搜索策略以进一步提高解的质量.基于110个经典Benchmark实例,将提出的FIG算法与目前求解该问题较好的启发式算法PHlp和元启发式算法SRTS、DPSOvnd进行比较,实验结果表明FIG在性能上优于SRTS和PHlp,略逊于DPSOvnd;在效率上优于SRTS和DPSOvnd,略逊于PHlp.     

冷轧生产调度模型及算法

针对冷轧生产线调度问题的复杂性, 将该问题规划为拼卷优化和轧制批量计划编制两个部分. 将拼卷优化问题归结为一个多容器装箱问题, 采用一种新的智能搜索算法——离散微分进化 (DDE) 对该问题进行求解; 对于轧制批量计划编制建立了一种特殊的双旅行商问题模型, 采用基于进化策略和邻域搜索的混合启发式方法求解模型. 最后通过上海宝钢生产实际数据对所提方法进行了试验, 试验结果显示本文给出的生产调度方法是有效的.     

Collision-free Scheduling of Multi-bridge Machining Systems:A Colored Traveling Salesman Problem-based Approach

Multi-bridge machining systems (MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially overlapping workspaces. Their scheduling problems can be abstracted into a serial-colored travelling salesman problem in which each salesman has some exclusive cities and some cities shared with its neighbor(s). To solve it, we develop a greedy algorithm that selects a neighboring city satisfying proximity. The algorithm allows a salesman to select randomly its shared cities and runs accordingly many times. It can thus be used to solve job scheduling problems for MBMS. Subsequently, a collision-free scheduling method is proposed to address both job scheduling and collision resolution issues of MBMS. It is an extension of the greedy algorithm by introducing time window constraints and a collision resolution mechanism. Thus, the augmented greedy algorithm can try its best to select stepwise a job for an individual machine such that no time overlaps exist between it and the job sequence of the neighboring machine dealt in the corresponding overlapping workspace; and remove such a time overlap only when it is inevitable. Finally, we conduct a case study of a large triplebridge waterjet cutting system by applying the proposed method.      

P2P流媒体系统数据调度研究综述

P2P流媒体系统主要涉及成员管理和数据调度等两方面研究.主要研究内容为不同的网络拓扑结构下的数据调度问题的研究问题.P2P流媒体系统网络拓扑结构主要分为三类:树状结构、网状结构和混合结构.树状结构又分为单组播树和多组播树结构,主要采取“推”模式的数据调度机制.网状结构主要采取“拉”模式的数据调度机制.混合结构主要采取“推-拉”模式的数据调度机制.通过介绍每一类方法和相应的代表系统,并给出各类数据调度的优缺点.     

一种P2P流媒体数据调度策略的研究

针对现有P2P流媒体调度策略在确定数据块的调度优先权以及节点服务能力时存在的不足,提出了一种以数据块的紧迫度和稀缺度为基础的凋度优先权的计算方法,以及提出了邻居节点的服务能力的计算方法,经过仿真试验证明町知该策略能有效的解决现有算法的不足,使流媒体启动延迟较小、播放流畅,且能使流媒体系统负载均衡。     

P2P流媒体直播系统数据调度算法及仿真

在数据驱动的P2P流媒体直播系统的研究中,数据调度算法的优劣影响流媒体的播放质量.因此主要研究了P2P流媒体直播系统中的数据调度问题.通过定义请求数据块的播放质量优先级,提出了最大化播放质量优先级的分布式调度模型.模型首先预测出本周期内请求节点与邻居节点之间的实际带宽,然后建立最优化数学模型并将其转换为等价的指派问题,根据该指派问题构造等价的赋权完全二部图,最后利用Kuhn-Munkres算法求出本周期的数据块调度策略.利用P2PStrmSim仿真器仿真,结果表明,所提出的分布式调度算法的性能比传统调度策略有显著提高.     

可分级P2P流媒体的自适应传输调度算法

可分级视频编码(SVC)技术实现了从单一码流中得到不同帧率、分辨率和图像质量的视频数据,使其更能应对网络的抖动.P2P技术已广泛应用到流媒体直播系统中,现有的SVC P2P传输调度机制主要基于传统流媒体,较少考虑SVC流媒体多层的特殊结构.本文提出一种基于层间网络编码的SVC P2P传输调度算法,称为可分级P2P流媒体的自适应传输调度算法.该算法通过预测和调整邻居节点各层的发送概率,使得请求节点能够按照预定的各层接收比例接收数据包.理论分析和仿真结果显示该算法具有较目前主流算法更好的性能.     

P2P流媒体数据块的优化调度策略

在基于数据驱动的P2P流媒体系统中,流媒体数据在参与应用的节点间进行分发,导致流媒体播放质量降低。针对流媒体数据块的分发调度问题,提出一种数据块分发调度策略,通过在调度中考虑节点所需数据块对其流媒体播放质量的影响,以期在合理利用节点有限带宽资源的同时,实现流媒体播放质量的优化。仿真实验结果表明,该策略在改善流媒体播放质量方面具有较明显的优势。     

炼钢连铸生产中炉机优化匹配问题的算法

将炼钢连铸生产计划中炉机优化匹配问题归结为一个不允许等待的混合流水车间排序问题来进行研究,提出了一个启发式算法-最小偏差算法。通过实验设计,用大量随机数据进行了模拟和统计分析。结果表明,最小偏差算法是一种合理的、实用的、有效的算法。     

Scheduling in a continuous galvanizing line

In this paper we address a sequencing problem in a Continuous Galvanizing Line of a Spanish Steel Company. Production scheduling in this context is an extremely complex task which needs to take into account many constraints. We present a conceptually simple model and a Tabu Search (TS) algorithm that efficiently solves it. The TS moves are defined in order to repair non-satisfied constraints, leading to smaller and more efficient neighbourhoods. The TS co-ordinates several intensification and diversification procedures guided by an evaluation function based on a shifting penalty strategy. This function reinforces the anticycling mechanism and makes the algorithm avoid already visited solutions. Our approach has been tested on some real instances from the galvanizing line. Computational results show that the TS improves, in all instances, the company solutions.     

Lower tolerance-based Branch and Bound algorithms for the ATSP

In this paper, we develop a new tolerance-based Branch and Bound algorithm for solving NP-hard problems. In particular, we consider the asymmetric traveling salesman problem (ATSP), an NP-hard problem with large practical relevance. The main algorithmic contribution is our lower bounding strategy that uses the expected costs of including arcs in the solution to the assignment problem relaxation of the ATSP, the so-called lower tolerance values. The computation of the lower bound requires the calculation of a large set of lower tolerances. We apply and adapt a finding from [23] that makes it possible to compute all lower tolerance values efficiently. Computational results show that our Branch and Bound algorithm exhibits very good performance in comparison with state-of-the-art algorithms, in particular for difficult clustered ATSP instances.     

设备带有恶化特性的作业车间调度模型与算法

考虑到现实作业车间调度中设备具有恶化特性,针对作业的处理时间是开始时间的线性递增函数的作业车间调度问题, 建立了以最小化最迟完成时间为目标的优化模型,进而设计了嵌套分割算法进行求解.该算法在抽样阶段嵌入单亲遗传算法以提高抽样的多样性和质量. 实例结果表明,所提出的算法在解决该问题上可以获得较高质量的解,并且具有很好的鲁棒性.     

一种改进的遗传算法及其在钢卷优化组合中的应用

针对遗传算法易于陷入局部最优和收敛速度慢的不足 ,引入个体适应度值的方差和均值来描述种群的聚散程度 ,提出了一种具有参数动态调节功能的改进遗传算法 ,仿真试验证明了算法的有效性 .改进遗传算法应用于罩式退火车间钢卷的自动组合堆垛 ,并在生产应用中取得了很好的效果     

A travelling salesman problem with allocation, time window and precedence constraints — an application to ship scheduling

A Travelling Salesman Problem with Allocation, Time Window and Precedence Constraints (TSP-ATWPC) is considered. The TSP-ATWPC occurs as a subproblem of optimally sequencing a given set of port visits in a real bulk ship scheduling problem, which is a combined multi-ship pickup and delivery problem with time windows and multi-allocation problem. Each ship in the fleet is equipped with a flexible cargo hold that can be partitioned into several smaller holds in a given number of ways, thus allowing multiple products to be carried simultaneously by the same ship. The allocation constraints of the TSP-ATWPC ensure that the partition of the ship's flexible cargo hold and the allocation of cargoes to the smaller holds are feasible throughout the visiting sequence. The TSP-ATWPC is solved as a shortest path problem on a graph whose nodes are the states representing the set of nodes in the path, the last visited node and the accumulated cargo allocation. The arcs of the graph represent transitions from one state to another. The algorithm is a forward dynamic programming algorithm. A number of domination and elimination tests are introduced to reduce the state space. The computational results show that the proposed algorithm for the TSP-ATWPC works, and optimal solutions are obtained to the real ship scheduling problem.     

Online and Offline Algorithms for the Time-Dependent TSP with Time Zones

The time-dependent traveling salesman problem (TDTSP) is a variant of TSP with time-dependent edge costs. We study some restrictions of TDTSP where the number of edge cost changes are limited. We find competitive ratios for online versions of TDTSP. From these we derive polynomial time approximation algorithms for graphs with edge costs one and two. In addition, we present an approximation algorithm for the orienteering problem with edge costs one and two.     

四点三线遗传算法求解旅行商问题

为解决NP完全的旅行商问题,提出一种四点三线遗传算法。该算法特色在两阶段策略,第一阶段是变异算子优化,将汉密尔顿环中所有大于两点的内部路径倒置,并用新极值代替原极值。第二阶段是四点三线优化,将汉密尔顿环分为n个四点三线局部路径并将每个局部路径转化为最优局部路径,将所有局部路径长度求和除以1/3。交叉算子结束后,如子代含有重复位点,将未交叉部分重复位点与交叉部分重复位点对应的父代等位点交换。通过将该算法与传统遗传算法及只进行第一步优化的遗传算法进行比较,采用TSPLIB数据库实例数据,证明该算法有更高的执行效率,有更强的收敛性,适合寻找最短TSP路径。     

A Puzzle-Based Genetic Algorithm with Block Mining and Recombination Heuristic for the Traveling Salesman Problem

In this research, we introduce a new heuristic approach using the concept of ant colony optimization (ACO) to extract patterns from the chromosomes generated by previous generations for solving the generalized traveling salesman problem. The proposed heuristic is composed of two phases. In the first phase the ACO technique is adopted to establish an archive consisting of a set of non-overlapping blocks and of a set of remaining cities (nodes) to be visited. The second phase is a block recombination phase where the set of blocks and the rest of cities are combined to form an artificial chromosome. The generated artificial chromosomes (ACs) will then be injected into a standard genetic algorithm (SGA) to speed up the convergence. The proposed method is called "Puzzle-Based Genetic Algorithm" or "p-ACGA". We demonstrate that p-ACGA performs very well on all TSPLIB problems, which have been solved to optimality by other researchers. The proposed approach can prevent the early convergence of the genetic algorithm (GA) and lead the algorithm to explore and exploit the search space by taking advantage of the artificial chromosomes.     

路径交叉检测与消除方法和邻节点置换方法改进TSP的解

针对当前算法在求解规模较大的TSP时得到的近似解中常常存在路径交叉这一不足,提出了一种路径交叉检测与消除方法,可以完全消除路径交叉从而提高近似解的质量;通过分析近似解的结构,发现一些相邻节点相互交换位置也可以有效提高解的质量,因此提出了一种邻节点置换方法。实验表明提出的方法可以有效改进模拟退火算法求得的TSP近似解。     

带多项式量级约束条件的多商品流BWTSP线性规划

黑白旅行商问题(BWTSP)是近年来出现的新NP-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗基数商品流,分析了环路上的弧应满足的约束条件,并证明这些n\\+2+2|W|的约束条件即是基数约束条件;类似地通过定义剩余和消耗权值商品流,得到n\\+2+n+2|B|个权值约束条件. 最终得到原始问题仅包含3n\\+2+7n个约束条件的线性规划.由于无向BWTSP问题和权值阈值等于+∞的有向BWTSP均是一般有向BWTSP的特例,故此结果对于它们同样有效.