进化规划方法在并行多机调度问题中的应用

并行多机调度问题是一类重要的车间调度问题,但迄今为止,在解决工件和机器数较多的大规模并行多机调度问题还存在着许多困难。进化规划方法与遗传算法一样是一种重要的进化计算方法,但与遗传算法相比,进化规划算法的应用还刚刚开始,特别是在调度领域的应用还很少见文献报道,第一次将进化规划方法应用到并行多机调度问题中,并在问题的描述、可行解的表示、变异方法、提高进化规划方法的局部寻优能力等方面作了研究。不同规模的计算实例表明了本文提出的进化规划算法是有效的,能用于解决较大规模并行多机调度问题,且解的质量优于启发式算法和模拟退火算法。     

客车调度问题(BSP)的数学模型及一种新的启发式算法

本文讨论并建立了客车调度问题的数学模型,着重讨论其费用矩阵和目标函数。本文提出的一种新的启发式算法,能保证该问题获得满意的可行解和非可行解。这种新算法经实践证明是有效的。     

LPGP的漂移与定位解的满意度

针对灰参数线性规划（ＬＰＧＰ）求解中的困难，提出了ＬＰＧＰ定位求解的新思路及定位规划、理想模型、临界模型等新概念；研究了定位系数变化对定位规划最优解的影响以及定位最优值的变化范围；定义了定位规划的满意度和满意解．从而可将灰参数线性规划问题化为若干个一般线性规划问题，在一定程度上解决了灰参数线性规划求解与解的评价问题     

基于多层次模型的高等教育满意值探讨

高等教育的产品就是高等教育服务，该服务产品得到的满意值应与个人、家庭、国家的利益密切相关．文章把满意值分为宏观的满意值（国家与社会的满意值）和微观的满意值（个人与家庭的满意值）两个部分，在计算国家与社会的满意值和个体暂时的满意值时借鉴了已经成熟的评价体系和量化分析方法，在计算个体长远满意值时提出一种基于投影梯度Lagrange乘子的约束优化方法来构造增广函数，这种方法有效的避免惩罚函数方法带来的迭代收敛速度慢、工作量大、Hesse矩阵越来越病态的问题．这种方法可以较为有效的计算现阶段高等教育的满意值，得到要适当降低高等教育收费，提高高等教育质量的结论．     

控制系统设计的满意优化方法

控制系统的参数设计可归结为一类多指标优化问题.本文介绍了关于控制系统设计的满意优化方法的一些研究工作.给出了可用于控制系统参数设计的满意优化计算模型,并通过算例说明了该模型的应用方法.通过对满意控制问题的分析,指出了进一步的研究问题.     

日计划机车周转图智能编制方法的研究

给出了日计划机车周转图的约束满足优化问题模型及其智能求解算法,该模型以列车工作计划、机车技术作业时间、乘务员作息时间、１８点归位机车台数、检修机车最晚到达基本段时间及段备机车的最早可解备时间等作为约束条件,以减少机车在站停留时间作为目标．该模型的智能求解算法将启发式知识与回溯策略相结合,以求得日计划机车周转图的满意解．     

基于反馈控制原理可靠性多目标优化设计的满意解

通过对多目标优化问题不确定性因素的分析,将有效解问题扩展到模糊多目标优化模型软计算满意解求解问题．利用模糊集理论中隶属函数,将各子目标模糊化后处理为满意度函数,进而在分析控制系统中的闭环控制原理和多目标满意解优化软计算的动态过程的相似性后,提出了建立基于闭环反馈控制原理,由协调校正权函数、相对优属度函数和重要性加权指数构成的多目标满意解总评价函数方法．最后,给出机械零件可靠性多目标满意解优化实例进行验证．     

应用启发式与逐步动态规划法进行机组最优组合

提出了一种机组组合优化的新型启发式方法，与现有的启发式方法不同之处是计及随时间变化的启停机费用对机组优先级的影响，并提出由开启机组决定所带负荷曲线；将该启发式方法与逐步动态优化法相结合进行机组最优组合，使计算时间大为减少，同时可保证得到最优解。计算结果表明，该法具有较好的实用性。另外，文中对现有的机组组合优化方法作了简要评述。     

用禁忌搜索算法求解单机总加权拖期最小问题

针对以总加权拖期最小为目标的单机调度问题,提出了一个将启发式方法与禁忌搜索算法相结合的混合禁忌搜索算法HTS（HybridTabuSearch）。利用启发式方法产生初始解,随后通过禁忌搜索算法逐步提高解的质量。大量实验结果表明,提出的混合禁忌搜索算法能够在较短的时间内得到令人满意的较优解。     

基于遗传算法的单件准时化生产计划

设计了一种遗传算法,用来解决以准时生产为目标的单件制造业生产计划问题,提出了基于投产日期的生产计划编码方法,这种编码方法直接把生产计划映射为一个有序的字符串,并针对这种编码设计了专门的交叉算子和变异算子,相似度检验增加了初始种群的多样性;小生境进化技术的运用有效地保持了群体的分布性;种群并行进化策略、变异率自适应调整、与启发式算法相结合等措施提高了遗传算法收敛到最优解的成功率。     

资源受限最小赋权树形图的一种贪婪分解启发式算法

