配送系统优化问题的分析与建模——以多对一配送网络为研究对象

在VMI模式下,物流配送系统中,供需双方的库存与运输的全面整合优化问题是获得配送系统总成本最优化的重要问题.通过运用双层规划法,为物流配送系统中典型的多对一配送网络建立具有随机需求的、多产品的库存与运输整合优化数学模型;用改进启发式算法分析其解法;并确定配送系统优化问题的最优成本下限以验证所用启发式算法的有效性;最后,运用算例验证模型与算法在实践中对改善库存与运输系统总绩效的重要作用.     

基于动态进化算法的多阶段备件供应优化决策

由于实际备件保障工作中备件需求以间歇性需求为主,备件供应通常为多阶段的动态优化。针对以上问题,构建了多阶段备件供应数学模型。为求解动态优化模型,提出了一种元启发式动态进化算法。首先,在经典差分进化算法中增加了环境变化检测算子和环境变化响应策略,使得差分进化算法能够解决环境变化的动态优化问题。其次,提出了自适应莱维飞行策略,使得算法在环境发生变化时仍能保持良好的全局搜索能力和局部寻优能力。算例表明,所提出的动态自适应差分算法能够求得模型的最优可行解,且算法的分布性和收敛性均得到了很大的提升。     

基于异质患者行为特征的动态门诊预约策略

针对服务时间不同的异质患者,研究患者动态到达且存在取消预约和爽约行为的门诊预约策略。假设患者行为依赖于其类型,以最大化期望利润为目标,采用超订的方式应对患者取消预约和爽约行为,当患者发出预约请求时需要立刻决定是否接受该患者。建立动态规划模型刻画患者的预约过程,利用逆推法进行求解以获得最优动态预约策略;通过近似方法降低模型的状态空间维度,并设计启发式算法求解状态向量不依赖于患者类型的动态预约策略。最后,基于蒙特卡洛模拟对启发式算法和动态规划结果进行比较,验证启发式算法的有效性,并分析参数变动对最终结果的影响。     

有新任务插入的多星动态调度模型与算法研究

对地观测卫星动态调度问题是一类复杂的调度问题.在对动态调度的要求进行分析的基础上,针对有新任务插入的多星动态调度问题的特点,建立了多星动态调度模型,提出了一种基于自由度规则的动态启发式求解算法.分别设计了基于最大自由度的退出启发式规则和基于自由度比例的退出启发式规则,采用深度有限搜索策略进行迭代搜索.仿真实例分析表明,基于自由度规则的动态启发式求解算法能够较好地解决有新任务插入的多星动态调度问题.     

多类顾客需求环境下动态批量补货策略

考虑在多类顾客需求环境下有限计划期内的动态批量补货问题。在一般的补货成本结构下,每类顾客的最优补货期各不相同,且该补货问题为NP难题。考虑在没有投机行为的补货成本结构下,最优的补货策略满足"零库存补货"规则,且在每类顾客在补货周期内存在一个最优的及时服务临界期,临界期之前的需求将得到及时满足,临界期后的需求将被缺货处理。基于最优的临界期库存分配策略,提出一个多项式算法得到最优的补货策略。与先到先服务的需求服务策略进行比较,数例分析得到临界期库存分配策略可以大幅提高整个计划期的利润。最后,在一般的补货成本结构下,考虑一种特殊发货规则,提出一种有效的启发式算法,优化每类顾客的最优补货期。     

带不可用时间段和恶化加工时间的单机调度

对机器带有一个不可用时间段并且加工时间恶化的不可续型单机最大完工时间调度问题进行了研究,简单说明了此问题的NP-困难性,提出了一种动态规算法以得到最优解,并给出了最短正常加工时间优先规则的最坏情况误差界限,最后提出了一种启发式算法采寻求近似解.实验结果表明该启发式算法无论从时间上还是解的质量上都是非常优异的,与动态规划给出的最优解相比,其平均相对误差仅为0.082%,最大误差也仅为3.448%,并且将近有一半的算例能得到最优解.     

带有缓冲区的资源受限调度问题的滚动时域求解算法

研究带有缓冲区的资源受限调度问题,设计了两种使用滚动时域策略的启发式算法TWBA和FWBA,通过依次处理一定量任务,尽可能使得调度所产生的费用最小.为了评估算法性能,进行了大量模拟研究,在不同条件下找出相应的最优的处理周期或者是最优决策时刻,仿真结果表明了新算法在应用中有较好的性能,并且得到比在线算法更优的调度结果.     

基于OpenGL的移动机械手路径规划仿真

针对移动机械手的动态不均匀性及运动冗余性,参考人类完成任务时的行为,提出了一种分级协调路径规划法,以及一种动态加权的优化策略,对移动机械手的路径进行离线规划,在避障的前提下保证了移动机械手性能指标最优。在VC 下通过OpenGL进行了仿真,取得了令人满意的结果。     

带有限缓冲区的知识化制造单元无死锁调度

鉴于制造系统无死锁随机调度问题研究的缺乏,在加工时间、工件到达以及产品需求到达均为随机的生产环境下,研究了带有限缓冲区的知识化制造单元无死锁随机调度问题.针对自动机对定量指标描述能力的不足,首先给出了一种费用自动机概念.在同时考虑工件加工、库存以及缺货费用的情况下,采用无限时域折扣准则下马尔可夫链建立了单元的费用目标函数,通过一致化技术对目标函数进行离散化处理,得到目标函数的随机动态规划模型,分析并证明了单元最优目标值函数的性质.为了克服离散状态空间组合所产生的维数灾问题,提出了一种基于仿真和函数逼近的启发式近似动态规划算法对模型进行求解.在上述研究基础上,构建了一种单元无死锁随机调度策略,以保证单元安全高效地运行.最后,通过实例研究对无死锁调度策略进行了验证.     

