基于NSGA-II的应急生产任务多目标优化模型及算法研究

重大突发事件发生后,若灾区的应急物资需求不能通过调用储备得到满足,则应急生产将成为灾区应急物资供应的重要保障手段。本文研究重大突发事件发生后应急物资生产任务的优化问题,重点关注原材料生产能力变化对完成应急生产任务的影响,以应急生产任务完成时间最短、完成成本最低为决策目标,研究了包含多个供应商、多个制造商以及单个受灾点的应急物资生产任务多目标规划模型。运用在求解多目标规划问题时具有众多优势的非支配排序多目标遗传算法(NSGA-II)对模型进行求解。通过算例分析,NSGA-II可以得到较好的Pareto前沿,并且可以根据不同情况给出最优的应急物资生产和原材料保障方案。本文的研究还表明,要想更快完成应急生产任务,需要做好原材料、资金、电力、交通等各种要素的配套保障工作。     

微粒群算法及其在热轧生产调度中的应用

针对整数规划问题的特点,提出了一种在整数空间中进行进化计算的PSO算法,使微粒群的进化限于整数空间。给出了热轧生产调度问题的最优轧制单元数学规划模型。并将该方法成功应用于最优轧制单元求解。     

多车型车辆调度问题的优化模型

基于第十一届"华为杯"全国研究生数学建模竞赛E题第五问,针对一类多车型多目的地的整车物流运输调度问题,先直接计算完成总任务所需的车辆数来阐明该题的最优解的下界限为113辆,再对原始数据进行预处理,基于对乘用车的分类与排样算法,筛选出每种轿运车的M种装载方案代表,再对目的地位置及结合各目的地的任务需求,确定出3条不绕行路线,根据启发式调整优化算法,并以轿运车使用量最少及总行驶里程最短为优化目标,建立了多目标整数规划模型进行求解,最优可行解为114辆,其中1-1型91辆,1-2型18辆,2-2型5辆.     

考虑任务优先约束的同类岸桥作业调度优化

分析了以箱组为任务对象QCSP与以整贝为任务对象QCSP的异同,指出前者更能均衡各岸桥作业负荷,并减少船舶装卸作业时间。考虑到岸桥具有作业效率差异的特点,将其视为同类平行机调度问题,同时结合任务优先约束、岸桥作业不可相互穿越与安全距离等特有约束,建立了更加符合实际的以箱组为任务对象的岸桥作业调度混合整数规划模型,其优化目标是最小化装卸作业的makespan。针对模型求解的复杂度,设计了一种遗传算法,对算法搜索空间进行了讨论,并推导了问题的低界。实验算例表明所建立的模型能够反映岸桥作业调度过程中作业效率差异及任务优先约束现象,其算法能够在允许的运算时间内获得稳定的满意解,并且优化结果要全面优于以整贝为任务对象QCSP的调度方案。     

多元利益主体目标下的可重入层流手术绿色调度

针对考虑患者、医院、社会多方利益下的可重入层流手术绿色调度问题,提出了混合优化算法INSGAII-LS以同时最小化三个目标：平均患者术前等待感知时长、层流手术中心使用时长和层流手术中心碳排放。首先,算法创新设计了合作搜索策略、种群初始化策略、变尺度交叉与变异策略,LS深度搜索迭代策略,以增强解空间的搜索能力;然后,根据问题特点设计了数据驱动解码策略,并通过三种解码策略对比实验,验证了本文提出的解码策略的有效性;最后,通过不同规模数值实验和仿真案例测试了本文算法相比于其他有效算法(IMSSA,IMOGWO,NSGA-II)的优越性和稳定性。案例仿真发现,决定手术中心使用时长的关键因素是对患者的排序;而手术中心使用时长的缩短并不直接导致碳排放量的减少,还需关注手术室的累积碳排放量。因此,层流手术室的调度在层流手术规划中至关重要。研究结果可为层流手术绿色调度多目标优化提供方法借鉴和决策参考。     

基于机会约束的公交调度研究

利用机会约束规划研究公交调度问题 ,考虑了公交走行时间的不确定性、乘客需求的不确定性、以及乘客等待时间约束等影响因素 ,据此建立在一定的置信水平下企业利益最大化模型 ,利用基于随机模拟的遗传算法进行求解 ,并通过实验算例说明模型的可行性 ,最后通过研究模型参数的敏感性 ,分析模型的参数对最优解的影响 .     

考虑时间和油耗的拖轮多目标优化调度研究

