一种求解多目标资源受限项目调度的遗传算法

采用基于非支配性排序的多目标遗传算法—NSGA－Ⅱ,设计了一种求解多模式、多种类资源约束的多目标资源受限项目调度问题的遗传算法,该算法所设计的编码包含两部分,一部分为一个任务链表,另一部分为任务链表中各任务所对应的执行模式组成的模式向量。将所设计的算法用于求解文献中的以项目总工期和资源均衡为目标的农业项目调度问题,结果表明此算法对于求解多目标资源受限项目调度问题是有效的。     

虚拟计算环境中的多机群协同调度算法

基于虚拟计算环境的核心机理,提出由自主调度单元、域调度共同体、元调度执行体为核心的多机群协同系统框架.剖析多机群任务并发运行性能模型,设计了多机群协同调度算法框架,提出最大空闲节点优先、最小网络拥塞优先、最小异构因子优先与最小异构空闲节点优先4种启发式资源选择策略.实验验证了协同调度模型与算法在任务集完成时间与系统平均利用率的测度上的有效性.     

协同设计环境中任务分解与调度的研究

在协同设计环境中,为了满足快速响应,低成本和高质量产品的设计需求,进一步提高产品的设计效率,提出了两级任务分解方法和双向选择优先的任务调度策略.借助计算机支持的协同设计技术,两级任务分解在协同设计联盟的抽象层次模型的基础上,采用了基于产品结构、特征服务和子任务目标属性的任务分解方法,从而降低了任务的复杂性.在此基础上,提出了双向选择优先的任务调度策略,以优化分布合作求解问题,并进行调度策略的仿真实验.仿真结果表明了该调度策略的优越性.     

基于分层优化的资源受限系统任务拆分调度方法

为挖掘资源受限系统的服务潜力,提出一种考虑任务拆分执行方式的调度方法。分析资源调配中所需遵循的约束条件,并以任务满足率为优化目标建立规划模型。设计问题求解框架,提出多层优化算法结构。其中,改进粒子群算法被应用于决策层问题求解,可通过种群进化实现对问题解空间的快速搜索。将冲突规避策略和任务拆分规则应用于逻辑层,能够根据资源稀缺程度进行任务切割,并根据需求分布挑选低重叠度时段进行分配。在仿真实验中,对该方法进行组合测试,分析结果验证了该方法的有效性。     

项目调度与物料订购集成优化研究综述

在项目管理实践中,活动安排与物料供应相互影响、相互制约,需要对这两个决策事项进行协同管理和规划.项目调度与物料订购集成优化问题(project scheduling and material ordering problem, PSMOP)研究的是如何合理制定项目调度和物料采购协同计划,以实现项目总成本最低、净现值最大、总工期最短等目标. PSMOP因其重要的理论价值和应用前景,近年来受到学术界和产业界的广泛关注.鉴于此,对国内外项目调度与物料订购集成优化的相关研究成果进行系统性总结与梳理:首先,介绍PSMOP问题及其常见的目标函数;其次,针对确定和不确定环境,分别总结了考虑不同特征的集成优化问题研究进展;然后,归纳了PSMOP常用求解算法及其在实践领域的应用情况;最后,指出未来进一步的研究方向.     

软件开发项目中任务调度的混沌遗传算法

考虑了软件开发任务的可拆分特性，针对其调度问题提出了最小化项目总周期的优化模型，并提出了一种混沌遗传算法用于求解该模型,该算法的变异算子采用一维Logistic映射作为混沌变异模型，利用混沌系统的漂移特性改善种群的多样性,给出了算法基于任务优先级的编码方案、任务单元解码规则以及遗传算子的设计方法．通过仿真实例验证了模型和算法的有效性．     

考虑胜任力水平的研发项目群人力资源调度

在资源受限项目调度问题中,将可更新资源进一步拓展为具有胜任力差异的人力资源,建立考虑胜任力差异的人力资源受限项目调度问题模型,该模型是对传统多模式资源约束项目调度问题（MRCPSP）更接近研发项目群实际的扩展。提出了衡量人员胜任力的参数及估算公式,以多项目总工期和总成本最小化为双目标,建立相应的数学优化模型。按双目标重要性排序,依次对工期最优及成本最优的单目标优化问题求解。根据模型的约束条件将多项目初始网络图转化为几种单项目初始网络图,利用枚举算法给出满足约束条件的可行解集,再设计基于动态规划思想的算法进行分阶段寻优。数值实验表明,考虑了胜任力差异的数学优化模型在求解质量方面具有良好性能。     

资源受限多项目调度问题的两阶段算法

