首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 78 毫秒
1.
并行多机调度问题的一种遗传算法   总被引:1,自引:0,他引:1  
运用遗传算法对最小化完工时间的并行多机调度问题进行了研究,给出了最小完工时间的一个下界,由此提出了初始种群的一种构造方法,并用计算实例表明该方法适用于大规模并行多机调度问题  相似文献   

2.
既有的项目反应性调度问题只关注了基准调度方案的稳定性,而忽略了项目调度目标的最优实现。本文提出了一种两阶段多模式资源受限项目反应性调度问题。第一阶段,在新的项目执行环境下,对项目进行完全重调度,得到新的最优调度目标值。第二阶段,以新的最优调度目标值为约束,以最大化调度稳定性为目标,求得新的最优调度方案。针对问题特点,基于IBM ILOG优化编程语言OPL和CPLEX V12.8.0,设计出该问题的求解程序。最后,基于标准算例,对本文提出的反应性调度方法、既有的反应性调度方法、完全重调度方法进行了充分的比较测试,结果表明本文提出的反应性调度方法在缩短项目工期、保护基准方案的稳定性方面具有明显优势。  相似文献   

3.
合理调度有限的码头资源以满足船舶的装卸时间要求是自动化集装箱码头的重要目标之一。针对自动化集装箱码头自动导引车(automated guided vehicle,AGV)配置与调度问题,考虑船舶装卸时间要求和AGV运输过程中的路径冲突,提出分阶段调度策略。将船舶装卸作业分为卸船阶段、装卸同步阶段、装船阶段三个阶段,在每个阶段中,建立以最小化最大完工时间和最小化AGV空载和等待时间为双目标的调度优化模型,并设计基于NSGA-Ⅱ的启发式算法求解。根据本阶段的实际完工时间,从最优解集中选择下一阶段AGV的配置与调度方案。最后对比其他调度方案表明本文调度方案能够满足集装箱船的装卸时间要求,且提高了AGV的利用率,更符合码头实际作业要求。  相似文献   

4.
基于混合算法的实时订货信息下的车辆调度优化   总被引:2,自引:0,他引:2  
实时订货信息下的车辆调度是随机性车辆调度中货物需求量、需求点均不确定的情况下的车辆调度.针对该问题,本文构建了配送总成本最小的目标函数,提出了采用混合算法求解的思路.即以局部搜索法求得初始解,采用遗传算法优化初始解,并在送货时间更新后,利用禁忌搜索法求解速度快的特点改进调度方案,得到订货信息不断更新的条件下的车辆调度方案.通过实例分析,本方法既可解决电子商务条件下实时订货的车辆调度问题,也具有求解结果可靠、求解过程快速的特点.  相似文献   

5.
多车场有时间窗的多车型车辆调度及其禁忌算法研究   总被引:12,自引:0,他引:12  
本文针对物流配送中的多车场车辆调度问题提出了两种多车场的处理方法,介绍了多车场车辆调度问题中容量、时间窗、多车型等多种约束的处理方法,并且根据具体约束情况设计了禁忌算法,对多车场有时间窗的多车型车辆调度问题加以实现,给出了一个具有代表性的算例试验结果和结果分析,通过试验表明了此方法对优化有时间窗的多车型车辆调度问题的有效性.  相似文献   

6.
针对健康管理理论在维修资源调度决策研究中的不足,分析了面向健康管理进行维修资源调度优化的可行性,研究了维修资源调度系统与健康管理系统的连接关系.然后结合装备维修资源供应保障的实际,建立了系统中调度优化模块所用到的带软时间窗的多需求地-多供应地维修资源调度优化模型,并应用遗传算法对模型的求解进行了分析.最后,对方法进行了演算,验证了模型在维修资源调度系统中应用的正确性和可行性.  相似文献   

