基于优化资源流约束的模具多项目反应调度算法

针对模具多项目执行过程中由于任务拖期而导致的调度计划变更,提出了一种基于优化的资源流约束的反应调度算法. 首先利用基于优先规则的微粒群算法构建一个项目加权工期之和最小的初始调度计划,采用启发式算法建立并优化初始调度计划的资源流网络,并将关键链技术与资源流网络相结合,对初始调度计划进行合理的时间缓冲设置. 然后建立了以调度计划扰动费用最小为优化目标的反应调度模型,并用基于优先规则的微粒群算法进行求解. 最后,通过仿真计算分析了算法的可行性与可靠性,结果表明该反应调度算法在模具多项目动态调度中具有一定的应用价值.     

资源受限项目组合选择及调度的双层决策方法

在资源受限条件下,综合考虑项目选择与项目调度,以最大化项目组合收益为目标函数,建立了一般化的资源受限项目组合选择及调度问题的数学模型。针对问题特性,设计了双层决策方法用于求解该问题。上层决策采用改进的蚁群优化算法求解项目组合选择问题,下层决策则采用基于优先规则的多项目调度启发式算法。采用实验设计方法系统生成24个项目组合选择与调度问题实例,对算法效果进行了对比检验。结果表明:所设计的双层决策方法对于项目组合选择及调度问题具有较好的求解效果;所建立的数学模型与解决方案能够为决策者提供平均收益更高的项目组合。     

基于优先规则的复杂并行机调度问题研究

研究一类从实际指挥控制系统提炼的具有工件释放时间、机器可用时间和机器适用限制等约束的并行同速机调度问题.首先针对该问题建立混合整数规划模型;其次考虑到该问题的NPhard性以及实时调度的要求,提出基于优先规则的调度算法框架从而可以快速获得可行解;最后将该算法框架应用到实际案例并分析比较不同优先规则的效果,发现与工件释放时间相关的优先规则(如ERD,EFD)效果更好.值得一提的是,本文首次研究具有多重约束的并行机调度问题Pm|r_j,a_i,M_j|C_(max),TC.     

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

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

基于混合流水作业组织的港口拖轮调度优化

在对拖轮调度问题进行分析的基础之上,将拖轮调度问题归结为一类具有多阶段共用机器特征的混合流水车间调度问题. 建立了针对多停泊基地不同作业模式下、且考虑靠泊与停泊两阶段的拖轮调度优化模型,推导了基于混合流水作业组织的港口拖轮调度优化问题的理论下界值,并设计了启发式规则与模拟退火相结合的混合算法（HSA）求解该模型. 通过运用该算法求解仿真算例,并将其结果与模型理论下界值、三种基于现行调度规则及基于Johnson 规则的调度方案进行比较. 结果表明,运用HSA求解的结果与理论下界值的平均偏差值为5.39%,且该结果远小于基于现行调度规则及Johnson规则的求解值,验证了模型与算法的高效性,可以为拖轮作业模式的选择以及调度方案的制订提供决策支持.     

基于混合流水作业组织的港口拖轮调度优化

在对拖轮调度问题进行分析的基础之上,将拖轮调度问题归结为一类具有多阶段共用机器特征的混合流水车间调度问题.建立了针对多停泊基地不同作业模式下、且考虑靠泊与停泊两阶段的拖轮调度优化模型,推导了基于混合流水作业组织的港口拖轮调度优化问题的理论下界值,并设计了启发式规则与模拟退火相结合的混合算法(HSA)求解该模型.通过运用该算法求解仿真算例,并将其结果与模型理论下界值、三种基于现行调度规则及基于Johnson规则的调度方案进行比较.结果表明,运用HSA求解的结果与理论下界值的平均偏差值为5.39%,且该结果远小于基于现行调度规则及Johnson规则的求解值,验证了模型与算法的高效性,可以为拖轮作业模式的选择以及调度方案的制订提供决策支持.     

飞机着陆调度问题的MPS优化算法研究

以深度优先搜索的隐枚举算法为基础 ,结合 MPS约束、位置冻结限制、优化深度限制 ,使用复杂的软件编码实现了特定于飞机着陆调度问题的优化排序算法 .该算法能满足现实复杂空管条件下的各种限制约束 ,以及多种目标成本函数 ,可应用于静态和动态的实时 ATC自动化系统 ,能有效地减小交通延误和提高着陆容量 .     

