实时系统中单处理器调度算法的优化设计研究

研究实时系统的建模与调度问题是运筹与控制领域研究的热点问题, 对实时系统中的单处理器的调度算法进行了分析与研究, 特别是对其中的单调速率算法和最早时间限优先算法进行了深入的研究, 指出单调速率算法是一种典型的静态调度算法, 并且证明了单调速率算法是单处理器最优的静态优先级调度算法, 同时还指出最早时间限优先算法是一种典型的动态优先级调度算法,证明了最早时间限优先算法是单处理器的最优的动态优先级调度算法. 最后, 为了更好地进行实时系统的建模与调度, 引入了一种新的对任务执行行为进行抽象的方法--T-LET平面方法, 利用这种方法建立了单处理器流调度模型和BLREF调度算法, 并指出这种模型和算法都具有很强的几何背景.     

一种改进的多模式项目反应性调度问题

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

调度系统n/m/P/Cmax[ω]在一类线性摄动下的鲁棒性

用实数集R上一个含幺元的Abelian半群的性质来研究调度系统n/m/P/Cmax[ω]在一类线性摄动下的鲁棒性.根据实际问题的需要,提出了一类线性摄动模型,由系统输出表达式及其性质和最优鲁棒调度的定义,证明了:摄动系统的最优鲁棒调度必是标称系统n/m/P/Cmax[ω,1,0]的最优调度;标称系统的越韩最优调度必是它的最优鲁棒调度.     

二机系统调度在一类线性摄动下具有鲁棒性的一个充要条件

用实数集R上一个含幺Abelian半群的性质研究了n／2／F／Cmax调度在一类线性摄动下具有鲁棒性的条件．由最优鲁棒调动的定义,证明了标称系统的最优鲁棒调度与标称系统的越-韩最优调度是等价的．     

基于改进混合遗传算法安排生产调度

研究了某工厂生产调度问题,建立了数学模型.针对这一实际问题,通过引入小生境技术、最优保存策略、近优淘汰策略、自适应调整交叉概率和变异概率,设计了用于求解多个最优顺序的混合遗传算法,用所设计的混合遗传算法对该模型进行了计算,获得了许多最优顺序,这就使得生产调度安排灵活机动,便于智能调度,同时生产量比原来大幅度提高.这表明使用混合遗传算法安排生产调度是非常有效的.     

一类串行生产线的最优调度问题的注记

本文讨论了文［１］中串行生产线最优调度问题，给出了生产线生产周期的显示公式，对两个变量时最优调度的解的特性进行了研究．     

一类串行生产线的最优调度问题的注记

本讨论了[1]中串行生产线最优调度问题，给出了生产线生产周期的显示公式，对两个变量时最优调度的解的特性进行了研究。     

不可压缩Navier-Stokes方程最优动力系统建模和分析

研究了同时满足任意速度边界条件和速度不可压条件的Navier-Stokes方程最优动力系统的建模方法.通过对方柱绕流问题的最优动力系统的建模与分析,发现该最优动力系统的动力学特性为极限环.同时,该最优动力系统仅使用了三个最优基函数就很好地描述了所有主要的流场特征和该问题的动力学特性,故满足任意速度边界条件和速度不可压条件Navier-Stokes方程最优动力系统的建模方法,能够用最少的基函数最大限度地描述复杂流体问题及其动力学特性.     

专家知识库粗集建模中基于熵的数据离散化

首先分析了专家知识库粗集建模中连续数据离散化存在的问题 ,指出允许引入少量的冲突对专家知识库的建模分析是有益的 ;提出了一种基于信息熵的数据离散化方法 ,并分析了数据离散化的熵的度量 ,根据求解问题设计了一种问题求解的遗传算法 ;最后以基于多 Agent车间调度系统中调度 Agent任务分派知识库的粗集建模为例说明了方法的应用过程     

最优刀具更换周期上界、检查间隔下界的证明

本文针对 99年大学生数学建模竞赛 A题中问题 1 ,利用目标函数求出了一般情况下刀具更换周期最优解 T<μ的一个充分条件及最优检查间隔的下界 ,并证明了问题 1中刀具更换周期最优解 T<551 <μ和检查间隔最优解 n≥ 8     

A performance analysis of dispatching rules and a heuristic in static flowshops with missing operations of jobs

An experimental investigation of the performance of dispatching rules and a heuristic for scheduling in static flowshops with missing operations is undertaken in this study. The measure of performance is the minimization of total flow time of jobs. Permutation schedules are generated by using the heuristic for scheduling. General schedules, which can be permutation or non-permutation schedules, are obtained by using dispatching rules. Four dispatching rules, including a new dispatching rule, are considered. Two types of flowshops are studied: one with no missing operations of jobs and another with missing operations of jobs. In the latter type of flowshops, jobs with varying number of missing operations are considered. An extensive investigation of the performance of the dispatching rules and the heuristic is carried out. It is observed that the heuristic minimizes total flow time of jobs more than dispatching rules up to a certain level of missing operations of jobs in flowshops, after which dispatching rules perform better. The performance of the heuristic and the dispatching rules in terms of minimizing the makespan as a secondary measure is also reported.     

The role of preparedness in ambulance dispatching

Response time in the emergency medical service is an important performance measure and ambulance dispatching is one of the most important factors affecting the response time. The most commonly used dispatching rule is to send the closest available unit to the call site. However, though dispatching the closest unit enables the service to achieve the minimal response time for the current call, the response times for the next incoming calls may increase if the area where the closest ambulance is currently located has a high call rate, that is the area becomes ill-prepared. A dispatching algorithm based on the preparedness concept was recently proposed. Rather than greedily minimizing each current response time, the dispatching algorithm takes account of future calls by a quantitative definition of preparedness. This study investigates the role of preparedness by examining the performance of the preparedness-based dispatching algorithm as well as by evolving the algorithm in several ways in order to magnify the effectiveness of preparedness consideration. As a result of these efforts, it is found that the consideration of preparedness in ambulance dispatching can provide significant benefits in reducing response time but only when appropriately used.     

