检索结果-南通市图书馆

考虑订单类型和准备时间的批处理机在线调度模型研究

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

运筹学学报 2024年

作者：靳凯媛郑斐峰刘明同济大学经济与管理学院东华大学旭日工商管理学院

本文探讨了批容量有限的一类批处理机在线调度问题。在订单实时释放的场景下,针对订单具有不同类型、同类型订单才能组批、不同类型订单批次之间需要既定准备时间、批处理时长依赖于订单类型的调度模型,以最大化总完工收益为优化目标,... 详细信息

本文探讨了批容量有限的一类批处理机在线调度问题。在订单实时释放的场景下,针对订单具有不同类型、同类型订单才能组批、不同类型订单批次之间需要既定准备时间、批处理时长依赖于订单类型的调度模型,以最大化总完工收益为优化目标,着重考察了两种加工情形。对于单台批处理机的在线模型,证明了问题的竞争比下界为1+w,其中w表示批次的最大完工收益。同时,设计了考虑准备时间的在线算法,并运用最坏情形分析法证明了其竞争比等于下界,表明该算法具有最优竞争性。对于两台平行批处理机的情形,提出了一个竞争比为1+2w1/2的在线算法。

关键词：在线调度批处理机在线算法竞争比

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

垃圾量有限预知下环卫车在线调度策略

黑龙江交通科技 2024年第3期47卷 160-163,167页

作者：罗杨石超峰重庆交通大学重庆400074

目前,垃圾清运是环保工作重点关注的问题之一,一般垃圾清运成本占总垃圾处理成本的60%~80%,所以以成本最小化为目标的环卫车调度问题就成为热点问题。现有对该问题的研究大部分都是基于静态需求,最后计算出环卫车调度的离线最优。因此,... 详细信息

目前,垃圾清运是环保工作重点关注的问题之一,一般垃圾清运成本占总垃圾处理成本的60%~80%,所以以成本最小化为目标的环卫车调度问题就成为热点问题。现有对该问题的研究大部分都是基于静态需求,最后计算出环卫车调度的离线最优。因此,将需求动态变化的特征纳入考虑范围,提出了在垃圾量有限预知的情况下城市环卫车在线调度的诱导策略和组合优化策略,同时证明了两个策略不同情况下的竞争比。最后通过实例比较策略的执行效果,得出了该实例的最优在线调度策略为诱导策略。

关键词：环卫车垃圾量有限预知在线调度调度策略竞争比

基于长短期记忆近端策略优化强化学习的等效并行机在线调度方法

在线全文

学校读者我要写书评

暂无评论

中国机械工程 2022年第3期33卷 329-338页

作者：贺俊杰张洁张朋汪俊亮郑鹏王明东华大学机械工程学院上海201620 上海交通大学机械与动力工程学院上海200240

针对等效并行机在线调度问题,以加权完工时间和为目标,提出了一种基于长短期记忆近端策略优化(LSTM-PPO)强化学习的在线调度方法。通过设计融合LSTM的智能体记录车间的历史状态变化和调度策略,进而根据状态信息进行在线调度。设计了车... 详细信息

针对等效并行机在线调度问题,以加权完工时间和为目标,提出了一种基于长短期记忆近端策略优化(LSTM-PPO)强化学习的在线调度方法。通过设计融合LSTM的智能体记录车间的历史状态变化和调度策略,进而根据状态信息进行在线调度。设计了车间状态矩阵对问题约束和优化目标进行描述,在调度决策中引入额外的设备等待指令来扩大解空间,并设计奖励函数将优化目标分解为分步奖励值实现调度决策评价。最后基于PPO算法进行模型更新和参数全局优化。实验结果表明所提方法优于现有的几种启发式规则,并将所提算法应用于实际车间的生产调度,有效减小了加权完工时间和。

关键词：等效并行机在线调度强化学习长短期记忆近端策略优化

实时需求下的带时间窗移动充电车在线调度算法

同方期刊数据库博看期刊评论

在线全文

学校读者我要写书评

暂无评论

科学技术与工程 2023年第15期23卷 6513-6521页

作者：陈程石超峰重庆交通大学交通运输学院重庆400074 重庆交通大学经济与管理学院重庆400074