在资源受限项目调度问题中,将可更新资源进一步拓展为具有胜任力差异的人力资源,建立考虑胜任力差异的人力资源受限多目标项目调度问题模型.该模型是对传统多模式资源约束项目调度问题更接近研发项目群实际的扩展.针对模型提出两阶段优化算法,第1阶段是项目时序约束优化阶段,采用蚁群算法(ACO)进行任务列表的优化求解,通过对信息素增量规则的改进、串联进度生成机制(SSGS)及资源冲突消解策略的使用,使蚁群算法的求解效率和质量得以提高;第2阶段是资源约束优化阶段,以第1阶段求得的优化任务列表为输入,逐项对人力资源约束进行核查与调整,最终生成项目调度的优化方案.数值实验表明,考虑胜任力差异的数学优化模型更符合研发项目群管理实践,同时两阶段算法在求解质量方面具有良好性能.     

面向建材装备集团制造的分布式多项目资源调度

针对建材装备集团项目执行过程中存在的项目内和项目间多类别资源协同共用现象,提出并行调度机制下考虑多类别资源转移时间和转移成本的分布式多项目资源调度问题,以最小化资源转移成本和项目执行工期为目标建立问题的数学模型.为改善进化算法在局部搜索能力方面的不足,提出将禁忌搜索与进化算法相结合,构造一种内嵌禁忌搜索寻优搜索的多目标混合进化算法,在保证算法全局搜索能力的前提下提升局部精确搜索能力.同时,考虑资源转移成本和时间对任务选取的影响,改进任务选择的优先权值,提出并行调度机制下资源转移冲突消解策略.数据实验表明,所提算法能够有效避免不合理的资源转移,在求解质量方面具有良好的性能.     

不确定环境下项目拆分和带缓冲时间的多项目协同调度研究

针对不确定环境下移动式装配的项目存在项目工期随机延长的问题,首先引用项目拆分思想,将单项目虚拟拆分成多项目;在加入最大鲁棒性约束下,以最小化项目工期为目标建立数学优化模型。并提出了改进的两阶段循环算法求解：项目划分阶段通过子项目拆分算法进行子项目划分;项目调度阶段以布谷鸟算法为框架对划分后的多项目调度进行求解,并将调度结果反馈至上阶段。最后选取PSPLIB算例库中不同规模的算例,分析各种参数在不同规模下对项目计划的影响。实例验证结果表明,所提方法能在不确定环境下提高项目资源利用率并缩短工期。     

Multi-mode resource-constrained project scheduling problems with non-preemptive activity splitting

In this paper, we explore the difference between preemption and activity splitting in the resource-constrained project scheduling problem (RCPSP) literature and identify a new set of RCPSPs that only allows non-preemptive activity splitting. Each activity can be processed in multiple modes and both renewable and non-renewable resources are considered. Renewable resources have time-varying resource constraints and vacations. Multi-mode RCPSP (MRCPSP) with non-preemptive activity splitting is shown to be a generalization of the RCPSP with calendarization. Activity ready times and due dates are considered to study the impact on project makespan. Computational experiments are conducted to compare optimal makespans under three different problem settings: RCPSPs without activity splitting (P1), RCPSPs with non-preemptive activity splitting (P2), and preemptive RCPSPs (P3). A precedence tree-based branch-and-bound algorithm is modified as an exact method to find optimal solutions. Resource constraints are included into the general time window rule and priority rule-based simple heuristics are proposed to search for good initial solutions to tighten bounding rules. Results indicate that there are significant makespan reductions possible when non-preemptive activity splitting or preemptions are allowed. The higher the range of time-varying renewable resource limits and the tighter the renewable resource limits are, the bigger the resulting makespan reduction can be.     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

基于改进遗传算法的资源限制建设工程多项目调度

随着建设工程企业规模的不断扩大,工程建设多项目管理成为企业发展的重要难题之一,对组织实现可持续发展有着重要的支撑作用。本文在资源限制单项目调度问题的基础上提出建设工程多项目调度问题,构建RCMPSP决策框架和数学模型,并在传统遗传算法的基础上对算法杂交和变异概率进行优化,设计针对该问题的改进遗传算法,通过案例对该算法的有效性进行验证,为建设工程企业进行RCMPSP问题决策提供依据。     

A random generator of resource-constrained multi-project network problems

