共查询到17条相似文献,搜索用时 970 毫秒
1.
2.
局内军车调度的时间优化及其竞争策略 总被引:7,自引:1,他引:6
提出时间目标函数下的局内k-军车调度问题,应用复位策略给出该问题的几种竞争算法:给出了对应的局内k-服务器问题的竞争比的c时的该问题的竞争比为c 1 1/θ的竞争算法;分别给出了当k=n和k=n-1时该问题的竞争比为1和1+1/θ的竞争算法。 相似文献
3.
具有时间窗的局内开放式车辆调度的竞争分析 总被引:1,自引:0,他引:1
基于k-卡车问题和局内运输问题,提出了具有时间窗的局内开放式车辆调度问题.该问题的优化目标为:在服务需求的发布为局内方式的条件下,如何最小化完成整个服务需求序列的时间跨度.建立了该问题的数学模型并对有关的概念和参数进行了定义和说明.研究了当车辆数为1时该问题的竞争分析的有关结果:给出并证明了对于该问题的竞争策略的竞争比下限;针对该局内问题,设计了两种不同的竞争策略,得到了相应的竞争比,并进行了理论证明. 相似文献
4.
5.
6.
研究决策者面对突发事件,应对单机调度中的应急管理问题.在完全没有突发事件发生时间和发生次数信息条件下,利用局内决策理论与方法构建确定情形下的应急策略,并利用"竞争比"说明该策略的有效性.在此基础上进一步研究随机模型下的平均竞争比.理论和数值分析表明指数分布的引入使得竞争分析的性能得到显著改善. 相似文献
7.
特殊优惠卡问题是租赁问题的推广.应用平均情形竞争分析研究了局内特殊优惠卡问题,理论和数值分析表明概率分布的引入使得竞争分析的性能得到了改善.并对存在市场利率的特殊优惠卡问题进行了讨论,市场利率的引入使得该金融模型更贴近于现实情况.得到两种情形下不同的竞争比,同时竞争比是市场利率的递减函数. 相似文献
8.
9.
以钢铁企业副产煤气为研究对象,基于在线理论,考察其在线均衡分配问题.在生产过程中,决策者在每个时期决策煤气的供应量, 目标是使得在各时期煤气供应尽可能均衡平稳.基于合理假设,建立煤气均衡分配模型,对于均衡区间未知的问题, 分析了离线情形的特殊性质,以及不同煤气产生序列情形下的在线特征;对在线问题设计了在线二分策略, 并用最坏情形法证明了其竞争比为(1+3M/m)/4.本研究为企业生产中副产品的均衡分配和利用提供了一定的思路与理论借鉴. 相似文献
10.
11.
12.
ON-LINE SCHEDULING WITH REJECTION ON IDENTICAL PARALLEL MACHINES 总被引:1,自引:0,他引:1
Cuixia MIAO Yuzhong ZHANG 《系统科学与复杂性》2006,19(3):431-435
In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs. We give an on-line algorithm for the problem with competitive ratio 1/2 (2 +√3) ≈ 1.86602. 相似文献
13.
The authors consider the problem of on-line scheduling of unit execution time jobs on uniform machines with rejection penalty. The jobs arrive one by one and can be either accepted and scheduled, or be rejected. The objective is to minimize the total completion time of the accepted jobs and the total penalty of the rejection jobs. The authors propose an on-line algorithm and prove that the competitive ratio is 1/2 (2 W √3) ≈ 1.86602. 相似文献
14.
In this paper, the authors consider an on-line scheduling problem of m (m ≥ 3) identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance time interval is larger than the largest processing time of jobs, the authors prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of maintenance time interval is less than or equal to the largest processing time of jobs, the authors prove a lower bound of 3 on the competitive ratio. The authors give an on-line algorithm with competitive ratio $4 - \tfrac{1} {m} $ . In particular, for the case of m = 3, the authors prove the competitive ratio of the on-line algorithm is $\tfrac{{10}} {3} $ . 相似文献
15.
16.
不确定处理时间批处理过程的鲁棒调度新策略 总被引:3,自引:0,他引:3
针对化工批处理调度过程中处理时间不确定的问题,建立了具有分解结构的调度模型,提出了一种新的鲁棒调度策略.策略由基本调度策略和在线调整两部分组成,分别与模型的主问题和子问题相对应.提出了基于遗传算法的分解算法求解模型,以获取具有鲁棒性和最优性的基本调度策略.通过对子问题的分析,提出了运用简单的推理进行在线调整的方法,无需复杂计算,并运用动态规划的原理说明了该方法的可行性和最优性.最后用实例说明了该鲁棒调度策略的有效性. 相似文献
17.
商家在策划优惠卡发行时需要严密论证发行价格和折扣率等因素对消费者消费行为的影响. 利用在线算法和竞争分析理论, 研究了消费者对同时发行的两种优惠卡的在线决策问题. 一方面得到了最优确定性策略及其竞争比; 另一方面构造了一个随机性策略, 得到了最优随机性策略竞争比的一个上界, 并利用Yao引理得到了随机性策略最优竞争比的一个下界. 借助于数值算例, 分析了各因素对在线策略及其竞争比的影响. 研究结果可以为优惠卡发行价格和折扣率的决策提供依据. 相似文献