多星联合对地观测调度问题的列生成算法

多星联合对地观测调度问题作为一类大规模组合优化问题, 其求解算法往往采用启发式或超启发式. 运用列生成思想对该问题设计了完全搜索算法. 在建立了问题的整数规划模型之后, 将原问题分解为集合配置主问题和含时间窗口的最短路径子问题, 其中集合配置主问题采用主单纯型法通过CPLEX求解, 含时窗的最短路径子问题采用动态规划求解, 该动态规划算法围绕观测冲突时段这一关键资源进行最优子路径的扩展. 只有在子问题的最优解对主问题的优化目标仍有改进时, 主问题的约束矩阵列才被扩展. 该算法针对部分算例得到了最优解, 其余算例也在指定的时间内得到了相比一种基于优先级的启发式算法更优的解.     

基于原材料订购及预防性维修中断的EPQ模型

建立了时变需求下带有多种原材料订购及预防性维修中断的制造系统在有限计划期内经济生产批量模型．利用动态规划求得各原材料的最优订购策略，采取（tj，Q）策略给出了寻求最优生产批量，最优维修中断次数及最优生产周期数的简单算法，并用数值例子说明本模型的求解过程．     

模糊能力约束下的生产批量计划方法研究

引入模糊技术 ,建立具有模糊能力约束的生产批量计划模型 ( FCLSP) .结合遗传算法和参数线性规划方法提出解 FCLSP的混合算法 ,数值实例验证了其有效性 .     

Numerical solution to optimal feedback control by dynamic programming approach: A local approximation algorithm

This paper considers optimal feedback control for a general continuous time finite-dimensional deterministic system with finite horizon cost functional. A practically feasible algorithm to calculate the numerical solution of the optimal feedback control by dynamic programming approach is developed. The highlights of this algorithm are: a) It is based on a convergent constructive algorithm for optimal feedback control law which was proposed by the authors before through an approximation for the viscosity solution of the time-space discretization scheme developed by dynamic programming method; b) The computation complexity is significantly reduced since only values of viscosity solution on some local cones around the optimal trajectory are calculated. Two numerical experiments are presented to illustrate the effectiveness and fastness of the algorithm.     

考虑批量折扣的单供货商多销售商动态规划模型

建立了有限计划期内单供货商多销售商动态规划模型。引入分配系统及最小分配的概念重新描述多销售商联合订购问题。在假定供货商提供全单位批量折扣的前提下,利用本文得到的判定最小分配的充要条件给出了寻求供货商最优生产策略及各个销售商最优订购策略的动态规划算法。最后给出了应用实例。     

动态公交网络设计的双层规划模型及算法研究

根据城市公交网络的具体特点,对公交网络进行了系统的描述,同时从公交管理部门和公交出行者两方面进行系统的考虑,提出了一个双层规划模型来描述动态公交网络设计的问题.在双层规划模型中,上层模型为一个基于时刻表的公交网络设计模型,下层模型是一个动态公交网络用户最优配流模型.针对所提出的模型,设计了基于混沌优化方法的求解算法,并给出了一个简单的数值实验来说明所给模型和求解算法的有效性.     

考虑库存能力约束的批量问题与定价的联合决策

针对多周期离散时间情形,研究了库存能力约束下如何有效地协调定价决策与批量决策,使得企业利润最大化。建立了非线性混合整数规划模型。分析了最优解的特征,详细讨论了子问题的求解方法。提出了基于动态规划的精确算法,可以在多项式时间内求解出联合决策问题的最优定价与最优生产计划。实验结果分析了库存能力与最优利润、最优生产计划之间的关系。     

基于改进DP算法的具有优先序的变速机最小化成本调度

研究了工件具有任意标准优先序、一台机器在同一时间只可加工一个工件、最小化工件加工成本与机器使用成本之和的变速机调度问题.为该问题建立了DP模型,通过启发式规则和常规动态规划方法相结合、引入工件完工时间界限并保存每一步函数值,得到改进的DP算法,数值实验显示该算法具有较强的寻优能力和稳定性.     

品种选择、货架分配与库存控制的联合决策模型

以某零售超市销售的一类产品为研究对象,假定产品的需求会受到时间、陈列库存水平和促销3种因素影响,以品种选择、货架空间分配与库存控制策略为决策变量,将3种策略的联合决策模型构建为一个非线性整数规划模型,并给出了模型求解的启发式算法.最后,构建了一个算例,运算结果表明,通过该模型的应用比该零售超市原有策略下的周利润上升了115%,说明该模型有较好的可行性和实用性,同时运算结果也给出了一些有益的管理启示.     

单机订单接受与加工调度问题的拉格朗日松弛算法

针对不同类型订单加工切换时机器需要准备时间的实际生产情况,研究了单机订单接受与加工调度优化决策问题,旨在最大化企业净收益。鉴于研究问题的强NP难属性,设计了基于拉格朗日松弛理论的启发式算法。首先,该算法通过加入相邻订单相异性约束以提高松弛解质量;其次,应用动态规划递推公式求解拉格朗日松弛问题;最后,利用问题的优化性质并基于贪婪规则构造原问题可行解。不同规模问题的实验结果表明,该算法能在合理计算时间内得到满意的近优解。     

城市公交系统连续平衡网络设计的双层规划模型及求解算法

根据城市公交网络的具体特点 ,对公交网络进行了系统的描述 ,提出一个双层规划模型来描述连续平衡公交网络设计问题 .在双层规划模型中 ,上层模型为一个标准的公交网络设计模型 ,下层模型是一个公交网络平衡配流模型 .针对所提出的模型 ,设计了基于灵敏度分析的求解算法 .最后 ,给出一个简单算例对所提出的模型和算法加以验证 .