在双碳背景下,移动充电车作为新型充电设施,能够缓解电动车保有量迅速增长带来的充电压力。然而成本高、效益低等问题阻碍了移动充电车的进一步发展。针对移动充电车只有在用户发出充电请求时,才能获知充电需求信息的特点,且需求带有时... 详细信息

在双碳背景下,移动充电车作为新型充电设施,能够缓解电动车保有量迅速增长带来的充电压力。然而成本高、效益低等问题阻碍了移动充电车的进一步发展。针对移动充电车只有在用户发出充电请求时,才能获知充电需求信息的特点,且需求带有时间窗要求的情形,提出实时需求下的带时间窗移动充电车调度问题,以总时间成本最小为目标,采用在线理论与方法,建立优化模型并设计在线算法;给出了不同情形下的调度方案,计算方案的竞争比,并进行对比分析;最后通过数值算例验证了在线算法的可行性和有效性。研究结果表明,用户发出的实时充电需求数量越大、最大单位惩罚时间成本系数越小,在线算法的执行效果越好。本文的模型和在线调度算法可以有效解决实时需求下的带时间窗移动充电车调度优化问题,提高移动充电车的充电效率,平衡充电供需。

关键词：移动充电车在线算法在线调度竞争比

在线全文

学校读者我要写书评

暂无评论

IoT数据敏感的工作流在线调度方法研究

IoT数据敏感的工作流在线调度方法研究

作者：张明珠北方工业大学

学位级别：硕士

随着万物互联时代的到来,越来越多的工作流中含有大量的IoT数据实时处理任务,如智慧城市、智能交通等应用场景中的工作流应用。为了提高工作流的执行效率、充分利用计算资源,采用云、边协同方式进行工作流调度执行成为必然。然而IoT数... 详细信息

随着万物互联时代的到来,越来越多的工作流中含有大量的IoT数据实时处理任务,如智慧城市、智能交通等应用场景中的工作流应用。为了提高工作流的执行效率、充分利用计算资源,采用云、边协同方式进行工作流调度执行成为必然。然而IoT数据参与的工作流在云边环境的调度执行会面临诸多挑战。例如IoT数据多为连续、时效性强的流数据,因此IoT数据处理的工作流需要不断地重复执行;同时,IoT数据的动态性也会影响到工作流任务的负载。如果长期采用静态调度算法可能会带来较大的代价以及时间延迟。在这种情况下,在线调度算法成为降低工作流负载动态性影响,进行更高效调度执行的有效途径。就现有的动态调度和在线调度算法而言,它们大多关注调度过程中计算资源的波动问题,而忽略了流式工作流负载的动态特性,这会影响到任务执行时间以及通信代价,甚至会导致部分数据丢失,如果不能及时根据负载变化调整调度方案,会给整个工作流执行带来不可预想的代价。针对工作流连续调度过程中,接入的IoT数据动态变化带来的调度不确定性,本文提出了一种负载敏感的工作流在线调度算法LAPT(Load Aware Plan Tuning)。与现有的调度算法相比,LAPT算法具有以下几个优点:1)在优化目标中引入任务的迁移代价,通过此来尽可能地限制两次连续调度中任务执行位置的变化,保证方案的稳定性并降低部署成本。2)该调度算法采用两阶段的方式,融合了遗传算法和局部搜索算法。首先利用遗传算法寻到近似最优解,随后工作流数据源数据产生速率变化大于20%时,则采用局部搜索算法更新调度方案。该调度算法减少了调度时间,尽可能满足工作流调度的实时性要求。为了进一步提高LAPT算法第二阶段中局部最优解的质量,本文提出了改进的 P-LAPT 算法(Predictive-based Load Aware Plan Tuning)。从大数据的角度出发,利用大量的工作流实例及对应的近似最优调度方案(在GA、NSGA等优化算法下得到)训练Seq2Seq模型,得到一个可以预测调度解的模型。在连续调度时将预测的近似最优解加入到LAPT算法的第一阶段,将局部搜索改为多领域局部搜索。通过有针对性地扩大搜索空间,优化调度方案的质量。本文实验在改进的WorkflowSim上进行,并利用DAG生成算法模拟生成了大量的IoT工作流参与实验验证,通过在预测解方法中嵌入不同的算法,评估了预测解的质量。同时与现有的几种调度方法对比,发现本文提出的方法能够适应IoT数据速率变化,并快速生成一个代价较小的调度方案,在执行时间、花销成本以及处理速度上均达到了整体较优的效果,满足了 IoT工作流调度的低时延需求。

