一种基于ILP的流水线调度算法

提出一种基于整数规划 (IL P)的流水线调度算法 ,可以在给定的流水时延槽之下优化资源需求 ,保证流水线长度的最小化 ;同时 ,在各个工作步中的操作与调度的先后顺序无关 ,整体性能优良 ,支持链式 (Chaining)操作 ,较适合于流水线数据通路的综合。     

流水线调度问题探究

流水线作业是现代生产线最常用的技术,流水线调度问题是具有很强工程背景的典型NP完全问题.文中介绍了特殊情况下流水线调度的有效算法:Johnson算法;对于一般情况,介绍了两种启发式算法:CDS算法和Palmer算法.对这两种启发式算法的分析表明,在时间复杂度上,CDS算法比Palmer算法复杂.但大量实验测试表明,CDS算法的结果比Palmer算法更佳.所以,当需要快速获得一个近似解的时候,可以采用Palmer算法;当对解的结果要求比较高的时候,可以采用CDS算法.     

调度问题的形式化描述

本文介绍高层次综合中调度问题的形式化描述。该描述将调度问题形式化为整数规划问题。它全面地考虑了调度问题的时间约束与资源约束、多周期操作与链式操作，流水线功能单元与非流水线功能单元以及分枝操作的调度问题。它为解决调度问题提供了一个较好的数学模型。     

禁忌搜索算法解决零空闲流水线调度问题

针对流水线调度这一类NP-Hard难题,深入分析了零空闲流水线调度问题,提出了一种解决零空闲流水线调度问题的基于NEH方法的禁忌搜索算法,建立了以工件的最大完工时间为目标的算法模型.新算法利用NEH启发式算法产生问题的初始解,改善了新算法的搜索性能.利用动态方式更新禁忌表长,提高了新算法的鲁棒性.为了提高算法的运行时效,利用快速搜索算法对提出的禁忌搜索算法进行改进,即采用快速搜索算法作为禁忌搜索的邻域函数,得到另一种改进的禁忌搜索算法.仿真试验结果表明了该算法的有效性及优越性,新算法在流水线生产调度及自动化工程等领域具有较高的实用价值.     

强时间约束条件下的调度优化算法的改进

对基于操作的结合律与分配律进行变换的强时间约束条件下的调度算法提出了改进，通过弱化基本操作变换类型的发生条件并结合递归试探的方法，改善了直接应用特定基本操作变换类型的同类算法适用范围窄、容易调度失败的缺点。     

动态零等待流水线调度问题的滚动策略及优化算法

针对工件动态到达的零等待流水线调度问题,提出一种基于工件的滚动策略.证明了在该策略下全局调度性能随着局部调度的逐步滚动可得到不断改善.将该策略与基于差分进化的混合算法有机结合,能有效处理动态零等待流水线调度问题.最后通过实验验证了所提出策略和算法的有效性.     

仓库调度中的规则约束遗传算法研究及应用

研究自动化立体仓库的优化调度算法,旨在有效提高企业的仓储管理效率与供货能力.根据自动化立体仓库调度专家的知识和经验给出作业调度和货位管理的规则集,在此基础上利用遗传算法对雄垛机行驶时间等参数进行进一步优化.算法很好地解决了遗传算法操作的盲目性以及专家系统过分依赖知识库等缺陷,通过对某卷烟厂大型立体仓库的实际参数进行仿真试验,在实例给出的具体约束条件下,算法使堆垛机仿真行驶时间最短.仿真试验结果表明,上述方法可提高立体仓库货位分布的合理性和出入库调度的效率.     

求解敏捷供应链调度优化问题的混合遗传算法

针对敏捷供应链调度决策中,需求的时间、数量约束和供应商生产能力、可用调度时段约束造成系统优化的复杂性,设计结合贪婪算法的混合遗传算法进行求解。算法以供应链系统库存成本和运输成本为适应度函数,以包含企业信息、部件信息和调度时段信息的时段编码作为遗传编码,以线性次序交叉LOX算子和逆序变异INV算子进行交叉和变异操作,在解码过程中结合贪婪算法进行调度决策和适应度计算,保证算法在满足约束条件的基础上快速收敛到系统Pareto最优解,通过算例验证算法的有效性。     

