Single machine scheduling with semi-resumable machine availability constraints

This paper considers the semi-resumable model of single machine scheduling with a non-availability period. The machine is not available for processing during a given time interval. A job cannot be completed before the non-availability period will have to partially restart after the machine has become available again. For the problem with objective of minimizing makespan, the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also proposed. For the problem with objective of minimizing total weighted completion time, an approximation algorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latter problem are also considered, and improved algorithms are given.     

两道工序智能加工系统调度模型

研究了两道工序智能加工系统调度问题·该问题为2018年全国大学生数学建模竞赛B题的一部分.系统由一辆轨道式自动引导车(RGV)和若干台计算机数控机床(CNC)等部件组成.以RGV的移动路径和两道工序的CNC分配为决策变量,以RGV在CNC上的操作结束时刻为时间节点,以物料加工剩余时间和RGV的手爪是否被占用为状态变量,给出了问题的数学模型.考虑周期内RGV的移动为固定序时,不同于一道工序问题,两道工序问题的周期长度与CNC的分配有密切的关系.最后给出了基于模型和RGV固定序的算例.     

考虑机器调整次数和产品质量的卷烟批量计划和柔性流水车间调度集成问题

针对卷烟企业生产中的批量计划和柔性流水车间调度集成问题,构建了整数规划模型,目标函数由卷烟生产时间、生产线调整次数、卷烟质量、库存成本四部分组成。鉴于该问题的NP-hard性,设计遗传算法进行求解,通过合理设计遗传算子,避免不可行解出现。应用某卷烟企业数据得到优化排产结果,与该企业之前依照经验排产方案进行对比,发现优化排程结果在减少品牌转换次数,提高生产的连续性方面具有明显优势。该算法已作为某卷烟企业排产人员的排产参考,应用于排产决策中,取得了良好的效果,对卷烟企业制定排产计划具有一定的实际指导意义。     

基于随机活动工期的多模式现金流均衡项目调度优化

承包商在项目执行过程中的现金流均衡是保证项目成功的关键因素。本文研究基于随机活动工期的多模式现金流均衡项目调度问题,旨是在项目工期及鲁棒性阈值约束下合理安排活动执行模式与开始时间,实现承包商现金流均衡。本文通过构建整数规划优化模型对研究问题进行刻画,随后设计模拟退火算法进行求解,最后进行案例分析。结果表明:鲁棒性阈值虽然可以保证基准进度的稳定性,但是提高鲁棒性阈值水平反而不利于承包商的现金流均衡,该值过高时甚至得不到可行解。本文研究可为随机活动工期背景下承包商的现金流控制提供定量化决策支持。     

电力市场环境下计及V2G和多类型需求响应的综合能源系统多目标优化模型

园区综合能源系统(Park integrated energy system,PIES)是满足用户多种用能需求的一种重要途径,但由于内部分布式能源机组出力具有不确定性,且与负荷在时间维度上存在一定的不匹配性,限制了能源利用效率和经济效益的提升.因此,本文首先在构建耦合热电的PIES的基础上,构建了多类型需求响应模型;其次,构建了考虑风光机组出力不确定性的以系统净收益、清洁能源弃能率为多目标函数的优化模型;然后,构建了"不确定性处理-多目标处理-单目标处理"的三阶段求解模型,最后,以V2G和需求响应为考虑条件,设计多情景.算例结果表明:V2G可以为清洁能源不稳定发电提供有效备用,在一定程度上提供清洁能源利用效率;引入电热需求响应,能够改变用户负荷,增加经济效益.     

随机ADMM算法及其在电力系统凸经济调度问题中的应用

针对电力系统中的一类凸经济调度问题,提出了随机ADMM算法,设计了周期循环更新规则和随机选择更新规则,证明了随机ADMM算法在周期循环更新规则下的收敛性,以及得出了在随机选择更新规则下按期望收敛的结论.数值实验结果表明该方法可以有效解决电力系统中的凸经济调度问题.     

考虑翻箱的场桥调度和提箱集卡数量的集成优化

在集装箱码头的进口箱堆场中,码头预约机制、待提箱的实时位置和场桥作业调度方案是制约堆场作业效率和堵塞情况的关键。为缓解进口箱堆场的拥塞情况并提高作业效率,在固定的预约时段内,考虑实时压箱量最少的翻箱规则,兼顾场桥间不可跨越和保持安全间距等现实约束,以场桥最长完工时间最小为目标,构建数学优化模型,设计了嵌入修复算子的改进遗传算法用于求解;通过算例实验验证了算法的有效性和方案的优越性,可为堆场实际作业提供决策参考。     

基于时间窗延迟的资源约束项目调度双层优化研究

本研究从业主—承包商交互的视角构建了一种RCPSP(resource-constrained project scheduling problem)双层优化模型,即在可更新资源约束条件下,项目双方如何进行交互决策达到双方NPV(Net present value)最大化的目标。首先对研究问题进行界定,构建资源约束下的max-NPV项目调度双层优化模型;然后利用延迟优先规则设计了一种基于时间窗延迟的嵌套式自适应遗传算法来求解该模型,以达到双方NPV最大化;最后用一个算例验证算法的有效性,同时通过PSPLIB数值实验说明算法的稳定性,并分析关键参数对项目双方收益的影响。研究结果为项目进程的安排以及奖励机制的设计提供依据,以提高双方利益。     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

运筹学在整车物流智能调度决策支持系统中的研究与应用

本文基于整车物流智能调度决策支持系统的研发、实施与运维的成功应用,论述运筹学在智能化上的应用路径以及实践驱动的学术路径。该系统是国内较早在汽车物流企业实现落地的智能化调度系统,其所形成的思想理论与方法技术揭示了运筹学在智能化应用上的核心价值,以及实践驱动的学术价值,对解决“卡脖子”难题提供示范性思路。本文提出运筹学在智能化研发上“三环七步”的整体研发框架。首先,分析智能化需求的运筹学特征,详细介绍汽车整车物流的发展趋势、瓶颈及智能调度需求;其次,论述运筹学系统模型的作用与建模方法,分析汽车整车物流系统模型的决策要素、目标及约束,提出汽车整车物流智能调度的运筹学应用问题。然后,提出“模式装箱”的新装箱理论问题,明确问题的计算难解性、可解性及核心科学特征。进一步,建立汽车整车物流调度应用问题与科学问题的混合整数线性规划模型;提出求解汽车整车物流调度问题的分支定界算法,以及大规模问题求解的时空分解及滚动求解方法与技术;提出面向运筹应用的生产测试及压力测试方法,给出汽车整车物流调度的测试分析的流程与结果。此外,提出深度集成整车运输管理系统与仓库管理系统、优化算法引擎驱动的分布式、多视图、多系统融合的智能调度决策支持系统。最后,论述该系统在实施过程中的推广使用和运维情况,并对运筹学应用及实践驱动的科学研究进行总结与展望。