基于改进DP算法的具有优先序的变速机最小化成本调度

研究了工件具有任意标准优先序、一台机器在同一时间只可加工一个工件、最小化工件加工成本与机器使用成本之和的变速机调度问题.为该问题建立了DP模型,通过启发式规则和常规动态规划方法相结合、引入工件完工时间界限并保存每一步函数值,得到改进的DP算法,数值实验显示该算法具有较强的寻优能力和稳定性.     

改进Q学习算法在作业车间调度问题中的应用

为解决动态环境下作业车间调度问题,提出了一种基于改进Q学习算法和调度规则的动态调度算法。以“剩余任务紧迫程度”的概念来描述动态调度算法的状态空间;设计了以“松弛越高,惩罚越高”为宗旨的回报函数;通过引入以Softmax函数为主体的动作选择策略来改进传统的Q学习算法,使改进后的Q学习算法在前期选择不同动作的概率更加平等,同时改善了贪婪策略在学习后期还会选择次优动作的现象。仿真结果表明：该调度算法相较于改进前,性能指标平均提升约6.5%;相较于IPSO算法和PSO算法,性能指标平均提升分别约为38.3%和38.9%,调度结果明显优于使用单一调度规则以及传统优化算法等常规方法。     

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

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

复杂时间约束的水利工程项目调度问题研究

水利工程项目的调度属于资源受限的项目调度问题,但现实中这类项目存在着一种复杂的时间约束,即项目中的某些活动在特定时间段内不允许执行.针对这类特殊约束,本文提出了一种新的资源受限项目调度扩展模型,设计了多优先规则的启发式算法进行求解.并在此基础上提出了一种混合遗传算法,构造了新的交叉算子同时结合精英保留和双对齐技术来改善解的质量.最后,用调整后的项目调度问题库(project scheduling problem library)大量实例验证了算法的有效性.     

资源约束下多项目调度的拓扑优化方法

为了有效解决带有项目优先权约束和资源约束的多项目调度问题,综合考虑项目调度过程中任务的时序关系和资源限制,以拓扑遍历方法为基础,提出了一种多项目调度问题的拓扑优化算法。该算法利用拓扑序列的特点,能够保证任务间的时序关系,采用关键路径任务优先、向后影响度大以及最小空闲时间等优先规则进行任务调度及资源分配。结合工程实例,验证了该算法的可行性。     

基于仿真的双目标并行机开放车间自适应动态调度

针对工件到达时间与加工时间不确定，且存在紧急工件的并行机开放车间调度问题，以TWC(total weighted completion time)与TWT(total weighted tardiness)为优化目标，设计了一种集成FlexSim仿真模型与NSGA-Ⅱ算法的自适应动态调度方法。该方法以FlexSim模型仿真工件的生成和加工为基础，根据车间实时负荷确定动态调度周期，对紧急工件进行右移重调度，利用NSGA-Ⅱ算法生成双目标优化的调度方案。某晶粒拣选车间生产数据的实验结果表明，相较于利用规则的实时动态调度与固定周期重调度，提出的方法能够在最小化调度偏离度的同时获得满意解。     

资源多时间窗约束下的项目调度

资源受多时间窗约束在项目管理实践中时常出现,却在资源受限项目调度的研究中很少涉及。根据资源的多时间窗特点,建立以成本最小化为目标、考虑资源多时间窗约束的项目调度优化问题的数学模型,提出基于优先规则的倒推右移调度方法,开发相应的优先规则。经算例测试,对比分析资源时间窗在不同的配置水平下对项目成本和工期的影响,并对活动网络复杂性和不同的优先规则下的结果进行比较。结果表明,基于优先规则的倒推右移调度方法可以有效地求解问题,项目目标在倒推右移操作后有明显改善,考虑任务资源时间窗匹配和最小后序活动静态成本的混合优先规则求解效果较好。     

基于指标函数的舰载机机队回收调度优化研究