资源受限的最小赋权树形图问题(RMWA)是NP-难的,针对RMWA问题给出一种新的贪婪分解启发式算法.通过分解目标函数和约束条件,把RMWA模型分解成一个最小赋权树形图问题和n个独立的特殊背包问题.对这n个独立的特殊背包问题,设计贪婪算法求其解,其时间复杂度为O(nmlog2m);然后调整该解使其满足树形图的约束条件得到RMWA问题的一个可行解,该算法总的复杂度为O(nm2).最后,给出实例来阐述该贪婪分解启发式算法.     

调运问题的新解法──元素判别值分配法的研究与实现

对运筹学的调运问题提出一种新解法──元素判别值分配法.它不同于国内外现行的任一种方法,只须一次调配即获最佳方案,不必进行调整.此法既便于人工操作,又易于程序实现.     

基于多邻域的车辆路径优化迭代局部搜索算法

针对物流配送中的带有容量约束的车辆路径优化问题,提出了一个基于多邻域的迭代局部搜索算法HILS.首先用简单插入法构造可行解,然后从该初始解出发,在多邻域内进行局部优化.当陷入局部最优解后,根据解的接受准则,选择某个解,并对该解进行扰动,然后从扰动后的解出发重新进行局部优化.为提高搜索效率,局部优化过程只在限定邻域内进行.在国际通用的14个benchmark问题上进行仿真实验,结果验证了本文算法HILS的有效性和稳定性,与文献中的其他几种算法的比较结果表明,算法HILS的总体性能更优.     

一种求解最大二等分问题的分散搜索算法

最大二等分问题是图论中的一个NP困难问题.本研究提出一种基于分散搜索框架的启发式算法求解最大二等分问题.该分散搜索算法采用Kernighan-Lin算法作为局部搜索算法,利用解的质量和解之间的距离构造参考集,通过两个可行解构造新的可行解.利用一些标准测试例子测试算法,实验结果与现存算法所得结果比较,表明该算法是有效的.     

考虑排班的人力资源投入问题的建模与优化

结合实际生产或项目中的排班情况,提出考虑排班的人力资源投入问题。针对该问题建立了以最小化人力资源投入为目标的数学模型。根据资源投入量与排班约束的性质,将原问题数学模型简化,证明简化后问题的数学模型与原问题最优解一致,并通过CPLEX软件求解过程,说明简化后的数学模型在求解速度上表现出很大的优越性。对于大规模问题,由于排班约束会导致班次间资源占用,使用传统任务列表编码方式难以获得较优的解。为此,提出了一种新型编码方式的遗传算法。该算法采用对作业延迟时间进行编码的方式,对作业开始时间进行搜索。为了提升算法的局部搜索能力,对作业延迟时间和开始时间进行局部优化。最后,通过数值实验与CPLEX和文献的算法比较,表明该算法的有效性。     

一种有效的启发式Flowshop调度算法

通过引入完工时间下限和优先权 ,Rajendran提出的启发式算法取得了良好的计算效果。本文对该算法进行了有效的改进 ,所提出的算法充分考虑了各种调度排序影响因素 ,将它们作为调度因子有机组合起来 ,添加到新提出的调度算法中。实验数据表明 ,新算法具有良好的计算效果 ,调度算法在高阶 weighted flowtime减少 2 .71 %左右。     

带时间约束的配送网络流问题

考虑带时间约束的物流配送中的网络优化问题,即由配送中心向各个客户通过某种运输工具（如货车）供应货物的问题,目的是在满足各客户对时间和需求量的要求下尽可能降低配送成本.首先不考虑时间约束,通过一个混和整数规划模型来加以描述,以网络单纯形法、拉格朗日松弛算法以及试探法为主要研究方法,有效地得到在没有时间约束条件下的一个近似程度较高的可行解;再在所得结果的基础上进行修正直到得出满足时间约束的可行解.     

基于混合算法求解ELSP问题的可行域分析

本文给出求解ELSP问题(Economic Lot Scheduling Problem)的可行域的特征、启发式规则和演化神经网络设计问题.经济批量问题采用基本时段方法表示,该方法产生两类决策变量,一种是表示基本时间段的连续变量,另一种是表示时间倍数的整数变量.在求解ELSP问题的算法设计中,可行域是判定启发式规则有效性的基础.为了给出可行域的特征,利用神经网络的演化计算,设计求ELSP问题的初值算法,设计演化参数函数、网络结构、演化函数、演化规则,并依此获得可行域的约束条件.对在可行域约束条件和启发式规则下设计的算法进行测试,并与用HGA和一般GA方法求解ELSP问题进行比较,求解效果明显提高,使得在满足可行性的前提下总费用减小.     

Integrated Quay Crane and Yard Truck Schedule Problem in Container Terminals

Quay crane and yard truck scheduling are two important subproblems in container terminal operations which have been studied separately in previous research. This paper proposes a new problem for the integrated quay crane and yard truck scheduling for inbound containers. The problem is formulated as a mixed integer programming (MIP) model. Due to the intractability, a genetic algorithm (GA) and a modified Johnson's Rule-based heuristic algorithm (MJRHA) are used for the problem solution. In addition, two closed form lower bounds are given to evaluate the solution accuracy. Computational experiments show that the solution algorithm can efficiently handle the scheduling problem and that the integrated methods are very useful.     

遥感卫星地面站资源调度的混合分解算法

针对传统算法逐渐难以满足地面站资源调度对精度和时效要求的问题, 提出一种混合分解算法. 该算法结合基于地面站资源使用冲突程度评价指标的启发式算法和Lagrange分解算法对问题进行求解, 以加快对最优解的搜索速度. 仿真测试结果表明, 该算法能在较短时间内得到遥感卫星地面站资源调度问题的高质量解.