进出港口的大型船舶需向港口申请拖轮协助以进行靠离泊作业。拖轮调度是港口重要的计划事项之一。针对拖轮调度过程中需要平衡完工时间和油耗量以提高港口服务水平和降低拖轮公司经营成本的问题,本文以最小化拖轮最大完工时间和最小化拖轮总油耗量为目标,构建了混合整数规划拖轮多目标优化调度模型。模型还考虑了潮汐港口大量船舶在潮水期间集中进出港的特点,并根据拖轮在调度过程中的不同状态分类计量其产生的油耗量,以使模型更接近实际状况。为求解模型,运用了带有精英策略的非支配排序遗传算法(NSGA-II),算法采用一维实数编码,以事件建模思想设置适应度函数,并结合拖轮调度特点设计了遗传算子,求得的Pareto前沿解和算法对比验证了该算法的有效性。最后,以广州港港口拖轮调度实际运作数据作为算例,验证了模型的可行性与有效性,为港口拖轮调度计划提供了决策依据。     

装备维修器材生产路径双目标问题优化决策方法研究

在装备维修器材供应保障中,针对精确保障背景下部队用户对器材保障精度的要求,构建了最小化总成本和最大化订单精准执行率的双目标优化决策模型。在ε-约束法框架内,开发可生成近似Pareto前沿的两阶迭代启发式算法,并采用模糊逻辑决策法选择符合决策者偏好的折中最优解。随机实例测试结果表明所提出的模型和算法可以很好地应用在双目标优化问题的研究中,并在求解不同规模实例时表现出优异的性能。     

考虑序列设置时间的混合流水车间多目标调度研究

基于混合流水车间多品种的特性,序列设置时间和工序跳跃是很多车间在调度时需要考虑的两个重要问题,论文充分考虑这两种生产约束,建立了以最大完工时间和负荷均衡指标为双目标的混合流水车间多目标调度数学模型,并运用改进的NSGA-II算法对基于实际企业生产数据假设的算例进行仿真求解,结果表明求解的调度方案符合实际需求,能够为企业的实际调度提供有效的方案。     

基于资源约束的突发事件应急救援鲁棒性调度优化

突发事件应急救援的调度优化,对于救援活动的顺利实施及应急资源的有效使用具有至关重要的作用。本文研究资源约束下的突发事件应急救援鲁棒性调度优化问题,其中,鲁棒性定义为各活动的时间缓冲与其权重系数乘积的总和,目标是在资源可用量及救援期限的约束下,安排活动开始时间和执行模式以最大化应急救援计划的鲁棒性。作者构建了问题的0-1规划优化模型,针对其NP-hard属性,基于问题特征设计双环路禁忌搜索启发式算法。通过对一个算例的计算分析,得到如下结论:给定网络结构及时间参数,利用权重系数的定义可以将时间缓冲分配到重要活动上,由此提高应急救援计划的鲁棒性;随着资源可用量的增加,计划的鲁棒性呈上升趋势,而当救援期限延长时,计划的鲁棒性单调增加。本文研究可为突发事件应急救援基准计划的制定提供决策支持。     

单机单转包商调度与外包联合优化问题的改进启发式算法

针对以总完工时间与总外包费用加权和为优化目标、总外包费用不超过给定上限的单机单转包商调度与外包联合优化问题,设计出一种改进的剔除型启发式算法。该算法通过运用动态规划技术求解新的辅助问题来获取初始外包工件集,并引入判定条件提前从初始外包工件集中剔除特定工件。为满足对总外包费用的上限约束,还利用新型的启发式筛选次序族逐一确定从当前外包工件集中剔除的工件。在仿真实验中,通过生成大量的测试算例,对比分析了改进算法与另2种已报道算法在求解质量、计算时间上的表现情况。实验结果表明所提出的改进算法在解的整体质量上具备显著的比较优势,并且能在5.6秒内完成对工件总数为1500的测试算例的求解。     

改进的蝗虫优化算法在双目标应急物资中心选址问题中的应用

近年来世界各地频发灾情疫情等紧急事件,严重影响人民的生活物资保障。在这种情况下,急需建立应急物资中心来缓解燃眉之急。该类问题通常面临资源稀缺并且时间相对紧迫的处境,因此需要在短时间内获得合理的应急设施选址方案来提升服务的质量和效率。本文对应急物资中心选址问题展开研究,提出一种考虑后续运输成本以及有概率发生紧急事件而导致无法正常运送物资的双目标离散选址模型,并为此设计一种二进制多目标蝗虫优化算法。该算法采用模糊关联熵系数来引导迭代更新,同时为其添加外部档案,最优解选择机制和竞争决策机制来提升算法性能。多次数值实验表明该算法的计算效率和求解质量较高,可作为应急物资中心选址问题的一种可行且有效的算法。     