Many scheduling problems in project management, manufacturing, and elsewhere require the generation of activity networks to test proposed solution methods. Single-network generators have been used for the resource-constrained project scheduling problem (RCPSP). Since the first single-network generator was proposed in 1993, several advances have been reported in the literature. However, these generators create only one network or project at a time; they cannot generate multi-project problems to desired specifications. This paper presents the first multi-network problem generator. It is especially useful for investigating the resource-constrained multi-project scheduling problem (RCMPSP), where a controlled set of multi-project test problems is crucial for analyzing the performance of solution methods. In addition to the single-project characteristics handled by existing network generators—such as activity duration, resource types and usage, and network size, shape, and complexity—the proposed generator produces multi-project portfolios with controlled resource distributions and amounts of resource contention. To enable the generation of projects with desired levels of network complexity, we also develop several theoretical insights on the effects of network topology on the probability of successful network generation. Finally, we generate 12,320 test problems for a full-factorial experiment and use analysis of means to conclude that the generator produces “near-strongly random” problems. Fully “strongly random” problems require much greater computational expense.     

一种基于虚拟截止时间制导的改进的Min—Min元任务调度算法

在网格环境下，资源状况和用户行为相当复杂，是一个异构计算环境，元任务（meta—task）调度比传统并行调度更为复杂。如何映射一组任务到一组机器上被证明是NP问题，其目的一般是最小化任务完成时间（makespan）。为解决这一问题，已经提出一些启发式任务调度算法，例如具有代表性的MinMin元任务调度算法。本文在Min-Min元任务调度算法的基础上，通过虚拟截止时间制导的方法来改进Min-Min算法。实验结果表明，本文提出的算法具有更短的任务完成时间。     

Group scheduling problem: Key to flexible manufacturing systems

We present an efficient heuristic algorithm for determining the sequence which minimizes the makespan of a group scheduling problem at the first level. The problem, therefore, focuses on scheduling of parts (jobs) in a part family. In the generation of partial schedules at each iteration, a job with a high mean total processing time is given a higher priority than others. An example problem, chosen from a real world application, is used to implement, the algorithmic steps. For this example, it has also been shown that the makespan determine by the proposed heuristic is smaller than that determined previously by two documented algorithms.     

云环境中基于分解的多目标工作流调度算法

云服务提供商在给用户提供海量虚拟资源的同时,也面临着一个现实的问题,即怎样调度这些资源,以最小的代价(完工时间、执行费用、资源利用率等)完成工作流的执行。针对IaaS环境下的工作流调度问题,以完工时间和执行费用作为目标,提出了一种基于分解的多目标工作流调度算法。该算法结合了基于列表的启发式算法和多目标进化算法的选择过程,采用一种分解方法,将多目标优化问题分解为一组单目标优化子问题,然后同时求解这些单目标子问题,使得调度过程更为简单有效。算法利用天马项目发布的现实世界中的工作流进行实验,结果表明,和MOHEFT算法以及NSGA-II*算法相比较,所提出的算法能得到更优的Pareto解集,同时具有更低的时间复杂度。     

基于深度强化学习的随机资源受限多项目动态调度策略

目前对于随机工期的分布式资源受限多项目调度问题（SDRCMPSP）的研究较少且大多数为静态调度方案,无法针对环境的变化实时地对策略进行调整优化,及时响应频繁发生的动态因素。为此建立了最小化总拖期成本为目标的随机资源受限多项目动态调度DRL模型,设计了相应的智能体交互环境,采用强化学习中的DDDQN算法对模型进行求解。实验首先对算法的超参数进行灵敏度分析,其次将最优组合在活动工期可变和到达时间不确定两种不同条件下对模型进行训练及测试,结果表明深度强化学习算法能够得到优于任意单一规则的调度结果,有效减少随机资源受限多项目期望总拖期成本,多项目调度决策优化提供良好的依据。     

Scheduling of collaborative operations of yard cranes and yard trucks for export containers using hybrid approaches

Optimizing collaborative operations for yard cranes (YCs) and yard trucks (YTs) is vital to the overall performance of a container terminal. This research investigates four different hybrid approaches developed for dealing with yard crane scheduling problem (YCSP) and yard truck scheduling problem (YTSP) simultaneously for export containers in the yard side area of a container terminal. First, these approaches use a load-balancing heuristic to assign containers to YCs evenly. Following this, each of them employs a specific heuristic/metaheuristic, such as genetic algorithm (GA), particle swarm optimization (PSO) or subgroups PSO (SGPSO), to generate alternative container loading sequences for each YC. Finally, a simulation model is used to simulate loading and transporting of these export containers, evaluate alternative planning results, and finally output the best planning result. Experiments have been conducted to compare these hybrid approaches. The results show Hybrid4 (SGPSO) outperforms Hybrid1 (Sort-by-bay), Hybrid2 (GA), and Hybrid3 (PSO) in terms of makespan.