基于Petri网和UML的流水作业调度模型设计及实现

为了对流水作业调度的行为提供支持,需要对其进行有效的建模和模型分析。Petri网具有坚实的理论基础和易于使用的图形表示,是一种理想的建模和分析工具。UML是一种易于编程实现的面向对象建模工具。针对UML和Petri网建模的特点,本文采用Petri网与UML相结合的建模分析方法,融合了Petri网精确、严格的形式化描述和UML友善的用户界面的优点。并提出了将Petri网转化为一种可以表示对象间的同步、并发的扩展状态图的方法。利用Petri网描述系统的动态特性,经过分析、验证或仿真后,通过提供的转化规则将Petri网模型转化成相应的UML动态图、扩展的状态图,对流水作业调度问题建模。利用动态规划算法解决满足Johnson法则的最优作业调度问题,并用Java实现。     

二机流水作业带不可用区间、工件可拒绝的调度问题

考虑了二机流水作业第一台机器带不可用区间、工件可拒绝的调度问题.所有的工件都是加工可中断的,即当某一工件在不可用区间出现之前开始加工但在机器不可用时并未加工完成,在不可用区间结束后可以接着加工.目标函数是最小化接受加工工件的最大完工时间与拒绝工件的惩罚之和.此问题是NP-难的.首先提出了一个动态规划的最优算法以求解小规模问题,并给出了数值计算实例.所提出的动态规划算法的运算时间随着问题的规模成指数增长,进而又提出了一个启发式算法,并证明了该启发式算法的最坏性能比是3.     

最小化总完工时间的流水作业调度混合算法

针对有效求解NP难的总完工时间最小流水作业调度问题,提出了一个有效的混合启发式算法产生初始解,并使用禁忌搜索算法对初始解邻域进行搜索的算法框架.基于不同的启发式算法,获得了3个混合禁忌搜索算法HA1,HA2和HA3.使用Taillards基准程序随机产生的大量实例,进行模拟实验,结果表明,所提出的3个算法通过扩大搜索范围提高了解的质量,在性能上均优于目前最有效的启发式算法.与目前最有效的算法相比,产生最好解的平均百分比偏差均下降至少30%,最优解所占比例皆有显著提高.     

智能混合优化策略及其在流水作业调度中的应用

通过结合蚁群算法(ACO)的并行搜索结构和模拟退火算法(SA)的概率突跳性,提出了一种有效的混合优化策略,并将该策略应用于流水作业调度问题(FSP)．在该策略中,蚁群系统的一个周游路线为模拟退火算法提供了一系列初始解,在每个退火温度上进行抽样准则检验并产生新解,然后更新信息激素;蚁群算法再利用模拟退火算法产生的新解进行并行搜索．同时,根据此策略构建并实现了针对FSP问题求解的具体混合算法．仿真结果表明,混合算法弥补了ACO易陷入局部最优和SA搜索效率较低的缺点,增强了全局搜索能力,在求解FSP调度问题的性能上也优于其他算法。     

漳泽水库库群防洪实时优化调度模型研究

根据漳泽水库库群的特点，按照水库每时段动用的调洪库容加权总和最小的准则，建立了水库群系统联合防洪实时优化调度的动态规划模型，采用逐步优化算法进行求解，并通过前向卷动决策方法实现洪水的实时调度。实例证明了该模型及其求解方法的合理性及可行性。     

基于演化多目标算法的混合流水作业调度优化

针对供应链网络优化领域中的混合流水作业调度问题提出了一种新的多目标演化优化算法。给出了这类问题的通用优化模型，在此基础上，提出了基于流程的矩阵基因编码方案，动态适应度分配机制，并引入小生境保优策略构造了算法过程，利用收敛进程参数分析了算法的收敛性能。性能分析和算例实验表明算法对于高维多目标优化问题是有效的，且能够以较快的速度收敛。     

奎屯灌区水库群水资源优化调度模型

运用统计分析水源,利用Jensen模型表达缺水对作物产量的影响。以灌区综合保证率最大为目标,建立灌区水资源配水模型,探讨了λ值的确定问题,借助动态规划、线性规划和一维搜索介绍了水源时空的分配和子系统的协调。     

流水作业调度问题的快速进入启发式算法改进