7.
研究在云计算中服务资源优化管理背景下,基于时间窗口的非等同并行机服务资源调度问题.为达到最大任务处理数,选取任务延误时间作为目标函数建立数学模型,并利用蚁群算法为模型求解.设计了算法的各项参数,而且进一步探讨了如何将资源分配的公平性引入到算法中来.还通过仿真算例对比了考虑公平性要素前后的调度结果.从结果来看,提出的模型和算法能够较好的用于解决云计算中的并行机资源调度问题,并以较快的收敛速度找到满足约束条件的较优解.  相似文献   

8.
中继卫星任务规划与调度是中继卫星系统应用中的重要问题。根据航天器的空间轨道参数,得到中继卫星与用户航天器之间的可见时间窗口。在此基础上,通过分析中继卫星系统中各种资源之间的约束关系、任务优先级与调度准则,建立中继卫星系统的任务调度模型。仿真结果表明,基于约束规划理论建立中继卫星调度模型是解决中继卫星调度问题的有效方法。  相似文献   

9.
针对车辆调度过程中资源不均衡的问题,利用需求的不确定性,将配送周期划分为初始配送阶段和补货阶段,建立多阶段电动汽车的两级车辆路径优化模型.根据需求的动态程度对配送区域进行划分,结合前摄性调度和反应性调度策略,提出了一种混合禁忌搜索算法(HTSA)来求解该模型.在真实的案例和多个基准评估算例上的实验结果表明:模型和算法的性能优于传统的启发式算法,具有一定的实用价值.  相似文献   

10.
采用带时间窗的车辆调度优化物流配送系统,建立了带时间窗的多目标约束条件下的派车优化问题的数学模型,并针对某大型连锁超市物流配送中心的车辆调度问题进行了求解,经过对比分析,新方案实现了一定程度多目标优化.  相似文献   

11.
研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断,且工件到达时间与工期满足一致关系,目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序,使得满足第二个代理目标可行情况下,第一个代理目标函数值最小.在固定区间等于加工时间的情况下,利用分块原则,提出了一个伪多项式时间动态规划算法,并给出了固定区间大于加工时间情况下的时间复杂度分析.  相似文献   

12.
Scheduling project networks with resource constraints and time windows   总被引:10,自引:0,他引:10  
Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities.We consider the problem to schedule such networks subject to arbitrary (even time dependent) resource constraints in order to minimize an arbitrary regular performance measure (i.e. a non-decreasing function of the vector of completion times). This problem arises in many standard industrial construction or production processes and is therefore particularly suited as a background model in general purpose decision support systems.The treatment is done by a structural approach that involves a generalization of both the disjunctive graph method in job shop scheduling [1] and the order theoretic methods for precedence constrained scheduling [18,23,24]. Besides theoretical insights into the problem structure, this approach also leads to rather powerful branch-and-bound algorithms. Computational experience with this algorithm is reported.  相似文献   

13.
Let be a set of n independent tasks and a set of m processors. During each time instant, each processor can be used by a single task at most. A schedule is for each task an allocation of one or more time intervals to one or more processors. A schedule is said to be optimal if it minimizes the maximum completion time. We say a schedule S has the machine saturation property (MS property) if, at any time instant of task execution, all the machines are simultaneously busy. In this paper, we analyze the conditions under which a parallel scheduling system allows a schedule with the MS property. While for some simple models the analytical conditions can be easily stated, a graph model approach is required when conflicts of processor usage are present. For this reason, we define the class of saturated graphs that correspond to scheduling systems with the MS property. We present efficient graph recognition algorithms to verify the MS property directly on some classes of saturated graphs  相似文献   

14.
姜昆 《运筹与管理》2020,29(7):105-109
研究带凸资源和恶化效应的单机窗口指派排序问题,其中窗口指的是松弛窗口,凸资源和恶化效应指的是工件的实际加工时间是其开始加工时间的线性函数,是其资源消耗量的凸函数。目标是确定工件的加工顺序,资源分配量以及窗口的开始加工时间和长度使其在总资源消耗费用(与窗口有关的排序费用)有上界限制的条件下,极小化与窗口有关的排序费用(总资源消耗费用)。获得了求解上述问题的最优算法,证明了该问题是多项式时间可解的。  相似文献   