关键词：工作流调度优化 IoT数据任务迁移在线调度 Seq2Seq模型

基于控制器的公交车辆在线调度方法研究与实现

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于控制器的公交车辆在线调度方法研究与实现

作者：王飞扬北京邮电大学

学位级别：硕士

在公共交通运营规划领域,公交车辆排班问题对于保障公交服务质量是十分重要的。然而,在实际的公交运营过程中,道路交通环境往往是不稳定的,交通拥堵、车辆故障等意外因素往往会使车辆行程耗时增加。如果车辆无法按时回到发车控制点,该... 详细信息

在公共交通运营规划领域,公交车辆排班问题对于保障公交服务质量是十分重要的。然而,在实际的公交运营过程中,道路交通环境往往是不稳定的,交通拥堵、车辆故障等意外因素往往会使车辆行程耗时增加。如果车辆无法按时回到发车控制点,该车辆的下个行程将无法准时发车,这将严重影响公交运营服务质量。如何生成高质量的排班方案,以及如何保证在线公交运营服务质量,是一个很有研究价值的问题。现有的公交车辆排班方法分为精确方法和启发式方法。精确方法计算耗时很长,难以应用到实际。启发式方法则难以保证排班方案的效果。对于不确定环境下的车辆排班问题,现有研究分为带有鲁棒性的车辆排班方法以及动态车辆调度方法。前者的车辆利用率较低,会提升公交运营成本。后者则十分耗时,难以满足在线调度时效性要求。针对现有方法存在的问题,本文首次提出了基于控制器的公交车辆排班方法,以及基于进化神经网络的公交车辆排班方法。控制器方法设计了一个发车选择控制器,将每个发车时刻点视为决策点,控制器在每个发车时刻点选择一辆车从车场发出。当所有时刻点都被车辆行程覆盖后,即获得一个发车时刻表。该控制器由车辆类型转换器以及车辆选择器组成。车辆类型转换器负责动态地在线转换车辆的类型与工作状态,以提高车辆利用率。车辆选择器负责选择合适的车辆发出,生成排班方案。此外,动态车辆调度场景下,为了保证车辆调度命令能及时下达给车辆,设计了一种前向探测机制来保证决策质量。控制器中含有一些人工设置的参数,本文使用粒子群优化算法优化这些参数,以提升控制器的决策质量。为了进一步提高决策质量,本文使用进化神经网络代替人工设计的控制器进行发车决策。本文设计了一种三层径向基神经网络替换了发车选择控制器,并使用粒子群算法优化神经元参数。试验结果表明,控制器方法的效果明显优于对比方法和人工结果,进化神经网络方法在复杂约束问题上的效果也有一定提升。动态调度场景下,该方法计算耗时很短,满足在线调度需求。最后,基于上述研究,本文设计并实现了基于Qt的公交车辆调度系统。该系统可应用于静态以及动态场景下的公交车辆排班任务中,显著提高了公交系统的服务质量,同时降低了公交线路的运营成本。

关键词：公交车辆排班在线调度控制器进化神经网络粒子群优化

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

面向需求未知的移动充电车在线调度算法研究

面向需求未知的移动充电车在线调度算法研究

作者：陈程重庆交通大学

学位级别：硕士

在双碳背景下,国家大力发展低碳交通,电动汽车保有量不断增加。但是行驶距离有限、充电时间较长以及配套充电设施不健全等问题制约了电动汽车的发展。现有的公共充电基础设施也不能满足城市电动汽车的充电需求。一种新型的、成本更低、... 详细信息