强时间约束条件下的调度优化算法

强时间约束是指控制数据流图CDFG的延迟时间无法满足的时间约束。为了使CDFG的延迟时间能够满足强时间约束,本文提出了对CDFG的优化(压缩)算法。该算法根据操作的结合律和兮配律,在满足硬件资源约束的条件下,将CDFG关键路径上的操作转换到相关的非关键路径上去,使关键路径上的操作个数减少(即CDFG的延迟时间减少),从而使CDFG的延迟时间满足强时间约束。该算法在不改变CDFG语义的前题下,重新安排CDFG中的各个操作,尽量减少关键路径上的操作个数。该算法已经加入到我们所完成的DBS调度算法的控制策略中,使得DBS调度算法能够在强时间约束条件下进行调度。     

流水线调度问题探究

流水线作业是现代生产线最常用的技术,流水线调度问题是具有很强工程背景的典型NP完全问题。文中介绍了特殊情况下流水线调度的有效算法:Johnson算法;对于一般情况,介绍了两种启发式算法:CDS算法和Palmer算法。对这两种启发式算法的分析表明,在时间复杂度上,CDS算法比Palmer算法复杂。但大量实验测试表明,CDS算法的结果比Palmer算法更佳。所以,当需要快速获得一个近似解的时候,可以采用Palmer算法;当对解的结果要求比较高的时候,可以采用CDS算法。     

多目标粒子群算法在乘务员排班问题中的应用

乘务员排班问题规模庞大并且限制因素复杂,一种公平合理的排班有利于调动乘务员的积极性。对建立的多目标排班模型进行分析和优化,并提出近似可行解以处理约束条件,基于Pareto最优的粒子群算法解决了这一问题,仿真实验表明该算法是合理的。     

带流水作业工程项目调度问题的遗传算法

介绍了带流水作业的工程项目调度问题，这是项目网络中带有流水作业子网络的项目调度问题。它不仅带有常规的时序和资源约束，还带有流水作业所带来的特殊约束。首先给出了带流水作业工程项目调度问题的描述；进而提出一种解决该问题的遗传算法。该算法引入了基于项目划分的编码方式，将个体划分为流水基因段和非流水基因段，并分别进行遗传操作。最后对提出的算法进行了数值计算验证，结果表明了算法的有效性。     

Hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints and limited buffers

This paper presents a genetic algorithm for an important production scheduling problem. Since the problem is NP-hard, we focus on suboptimal scheduling solutions for the hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints, and limited buffers. The production environment of a television assembly line for inserting electronic components is considered. The proposed genetic algorithm is a modified and extended version of the algorithm for a problem without limited buffers. It takes into account additional limited buffer constraints and uses a new crossover operator and stopping criteria. Experimental results carried out on real production settings show an improvement in scheduling when the proposed algorithm is used.     

基于至少连续满足弱硬实时限制的调度算法

对至少连续满足弱硬实时限制的性质进行了扩充，提出并证明了任务不满足子序列长度与任务连续满足的截止期限数之间的关系.在此基础上提出了改进的弱硬实时限制调度算法：MRA．MRA用于在弱硬实时系统中保证任务满足至少连续满足限制，是一种高效、易于实现的调度算法,仿真实验的结果表明，MRA调度算法在提高任务对限制的满足率和保证任务实时性方面优于同类算法．     

Course scheduling algorithm based on improved binary cuckoo search