混合整数规划求解多联票据印刷过程中的生产调度问题

多联票据的印刷过程包括排版、单联印刷和多联配页与装订三个过程。该过程是柔性的流水生产线与装配混合的生产系统。本文研究了该系统中的票据印刷生产调度问题,目标是最小化所有产品的最大完成时间（Makespan）。该问题到目前为止还没有人研究,本文首先建立了该问题的混合整数规划模型,然后提出了该模型的求解方法,并给出了该问题的下界。最后的量化示例和算例试验表明本文的模型是有效的。     

Heuristic Control of a Constraint-Based Algorithm for the Preemptive Job-Shop Scheduling Problem

In the recent years, constraint programming has been applied to a wide variety of academic and industrial non-preemptive scheduling problems, i.e., problems in which activities cannot be interrupted. In comparison, preemptive scheduling problems have received almost no attention from both the Operations Research and the Artificial Intelligence community. Motivated by the needs of a specific application, we engaged in a study of the applicability of constraint programming techniques to preemptive scheduling problems. This paper presents the algorithms we developed and the results we obtained on the preemptive variant of the famous job-shop scheduling problem. Ten heuristic search strategies, combined with two different constraint propagation techniques, are presented, and compared using two well-known series of job-shop scheduling instances from the literature. The best combination, which relies on limited discrepancy search and on edge-finding techniques, is shown to provide excellent solutions to the preemptive job-shop scheduling problem. A mean relative distance to the optimal solution of 0.32% is achieved in five minutes, on instances with 10 jobs and 10 machines (100 activities).     

带组约束可靠性网络最优化问题的精确算法

本文提出了一种求解带组约束串-并网络系统最优冗余问题的精确算法.该算法利用拉格朗日松驰和Dantzig-Wolfe分解法得到问题的上界,并结合动态规划求解子问题.算法采用一种有效的切割和剖分方法,以逐步缩小对偶间隙和保证收敛性.数值结果表明该算法对于求解带组约束可靠性最优化问题是很有效的.     

共享单车调度优化问题研究

针对共享单车站点经常出现的供需不平衡问题,提出人工调度策略,以提高单车利用率和用户满足率.首先将一天划分为几个用车高峰时段,根据每个站点的单车使用历史数据,计算各站点在每个时段的需求量区间;在区域内单车总投放量不变的前提下,基于每个时段初期各个站点存放的单车数量,确定单车调出站点和单车调入站点,进一步以站点之间的单车调...     

Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem

The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration. Basically, they consist in the construction of mixed integer subproblems, considering the integrality of some subset of variables, formulated using the information obtained from the solution of the linear relaxed problem. Computational experiments are reported for a collection of test problems, showing that some of the proposed algorithms achieve better solutions than other relevant approximation algorithms published up to now.     

呼叫中心坐席人员排班问题优化模型与算法研究

国内呼叫企业在保证每个坐席人员周内当值相同班次情况下,通过灵活安排周内当班日期与班次来制定排班方案。针对该实际排班场景,构建问题整数规划模型。通过对问题数据特征及优化性质分析,以及对班次人力有效满足区段电话服务需求的量化指标表征,分别提出两个构造性启发式算法。使用企业实例数据对模型算法进行计算实验。实验结果显示,整数规划模型适合于求解小规模排班问题最优解,而启发式算法能够以小计算成本获得大规模排班问题优化解。最后讨论保证员工上班规律性的同班次用工制度对企业人力成本控制的影响。     

Parallel Integer Optimization for Crew Scheduling

Performance aspects of a Lagrangian relaxation based heuristic for solving large 0-1 integer linear programs are discussed. In particular, we look at its application to airline and railway crew scheduling problems. We present a scalable parallelization of the original algorithm used in production at Carmen Systems AB, Göteborg, Sweden, based on distributing the variables. A lazy variant of this approach which decouples communication and computation is even useful on networks of workstations. Furthermore, we develop a new sequential active set strategy which requires less work and is better adapted to the memory hierarchy properties of modern RISC processors. This algorithm is also suited for parallelization on a moderate number of networked workstations.