在双碳背景下,国家大力发展低碳交通,电动汽车保有量不断增加。但是行驶距离有限、充电时间较长以及配套充电设施不健全等问题制约了电动汽车的发展。现有的公共充电基础设施也不能满足城市电动汽车的充电需求。一种新型的、成本更低、灵活性更好的新型移动充电车应运而生,作为城市电网服务的有利补充,移动充电车可以在合适的时间和地点为用户提供充电服务,为电动汽车提供随机存电保供服务。同时移动充电车可以分担电动汽车保有量迅速增长带来的充电压力,缓解电动汽车用户里程焦虑,平衡充电供需。因此,如何合理调度移动充电车,最大化资源利用率,具有重要的应用价值,其相关的理论也值得研究。本文采用在线理论与方法,针对充电需求未知的特点,即移动充电车只有在用户发出充电请求时,才能获知充电需求信息,且需求带有时间窗要求的情形,提出面向需求未知的移动充电车调度问题。首先,考虑高峰时期需求较多,供给小于需求的情况,移动充电车只能有选择地服务部分需求。在尽可能多的满足服务需求前提下,本文以总时间成本最小为优化目标,建立了需求部分满足下的移动充电车在线调度优化模型,并设计了CO策略和TS策略;验证不同情形下的竞争比,对竞争比和影响参数进行分析,同时分析策略的适用性。其次,考虑平峰时期,供给大于等于需求时,移动充电车能够服务全部需求。在保证服务所有需求的前提下,本文以总时间成本最小为优化目标,建立了需求完全满足下的移动充电车在线调度优化模型,并设计了FP策略和NM策略;验证不同情形下的竞争比,对竞争比和影响参数进行分析,同时分析策略的适用性。最后以重庆市南岸区为例,分别验证需求部分满足和需求完全满足下的策略执行效果,证明了本文设计的在线算法的可行性和有效性。研究结果表明,本文所提优化模型和设计的在线调度算法可以有效解决面向需求未知下的移动充电车调度优化问题,提高移动充电车的充电效率,平衡充电供需。本文将在线问题与竞争策略的理论与方法运用到移动充电车的调度问题研究中,提出面向需求未知的移动充电车在线调度优化模型和算法,为移动充电服务运营商调度移动充电车提供了新思路,为实现移动充电车资源利用最大化问题的解决提供了理论支持。

关键词：移动充电车需求未知在线调度竞争比

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

同城即时配送问题基于多预测场景的在线调度

系统工程理论与实践 2018年第12期38卷 3197-3211页

作者：王征李婷玉岳彩凡大连海事大学航运经济与管理学院大连116026 大连理工大学软件学院大连116620

同城即时配送是随现代电子商务而产生的新问题,该问题呈现出极强的动态性与求解时间的紧迫性,并具有商户与顾客一对多的关系、车辆需要多次往返商户取货、货物取送有时效要求等诸多新特征,无法依赖现有研究而求解.针对这一问题,建立了... 详细信息

同城即时配送是随现代电子商务而产生的新问题,该问题呈现出极强的动态性与求解时间的紧迫性,并具有商户与顾客一对多的关系、车辆需要多次往返商户取货、货物取送有时效要求等诸多新特征,无法依赖现有研究而求解.针对这一问题,建立了基于多预测场景的在线优化调度方法,将带有预测订单的多个场景整合到路线规划过程,通过每个场景的方案计算,以及多场景方案的整合,得到了车辆赖以运行的集成方案,提高了调度方案面对未来不确定需求的适应性;所建立的调度系统在新订单进入时立即响应,在系统闲置时则采用大邻域搜索技术不断优化未完成的任务方案.最后,在具有200~300个日订单的大连市某同城即时配送公司的真实数据上,验证了在线调度方法的有效性和可行性.

关键词：同城即时配送在线调度多预测场景大邻域搜索

在线全文

学校读者我要写书评

暂无评论

可重构系统中的实时任务在线调度与放置算法

计算机学报 2007年第11期30卷 1901-1909页

作者：周学功梁樑黄勋章彭澄廉复旦大学计算机与信息技术系上海200433

有效的任务调度与放置是发挥可重构计算性能优势的重要因素.针对实时任务在二维可重构器件上的在线调度问题,定义了调度算法完全识别的概念,即算法不会拒绝能够成功调度的任务.提出了新的实时在线调度与放置算法,充分利用了任务的时间信... 详细信息

有效的任务调度与放置是发挥可重构计算性能优势的重要因素.针对实时任务在二维可重构器件上的在线调度问题,定义了调度算法完全识别的概念,即算法不会拒绝能够成功调度的任务.提出了新的实时在线调度与放置算法,充分利用了任务的时间信息,实现了完全识别的调度.实验表明,与已有的算法相比,新算法显著地改善了调度效果,而运行开销没有明显增加.

关键词：可重构计算在线调度实时放置策略完全识别