基于深度学习的RCPSP调度优先规则实时动态选择算法

针对资源受限项目调度问题,以最小化项目完成时间为目标,设计基于深度学习的调度优先规则实时动态选择算法,在每个调度阶段实时选择优先规则进行活动安排.通过构建深度神经网络模型,确定已调度项目在各阶段的项目状态与最佳优先规则之间的映射关系,再据此为待调度项目实时动态选择优先规则,结合串行调度机制生成最终调度计划.实验研究表明:实时动态选择优先规则算法表现优于文中所涉及的单一优先规则算法及混合优先规则算法,且具有更好的泛化性;此外,与元启发式算法相比该算法具有更高的求解效率.     

基于优先规则的活动成本目标资源受限工程调度

首先给出了该问题的数学模型,问题分析得出该问题也是一类NP完全问题,继而讨论了启发式方法进行问题求解的基本思想,基于此,结合活动成本目标的特性提出了问题求解的串行调度方案和并行调度方案,并设计了相应的几种优先规则,分析了算法的时间复杂性.基于改造PSPLIB中的单模式算例测试,并行调度方案的结果大多优于串行调度方案,而在最大最早完成时间和最大活动先序相关成本等两种优先规则下的调度方法计算效果相对较好.     

生产作业计划调整的优先调度算法研究

本文基于生产作业计划生成的优先调度法,提出了针对生产作业计划调整的机床优先调度算法和工件优先调度算法。在机床优先调度算法中,设计了机床优先调度算法的步骤。而在工件优先调度算法中,利用归纳学习方法,研究了面向生产系统状态的生产作业计划调整方法。     

基于权值的优先调度算法

介绍了经典的期限最近优先调度算法，分析了优先级倒置难题。提出一种基于权值的优先调度算法。该算法对资源分配权值，建立任务的权值评价函数。该算法由资源权值表和评价函数来实现。实验表明，该算法资源分配更合理，特别是能够克服期限最近优先调度算法的优先级倒置难题，从而更加有效提高实时操作系统的实时性能和稳定性。     

网络化制造模式下基于改进蚁群算法的供应链调度优化研究

为制定网络化制造（networked manufacturing,NM）模式下供应链合作成员间的动态调度策略,构建了由制造商、协同设计商以及客户组成的三层动态调度模型;在生产能力约束、多目标优化约束等制约因素下,采用时间函数、成本函数和延期惩罚函数三个目标函数对调度问题进行描述;使用改进蚁群算法（improved ant colony optimization algorithm,IM-ACO）,对调度路径可行解节点添加不同的信息素,并将信息素浓度约束在τ_min和τ_max之间,使得供应链客户个性化需求服务、运作时间、成本等综合收益达到最优. 实例仿真表明本文提出的动态调度优化算法求解具有较快的搜索速度、收敛性好,算法具有较好的稳定性;同时,也表明本文构建调度模型合理,可以为实际生产调度提供优化的策略.     

给出方案优先序的模糊多属性决策方法

针对属性值为模糊变量,属性权重完全未知但给出方案优先序信息的模糊多属性决策问题给出决策方法.该方法通过建立一个二次规划模型来确定属性的权重,进而通过求解一个以极大化方案总贡献为目标的0-1规划模型来获得方案的排序及最佳方案.最后给出了应用算例.     

基于稳定性的生产调度建模

针对传统调度模型得出的方案由于决策参数变化而不能应用于实际生产等问题,分析了在实际生产环境中可能导致重调度的各种不确定因素,从调度稳定性的角度使用两阶段随机规划方法重新设计了包含随机参数的模型,不仅使调度可以稳定在某置信水平上,而且允许调度结果以一定的风险获取更好的性能指标。最后,应用一个化工调度模型讨论了新方法的特点。     

基于综合优先度的卫星数传调度算法