15.
合理的资源配置是提高项目调度鲁棒性一种有效的方法。本文针对项目鲁棒调度问题,提出了Max-PRUA资源分配启发式算法,以期通过生成鲁棒性高的资源分配方案来提高调度计划的鲁棒性。本算法设计了最大化利用优先关系和不可避免弧传递资源的资源分配两项策略来传递最大资源量,以减少由额外约束传递的资源量,降低对项目调度鲁棒性的影响。为寻优最优资源分配方案,配合局部搜索算法,本算法构建了动态活动组GRA,通过对组内活动顺序重排以生成多种资源分配方案,以利于从解空间中寻优出最佳的鲁棒性方案。最后通过大量的仿真实验验证和与其它算法进行比较,结果表明本算法对于不同规模和不同因素影响的项目均有较好的适应性,生成的资源分配方案对调度计划鲁棒性影响较小,是一种有效的算法。  相似文献   

16.
同时具有学习效应和退化效应的单机排序问题   总被引:1,自引:0,他引:1  
本文给出了一种同时具有一般化学习效应和退化效应的单机排序模型。在此模型中,工件的实际加工时间既与工件所在位置又与其开工时间有关,且工件在加工之后具有一个配送时间。其中学习效应是工件所在位置的函数,退化效应是工件开工时间的函数。证明了极小化最大完工时间和极小化总完工时间问题是多项式可解的,在满足一定的条件下,极小化加权总完工时间和极小化最大延误问题也是多项式可解的。推广了一些已有文献中的结论。  相似文献   

17.
在不确定环境中,一个具有较高鲁棒性的进度计划可以保证项目的稳定实施。考虑到现实中资源可能具有多种技能,会对制定鲁棒性较高进度计划的过程产生影响,因此本文研究了柔性资源约束下前摄性项目调度优化问题。首先界定研究问题;然后从鲁棒性最大化的视角出发,构建了研究问题的优化模型,在对模型进行分析的基础上将其分解为经典鲁棒优化和资源技能分配两个子模型;随后设计了求解问题的基于削峰算法的启发式算法;最后用一个实际案例验证了算法有效性,并分析了关键参数对进度计划鲁棒性的影响,得到如下结论:项目进度计划鲁棒性随着项目工期的延长、资源可用量的增加或资源柔性的提高而增大。  相似文献   

18.
This paper addresses the issues concerning resource allocation and process scheduling in a dynamic environment, where resources are distributed and availability of them is uncertain. In this context, we introduce a new multi-agent-based resource allocation and process scheduling approach, where agents communicate and cooperate among themselves to produce an optimal schedule. A distributed constraint optimization problem-based model in accordance with Markov Decision Process is proposed in this regard. We overcome the hardship of existing centralized approach and our technique optimizes not only the process completion delay but also the number of resources being idle, which is much more beneficial. Apart from the theoretical approach, we take a case study in its practical application domain to validate our claim. Analysis and experimental results show that this proposed method outperforms the state-of-the-art methods and bridges the gap between theory and its applications.  相似文献   

19.
A general problem in health-care consists in allocating some scarce medical resource, such as operating rooms or medical staff, to medical specialties in order to keep the queue of patients as short as possible. A major difficulty stems from the fact that such an allocation must be established several months in advance, and the exact number of patients for each specialty is an uncertain parameter. Another problem arises for cyclic schedules, where the allocation is defined over a short period, e.g. a week, and then repeated during the time horizon. However, the demand typically varies from week to week: even if we know in advance the exact demand for each week, the weekly schedule cannot be adapted accordingly. We model both the uncertain and the cyclic allocation problem as adjustable robust scheduling problems. We develop a row and column generation algorithm to solve this problem and show that it corresponds to the implementor/adversary algorithm for robust optimization recently introduced by Bienstock for portfolio selection. We apply our general model to compute master surgery schedules for a real-life instance from a large hospital in Oslo.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号