由于复飞逃逸、飞行故障等因素随机发生, 传统静态调度方法难以有效解决动态随机调度问题。对此,提出一种基于飞机优先序指标函数的蒙特卡罗模拟-差分进化搜索的实时调度算法。在离线模拟回收环境下,由算法完成基于随机模型的指标函数系数优化,后由该指标函数实现对机队优先序的实时评估排序,进而完成回收在线动态调度。仿真结果表明所提算法能有效解决回收调度问题。在相同机队初始输入下, 目标值呈现较好统计特性, 其期望值能够快速收敛到一定范围, 且无复飞情况下着舰时间窗目标呈显著正态性; 不同回收机队输入对指标系数最优值的散布较小, 表明指标函数评估优先序具有较好的通用性和有效性; 模拟回收调度发现, 着舰成功率的提高将显著降低机队复飞次数, 提高回收效率。     

基于蚁群算法的海洋工程群项目资源调度研究

针对海洋工程项目管理的热点问题——群项目管理中的难点,即人力、资金、设备及材料等资源的合理、动态调度问题,提出了一种基于蚁群算法(ACO)的资源调度方法.该方法利用群项目间资源调度问题与旅行商问题(TSP)的相似性,结合ACO算法的特点,将资源需在各个分项目中占用的时间与资源的急需程度与之比作为算法中的启发式信息进行处理.海洋工程群项目管理中资源调度的实例表明,该方法实现了资源的合理、动态调度,为海洋工程群项目管理提供了一较为有效的资源调度算法,对提高我国海洋工程及其他领域群项目管理水平具有一定意义.     

大型活动的安保警力部署和调度优化研究

近些年,我国大型活动(特别是大型体育活动)数量逐渐增多,规模日益扩大,活动中潜在的风险和威胁也随之增加,由此衍生出巨大的活动安保警力需求,这与有限的警力资源之间产生的矛盾就成为亟需解决的问题.通过对大型活动安保实践的调研,构建了警力部署点的数量与风险损失的函数关系,并建立了最小化预期风险损失的静态警力部署模型,以及在风险发生后有效调度警力的动态警力调度模型,准确刻画了大型活动中的警力初始部署和变动情况.两种模型可以分别用动态规划算法和线性规划算法求解.为使模型在实践中更易推广使用,依据贪婪算法为大型活动的安保警力部署和调度设计了一套优化规则.数值实验结果表明,对于静态警力部署模型,我们给出的优化规则和通过动态规划算法得到的精确解具有良好的近似程度;而对于动态调度模型,优化规则得到的解和线性规划算法得到的精确解在99.5%的情况下完全一致.研究丰富和发展了大型活动中安保警力优化调度的相关理论,也为公安部门的安保实践和相关规则的制定提供了理论基础.     

一类多资源作业车间混合优化调度方法

针对多资源作业车间调度问题,结合启发式算法和遗传算法的特点,提出了混合优化调度方法,建立了多资源约束的车间优化调度模型.根据启发式算法中调度优先规则对调度目标的影响程度,设计了新的编码规则.采用正弦函数作为改进遗传算法中的自适应因子,使交叉概率和变异概率随群体的适应度自动改变,提高了运算的效率.通过实例仿真并与其他算法比较结果表明,该混合调度算法可以进行作业车间在机床、刀具等多种生产资源约束下的优化调度,并在评价指标上较其他算法更优.     

考虑了交箱时间不确定性的场桥堆存作业优化

客户送箱时间的不确定性直接影响出口箱的场桥堆存作业效率和其在集装箱码头堆场的堆存状态,进而增加场桥作业移动距离以及后续装船过程中的翻箱作业量,降低码头作业效率.针对该问题通过马尔可夫链预测方法将随机交箱序列转化为广义交箱序列,在此基础上,结合集装箱港口作业实际,建立了以最小化预翻箱数量和场桥堆存作业移动距离为目标的场桥调度优化两阶段数学模型,并分别针对初始决策阶段和实时调度阶段设计了静态与动态求解算法.通过仿真算例,借助于与不同堆存策略的对比,显示了优化模型及算法的实用性与有效性,为场桥调度方案的实时生成提供决策支持.     

应急事件中瓶颈环节的实时优化调度

应急事件中的资源优化调度处于复杂动态的环境中,受到各种随机因素的影响,使得问题求解更加困难。约束理论指出瓶颈决定了整个系统的性能,通过对瓶颈环节的实时调度可以简化问题。用三元组α/β/γ方法分析了应急事件中瓶颈环节优化调度问题的特征,建立了对应的数学模型。运用基于任务的实时调度策略与包含复合动态分派规则的启发式算法进行问题求解。通过仿真结果验证算法的优越性和可行性。