研究了在地面站资源有限、数传任务急剧增多的情况下,合理分配资源以有效实现卫星数传任务的调度问题.首先建立了卫星数传任务模型和调度问题模型,提出了综合优先度的概念及其各个指标,对每个指标进行了详细分析.在此基础上,提出了一种基于综合优先度的卫星数传调度算法。仿真结果表明该算法能够取得较好的调度结果.     

具有时间窗口约束的并行机床调度问题研究

具有时间窗口约束的并行机床调度问题可以被描述为在M台互不相同机器上安排加工N个工件。每个工件只能在一个给定机器子集中的一台机器上加工，且加工过程只能在给定的离散时间窗口内进行，并且工件的加工时间长度和时间窗口约束与加工机器有关。为了解决该问题，本文给出一种集成约束规划与禁忌搜索的搜索算法，其中约束规划系统被作为验证解的可行性和确定变量的值，而禁忌搜索过程被用来对解空间进行搜索。讨论禁忌搜索过程中的初始解产生、邻域结构、禁忌列表、解空间搜索等算法设计问题。最后给出算法在不同问题实例上的算法效率比较及分析。     

基于优先缺货权的工厂生产计划的动态规划模型

对满足一定市场需求量情况下的工厂生产计划，建立一动态规划模型，在模型求解过程中，提出了优先缺货权准则，并在此准则下寻找最优解。这一方法的引入，对实际问题的处理有一定的指导意义。     

An improved branch-and-bound algorithm to minimize the weighted flowtime on identical parallel machines with family setup times

This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.     

Scheduling algorithm based on critical tasks in heterogeneous environments

Heterogeneous computing is one effective method of high performance computing with many advantages. Task scheduling is a critical issue in heterogeneous environments as well as in homogeneous environments. A number of task scheduling algorithms for homogeneous environments have been proposed, whereas, a few for heterogeneous environments can be found in the literature. A novel task scheduling algorithm for heterogeneous environments, called the heterogeneous critical task （HCT） scheduling algorithm is presented. By means of the directed acyclic graph and the gantt graph, the HCT algorithm defines the critical task and the idle time slot. After determining the critical tasks of a given task, the HCT algorithm tentatively duplicates the critical tasks onto the processor that has the given task in the idle time slot, to reduce the start time of the given task. To compare the performance of the HCT algorithm with several recently proposed algorithms, a large set of randomly generated applications and the Gaussian elimination application are randomly generated. The experimental result has shown that the HCT algorithm outperforms the other algorithm.     

时序约束下科学工作流的动态调度研究

随着分布计算技术的迅速发展,利用广域分布的计算资源构建并执行科学工作流,已成为当前学术界和工业界关注的热点问题.为满足用户和计算控制机制的需求,往往需定义科学工作流的时序约束.但是,由于任务处理时间具有不确定性,在运行过程中容易出现时序违反.为保证科学工作流的正确执行,迫切需要能根据实时运行状态自动实现动态调度的方法.针对已有研究方法的不足,本文提出了一种基于遗传蚁群混合算法的科学工作流动态调度优化方法.首先,建立了时序约束下的科学工作流动态调度模型,该模型综合考虑了科学工作流的时间与成本优化目标,并融合了基于概率的时序约束满足性需求;然后,采用改进的遗传蚁群混合算法实现模型求解.该算法通过设计提高种群搜索导向性及保持种群多样性的策略,从求解精度及求解速度两方面提高了求解效率.最后,通过与现有方法的多组实验对比,说明了本文算法的优越性.     

多技能资源时间窗约束下可中断项目调度的分支定界算法

资源的多技能和时间窗属性是软件开发、工程设计、设备维修等领域在人力资源调度时常考虑的关键因素,而且在很多实际项目中,任务的执行允许中断.研究一类资源具有多技能和时间窗约束的任务可中断项目调度问题,建立了相应的整数规划模型,设计了一种分支定界算法构造搜索树进行求解,搜索树的每个节点代表一个任务组合,同时为减少分支节点数,提出了两个有效的剪枝规则,并设计了节点优先规则,对各节点任务组合则采用贪婪算法来进行资源约束判断.利用改进的PSPLIB案例库设计多组计算实验,实验结果检验了优选策略的有效性,经与CPLEX模型求解和基本启发式方法的对比揭示了算法在解决这类问题上的效率和有效性,求解结果可为实际项目调度提供决策依据.     