Course scheduling is a combinatorial optimization problem with multiple constraints. To achieve the reasonable allocation of teaching resources, all courses should be arranged under a number of specified constraints. With the increased number of courses, the solution space increases exponentially. However, the traditional methods cannot quickly find the optimal solution. In order to overcome the disadvantages of low efficiency and the possibility of high conflict in traditional course scheduling, this research study proposes a course scheduling, method based on an improved binary cuckoo search algorithm (IBCS). First of all, a multi-objective and multi-constraint mathematical model of course scheduling is established. Course scheduling involves issues, such as allocating teachers, courses, classes, classrooms and time under specific constraints. The class element is defined to represent the class and the course that the teachers will teach. Therefore, the problem of course scheduling is transformed into the process of mapping from the class element to the classroom-time pair. Six hard constraints and three soft constraints are also defined accordingly. Then, the BCS algorithm is used to search the best course scheduling scheme in the binary-encoded solution space. In order to control the convergence rate effectively and avoid falling into the local optimum, a dynamically adjustable, equilibrium coefficient is introduced. Therefore, the algorithm retains the diversity of the solutions while converging. Finally, this research study constructs the data set and carries out the simulation experiment. It also compares the IBCS algorithm in this paper with the genetic algorithm and the standard binary cuckoo search algorithm (BCS). Experimental results show that the IBCS algorithm can converge in effective time. Meanwhile, it can achieve an improved global scheduling scheme with higher stability.

     

基于模糊偏好的多目标成像卫星调度方法研究

不确定条件下的成像卫星调度问题是一个多目标优化问题。借鉴连续函数的鲁棒性优化思想,提出了一种基于邻域的鲁棒性指标,考虑多种约束条件,建立了多目标成像卫星调度模型。在考虑目标间偏好的情况下,提出了一种基于模糊偏好的多目标遗传算法。实例研究表明,该模型和算法能够有效地解决不确定条件下的成像卫星调度问题。     

满足偏序约束的在线调度

具备偏序关系的实时调度要求调度算法产生的执行序列既要满足任务的实时约束,又要满足任务间执行的偏序约束。基于并行拓扑排序,提出一种新的在线调度算法,该算法通过同时考察任务间执行的串行性和并行性来进行优先级设置,能够处理释放时间任意的任务集。给出该算法的原理和设计,并通过示例分析和比较对算法进行验证。     

汽车维修车间作业排序的优化模型及调度算法*

针对汽车维修车间调度缺乏科学规划,导致较长的客户等待时间和较低的设备利用率的问题,在结合优化调度理论的基础上, 对这一实际调度问题的特性、模型和算法进行了研究。首先从最小化目标、机器环境、加工特征和约束几方面分析了问题的特征,建立了对应的数学模型;然后根据问题特性设计了分解法与约束引导的启发式算法相结合的调度算法;最后以实例分析验证了算法的可行性。仿真结果表明了所用算法在优化目标函数值上的优越性。     

一种能量收集嵌入式系统自适应调度算法

能量收集嵌入式系统(energy harvesting embedded system,简称EHES)的任务调度算法需要考虑能量收集单元的能量输出、能量存储单元的能量水平和能量消耗单元的能耗.实时任务在满足能量约束的条件下,才可能满足时间约束.在这个背景下,传统固定优先级调度算法不再适用于EHES.提出一种基于分组的自适应任务调度算法,它能根据能量收集单元由于能量输出的不确定性而造成的非能量约束情况和能量约束情况,自适应地选择任务调度算法.在非能量约束的情况下,减少任务抢占次数,增强任务的可调度性;在能量约束情况下,减少电池模式切换次数,提高能量存储单元的平均能量水平,从而降低系统能量约束.在一个可进行大范围任务集合仿真的实验环境下对提出的算法进行验证,并将基于分组的自适应调度算法与现有的两个经典算法进行了对比.     

移动微云任务迁移与调度

为了解决移动微云中时间期限约束下的任务能效调度问题,提出一种基于自适应概率的分布式任务调度算法。算法分为两个阶段:资源发现阶段和自适应概率调度阶段。第一阶段主要通过修正的QoS OLSR协议,使发送任务执行请求的源节点周期性地收集邻近处理节点的资源信息;第二阶段主要根据源节点的任务到达率,以概率计算方式选择最优的处理节点执行任务,在满足时间约束的同时,达到最优的能效。经过大量仿真场景的验证,结果表明该算法在维持较高的任务完成率的同时,还可以降低任务完成的平均能耗。