A comparison of different dispatching policies in two-warehouse inventory systems for deteriorating items over a finite time horizon

This paper considers a two-warehouse inventory problem for deteriorating items with a constant demand rate over a finite time horizon. A modified first-in-first-out dispatching policy is first proposed, and a new two-warehouse inventory model based on this dispatching policy is developed. The results of this model are then compared with those of other models based on classical dispatching policies, such as the last-in-first-out, modified last-in-first-out and first-in-first-out dispatching policies. We also prove the existence and uniqueness of the optimal solutions for the models considered. Finally, a numerical example is presented to illustrate the results, and several key conditions are derived for comparing the general cases of these four models.     

基于区间数的应急物资调度决策模型及算法研究

应急物资调度决策是应急物流管理的重要研究问题之一,是影响应急救援效果的关键环节,加强应急物资调度方法研究,对提升我国应急物流管理水平,提高突发事件的应急保障能力和应对效果具有重要现实意义和理论研究价值.为了提高应急物资调度决策的有效性,基于应急物资调度问题的特点,引入区间数来描述应急物资调度决策中的不确定因素,建立了区间数信息环境下应急物资调度问题的时间最小化决策模型,提出了基于满意度水平的应急物资调度问题有效解的具体算法,最后通过算例分析验证了该方法的有效性.     

生命线网络系统多节点失效的应急抢修队伍派遣模型研究

针对生命线网络系统中多个节点失效的应急抢修问题,给出了抢修队伍派遣优化模型以及模型的求解方法。在本文中,首先考虑应急修复所需时间、各节点失效所造成的损失和应急修复所需成本等因素,构建了以节点失效损失最小和应急修复成本最低为目标的抢修队伍派遣优化模型;然后针对优化模型的特点,给出了模型的求解方法。最后,通过一个算例分析说明了构建的模型的可行性和有效性。     

A new dispatching rule based genetic algorithm for the multi-objective job shop problem

Hyper-heuristics or “methodologies to choose heuristics” are becoming increasingly popular given their suitability to solve hard real world combinatorial optimisation problems. Their distinguishing feature is that they operate in the space of heuristics or heuristic components rather than in the solution space. In Dispatching Rule Based Genetic Algorithms (DRGA) solutions are represented as sequences of dispatching rules which are called one at a time and used to sequence a number of operations onto machines. The number of operations that each dispatching rule in the sequence handles is a parameter to which DRGA is notoriously sensitive. This paper proposes a new hybrid DRGA which searches simultaneously for the best sequence of dispatching rules and the number of operations to be handled by each dispatching rule. The investigated DRGA uses the selection mechanism of NSGA-II when handling multi-objective problems.     

Data mining-based dispatching system for solving the local pickup and delivery problem

The Local Pickup and Delivery Problem (LPDP) has drawn much attention, and optimization models and algorithms have been developed to address this problem. However, for real world applications, the large-scale and dynamic nature of the problem causes difficulties in getting good solutions within acceptable time through standard optimization approaches. Meanwhile, actual dispatching solutions made by field experts in transportation companies contain embedded dispatching rules. This paper introduces a Data Mining-based Dispatching System (DMDS) to first learn dispatching rules from historical data and then generate dispatch solutions, which are shown to be as good as those generated by expert dispatchers in the intermodal freight industry. Three additional benefits of DMDS are: (1) it provides a simulation platform for strategic decision making and analysis; (2) the learned dispatching rules are valuable to combine with an optimization algorithm to improve the solution quality for LPDPs; (3) by adding optimized solutions to the training data, DMDS is capable to generate better-than-actuals solutions very quickly.     

防洪物资调运的数学模型

首先构建防洪物资调运的交通网络矩阵模型,并利用Dijkstra算法寻找各调运节点之间的最优路线,然后在平时以追求最小总调运费用、紧急情况下以追求最快调运速度为目标建立了防洪物资调运的优化模型,在此过程中引入偏离控制量以便充分考虑各调运节点的需求,讨论了调运期、偏离控制量对调运费用的影响,为科学制定调运方案提供依据,较好地解决了防洪物资的调运问题.     

一种解决集装箱港口拖车调度的混合策略

集装箱码头作为集装箱船舶与其它运输节点之间的枢纽,在不断增长的全球贸易中起着极其重要的作用.由于多种因素影响着集装箱码头的服务效率,从而使其成为了商界和学术界研究的热点.本文针对集装箱码头中的拖车调度问题,对于当某辆拖车完成一项作业任务后,如何去寻找下一个装卸任务的问题,提出了一个多因素的在线调度策略,该策略在针对我国大多数港口的现有布局和信息现状的基础上,综合考虑了拖车空驶和距离平衡多种因素,建立了综合评价函数,并应用评价搜索和离散事件仿真方法对评价函数进行了优化计算.在相关理论分析基础上,通过比较本文的调度策略和港口传统调度策略,我们认为本文的调度策略在缩短船舶停留时间和减少拖车空驶上具有十分明显的效果.     

大型水电工程物资调运建模及算法

根据小湾水电工程物资供应管理的实际情况,提出了物资调运的三级节点概念模型,论述了物资采购与调运的数学模型,并给出了具体算法。模型已应用于该工程物资调运决策支持系统中,运行实践表明,该模型能够辅助调度人员制定合理的物资采购与调运方案。