局外k—出租车问题及其动态规划求法

局内问题及其解法在研究是优化领域研究热点之一,而有关局内问题解法的研究必将涉及相应的局外问题。提出了局外k-出租车调度问题,给出了问题的动态规划求解方法,并给出该问题的一个具体算例。同时简要地介绍了局外k-卡车调度问题的动态规划求解方法。     

带有限缓冲区的知识化制造单元无死锁调度

鉴于制造系统无死锁随机调度问题研究的缺乏,在加工时间、工件到达以及产品需求到达均为随机的生产环境下,研究了带有限缓冲区的知识化制造单元无死锁随机调度问题.针对自动机对定量指标描述能力的不足,首先给出了一种费用自动机概念.在同时考虑工件加工、库存以及缺货费用的情况下,采用无限时域折扣准则下马尔可夫链建立了单元的费用目标函数,通过一致化技术对目标函数进行离散化处理,得到目标函数的随机动态规划模型,分析并证明了单元最优目标值函数的性质.为了克服离散状态空间组合所产生的维数灾问题,提出了一种基于仿真和函数逼近的启发式近似动态规划算法对模型进行求解.在上述研究基础上,构建了一种单元无死锁随机调度策略,以保证单元安全高效地运行.最后,通过实例研究对无死锁调度策略进行了验证.     

基于规则导向的柔性作业车间多目标动态调度算法

设计了一种具有柔性资源约束的多目标集成优化方法,建立了包括最小完工时间、最小生产成本、最大设备利用率、最大交货满意度和最优人工分配在内的多目标组合优化模型;为降低模型的复杂度,抑制组合优化模型的状态爆炸效应,采用规则导向的资源调度思想,通过调整规则概率使概率大的规则被优先选中,从而"推动"搜索过程向预期目标方向移动;采用改进的非支配排序遗传算法—NSGA-Ⅱ获得不同规则概率值的Pareto解集,并结合动态规划法求解最优人员分配方案;仿真对比与算例验证,本文算法可以有效解决柔性作业车间多目标调度优化问题.     

多模式项目支付进度的整合优化研究

首先明确了研究的假设条件并对符号进行了定义;随后分别从承包商和业主各自的角度构建了多模式项目支付进度的优化模型;在此基础上讨论了项目融资费用分担问题并对双方整合角度的多模式项目支付进度问题进行了界定,构建了由两个优化模型集成的双方整合角度优化模型,求解该模型可以获得使双方联合收益最大化且按照商定比例分担项目融资费用的支付进度安排;最后,通过一个实例的计算分析对本文的研究成果进行了说明.     

有新任务插入的多星动态调度模型与算法研究

对地观测卫星动态调度问题是一类复杂的调度问题.在对动态调度的要求进行分析的基础上,针对有新任务插入的多星动态调度问题的特点,建立了多星动态调度模型,提出了一种基于自由度规则的动态启发式求解算法.分别设计了基于最大自由度的退出启发式规则和基于自由度比例的退出启发式规则,采用深度有限搜索策略进行迭代搜索.仿真实例分析表明,基于自由度规则的动态启发式求解算法能够较好地解决有新任务插入的多星动态调度问题.     

基于多目标遗传算法的卫星成像任务调度技术

针对成像卫星的任务调度问题,考虑多种约束条件,提出了成像任务约束图模型。基于多目标优化和遗传算法思想,提出了一种应用于卫星成像任务调度的多目标遗传算法,详细分析了算法的各个关键步骤的设计思想,能够求得基于成像约束图模型的满意解,生成卫星的优化拍摄计划。卫星成像任务调度原型系统的实现和实验结果验证了该模型和算法的合理性和有效性。