文章提出了解决流水作业调度问题的改进快速进入启发式算法。这种改进算法遵循原算法中构造双机子问题的基本思想,将原线性权重改进为指数权重并用Johnson双机算法进行求解。改进算法的性能使用了来自文献的实例测试,并与原算法进行比较。比较结果表明,在大规模工件的调度问题中改进算法优于原算法。     

基于多目标动态规划模型的水库优化调度研究

针对以灌溉为主要供水任务的水库，阐述了多目标动态水库调度模型的组成，引入罚函数将多目标单一化处理，并给出了迭代算法。实例结果表明，本文方法可以为水库优化调度提供有益的参考。     

柔性流水作业排序问题的贪心算法求解

柔性流水作业排序问题是一类复杂的车间作业调度问题。针对通常情况下调度问题求解困难的问题,给出了求解柔性流水作业排序问题近似解的贪心算法,并对其性能进行了分析测试。结果表明,虽然该贪心算法求出的近似解与最优解相比有一定误差,但由于其时间复杂度较小,因此对求解车间作业调度问题仍有一定的现实意义。     

城市公共交通调度CAD软件系统模型

对公共交通调度CAD软件系统进行了详细的需求分析,按照面向对象软件工程的设计思想,以UML为工具,从静态模型和动态模型角度建立了软件系统的模型,包括采用系统用例图、类结构图和时序图对系统进行了模型描述.该模型已通过采用MFC提供的文档/视图机制进行了系统实现,软件具有易于使用、维护、运行速度快和对硬件要求低等优点.     

一类三机器流水作业极小化加工全长问题

一般的三台机器流水作业的加工全长问题为强NP困难的．本讨论它的特殊情形，即第二台机器上工件的加工时间均相等．我们证明了该问题仍为强NP困难的，并构作了一动态规划算法，最后讨论问题的可求解情形．     

公交车调度模型

在假定乘客到达时间服从均匀分布的基础上，为公交车的调度建立了一个线性规划模型，并通过实例说明了该模型的应用。     

动态规划算法在小浪底水库优化调度中的应用研究

采用运筹学中的动态规划法建立水库优化调度模型,并利用此模型对小浪底水库调度问题进行建模并求解.     

轧钢切断阶段动态HFS调度模型和LR算法研究

以钢管生产为背景,在分析钢管切割工艺的基础上,提炼出第一阶段具有批处理特征的动态HFS调度问题,建立了数学规划模型,目标是最小化所有工件的加权完成时间.针对该模型,构造了改进的拉格朗日松弛算法(lagrangian relaxation,LR)的求解过程,设计了求解批级子问题的动态规划算法和构造可行解的启发式算法.     

并行流水车间调度问题模型与算法研究

将大型钢管企业的管加工调度问题抽象提炼为一类具有普遍意义的并行流水车间调度问题,建立了数学规划模型,并对其求解算法进行了探讨。     

葛洲坝水电站厂内优化调度分析

水电站厂内优化调度是一个优化问题,它包括机组组合,负荷分配以及机组检修等问题.针对葛洲坝水电站厂内经济运行要求,在满足电能生产的安全、可靠、优质的前提下,基于动态规划以及遗传算法2种优化方法,对葛洲坝各机组优化调度进行了研究,合理的安排组织电厂设备的运行,以获得尽可能大的经济效益.由计算结果可以看出,运用的2种方法都能较好地求出最优结果,在给定水头和总流量的情况下,合理的进行流量分配,从而实现葛洲坝生产调度的优化运行.     

平行三阶段流水作业问题的近似算法

研究了n个三阶段工件在m个流水车间进行加工的排序问题,目标为最小化最大完工时间。当m是定值时,该问题是NP困难;当m2时,问题是强NP困难。将问题分解成3种情形,情形1给出了7/3-1/(3m)的近似比;情形2给出了一个3的近似比;情形3给出了近似比为23/6-1/(3m)。结合3种情形,最终给出了性能比为23/6-1/(3m)的算法。     

基于改进遗传算法的Flow Shop调度算法研究

给出了Flow Shop调度问题的数学模型,介绍了三种用于求解该问题的启发式算法,根据普通遗传算法与启发式算法的互补特性,提出了结合两者各自优势的改进遗传算法．通过两个不同规模的经典算例对算法的优化性能进行了对比分析,结果表明,采用了保优策略的改进遗传算法的搜索能力优于启发式算法及普通遗传算法,并具有较强的鲁棒性．