一种解决有限缓冲区流水车间调度问题的复合启发式算法

针对以最大完工时间为目标的有限缓冲区流水车间调度问题,提出了一种新的复合启发式算法.算法设计中首先使用PF-NEH算法进行解空间的搜索,并采用基于插入邻域和交换邻域的可变邻域搜索算法来增强局部搜索.仿真实验表明,该算法具有高效性和优越性.     

基于VNS-EM混合算法的两阶段装配流水车间调度

针对以最小化工件提前期和拖期惩罚费用加权和为目标的两阶段装配流水车间调度问题,证明了工件之间的最优排序性质,并将其嵌入优化算法中.由于该问题的NP难性,提出了一种变邻域类电磁机制(VNS-EM)混合算法.该混合算法在类电磁机制(EM)算法的每一次迭代过程中嵌入改进的变邻域搜索(VNS)算法,利用其较好的局部搜索能力对每代最优个体的邻域进行精细搜索,从而提高解的质量.仿真结果表明了算法的有效性.与VNS算法和EM算法相比较,提出的VNS-EM混合算法能更好地兼顾算法的精度和求解速度.     

基于跨邻域搜索的连续域蚁群优化算法

针对连续域蚁群算法寻优能力差、容易产生局部最优的问题,提出了一种基于跨邻域搜索的改进蚁群算法。首先,通过自适应种群划分方式计算可行解和不可行解群体;然后,针对不可行解群体利用自主选择学习算子选择对象进行学习,目的是不断扩大种群规模,避免算法陷入局部极值点,继而对可行解群体采取全局跨邻域搜索的方式,引导蚂蚁向全局最优解靠近,加快收敛速度;最后,基于全局最优解采用局部跨邻域的方式引导蚂蚁在小范围内进行细致搜索,提高收敛精度。通过与其他连续域蚁群优化算法针对CEC2017测试函数在低维和高维情况下的实验对比,证明本文算法具有较好的寻优能力和稳定性,能有效避免陷入局部最优。     

作业车间调度问题的新型邻域结构

针对作业车间调度问题(JSP),在现有邻域结构的基础上进行拓展,提出一种新型邻域结构.通过对现有邻域结构中产生可行邻域解的约束条件进行松弛,能够使得当前解生成更多的可行邻域解.使用禁忌搜索算法将已有的3种常见的邻域结构与该新型邻域结构进行对比,使用TA数据集中的前50个算例进行验证.实验结果表明:设计的新型邻域结构无论在最优值还是平均值,都比其他3种邻域结构具有优势.实验数据表明:新型邻域结构在4种邻域结构中能够搜索的最多可行邻域解.尽管新型邻域结构搜索花费的时间最多,但由于使用了近似评估方法,因此搜索时间在可接受范围内.     

混合流水车间调度问题的两阶段启发式算法

针对以最小化makespan为目标的混合流水车间调度问题,提出了一种两阶段启发式算法。在算法设计中,借鉴求解常规流水车间调度问题的经验,定义了一种相邻交换的邻域结构。算法的第一阶段利用基于排列排序的Nawaz-Enscore-Ham(NEH)算法求得一个较好的初始解,第二阶段通过邻域搜索来提高解的质量。基于benchmark算例的仿真实验结果表明该算法的有效性,与NEH相比,77个算例的平均偏差降低了2.004%,且其运行时间不超过0.031 s。     

考虑能耗和准时的混合流水线多目标调度

针对加工时间和交货期模糊的混合流水线,考虑阶段内并行机互不相关、换模时间与工件加工次序相关等约束,面向降低生产能源消耗和保证准时交货的双目标调度问题,提出一种改进型差分进化算法.首先,以最小化系统能耗和准时交货惩罚为优化目标建立双目标优化数学模型;在此基础上,使用NEH(Nawaz, Enscore, Ham)方法获得优质初始解,并利用优质解挑战机制进行有效的邻域挖掘;同时,引入混沌搜索策略以保证算法的全局搜索能力;最后,将数值实验与有代表性的算法的计算结果进行对比,以验证所提算法的可行性与有效性.     

基于遗传和禁忌搜索算法求解双资源车间调度问题

针对柔性生产环境下的车间调度问题,在考虑遗传算法早熟收敛特性和禁忌搜索法自适应优点的基础上,将遗传算法和禁忌搜索法结合起来,提出了基于遗传算法和禁忌搜索算法的双资源作业车间的调度优化问题算法,即不仅考虑到了每个工件有几条可行的工艺路线,而且考虑到了工件的调度受到机床、工人等资源制约的影响,并用实例对该算法进行了仿真研究.结果表明此算法有很好的收敛精度,是可行的,与传统的调度算法相比较,体现出其明显的优越性.     

周期性居家医疗护理问题的禁忌求解算法

针对周期性服务需求的居家医疗与护理资源管理问题，提出一种基于插入法和节约算法的禁忌算法。该算法综合考虑客户接受服务的日期、客户的服务等级和客户访问次序，在初始解基础上进行邻域搜索，每次邻域搜索选取部分客户，搜索其所有可能的服务日期、服务等级对应的调度方案，选择成本最低的方案作为邻域搜索的最新解。邻域搜索中变换过的客户将列入禁忌表，在禁忌步长内不予变换。通过多次迭代，求解结果向最优解方向收敛。对随机生成的算例及基于标准 Vehicle Routing Problem （VRP）算例构造的算例进行仿真验证，并与 Rolling Horizon Myopic Planning Approach （RHMPA）算法求解结果对比，实验结果表明，该算法在一定运行时间内适合求解客户规模低于500人的案例，且求解结果优于 RHMPA 算法，多次求解的结果相对误差仅为0．94％。该算法为家庭护理管理和计划调度问题提供了新的算法设计优化思路，对提高当前我国相关产业的管理和调度水平具有现实意义。     

面向作业车间调度问题的改进型蝙蝠算法

针对作业车间调度问题(Job shop scheduling problem,JSP),提出了一种改进型蝙蝠算法(Improved bat algorithm,IBA)以优化车间内工件的最大完工时间.根据作业车间调度问题的特点以及基本蝙蝠算法的搜索机制,首先对个体位置向量进行了设计,实现了蝙蝠算法中离散问题的连续编码;然后分别采用GT算法和随机生成两种方法对算法种群进行初始化,以提高初始解的质量.此外,采用三种邻域结构,并在此基础上设计了变邻域搜索策略作用于最优个体,以避免算法出现早熟收敛,提高IBA算法的性能.最后,针对JSP问题的基准算例进行了大量的仿真实验,计算结果验证了本文所提出的IBA算法的可行性和有效性.     

基于混合变邻域遗传算法的柔性车间调度研究

针对柔性作业车间调度的问题，以最大完工时间为目标建立数学模型，提出一种混合变邻域遗传算法。采用三种初始化方法保证初始解的质量，用遗传算法进行初步搜索，将搜索的结果通过迭代贪婪策略进一步搜索，以提高解的质量，再对关键路径进行邻域搜索，设计“跨机器工序搜索邻域”、“同机器工序搜索邻域”、“次优工序搜索邻域”三种邻域结构，加强局部搜索能力。引入迭代贪婪策略和改进的邻域结构可显著提高算法的稳定性与迭代速度。通过对国际通用的柔性作业车间调度基准算例进行测试，实验结果表明所提改进算法能够有效求解柔性作业车间调度问题。     

作业时间依赖资源分配决策的项目调度问题建模与算法

针对实际问题的需求,提出了作业时间依赖资源分配决策的项目调度问题.以最小化项目工期为目标,建立了作业时间与资源分配量呈函数关系的资源受限项目的调度模型,提出了基于1-opt及2-opt局部搜索的遗传算法以提高算法的求解质量,分析了2-opt局部搜索中的作业组合情形,归纳与证明了不同作业组合调整与问题目标之间的关联性质,在此基础上建立了选取有效作业组合的方法,以提高算法在局部搜索求解中的效率.数据实验结果表明,所提算法相较于现有算法,其求解的质量和速度均具有优越性.     

单无人搬运车/单缓冲区约束的柔性生产系统调度研究

阐述了无人搬运车( AGV)在柔性生产系统中的调度规则,并在此基础上建立了实现工件调度和AGV调度集成问题的数学模型.改进了普通的遗传算法,设计了二次解码算法,优化了基因序列,实现对遗传算法的优化.调度结果不仅给出了各加工站的优化作业顺序,而且给出了AGV的行走优化路径.实验结果表明,改进的遗传算法的计算效率比普通的遗传算法高,同等计算条件下设备利用率也明显提高.     

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

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

单件车间生产作业计划再生方法研究

针对单件车间生产作业计划的再生问题,用ＶｉｓｕａｌＦｏｘｐｒｏ开发了一个时间调整算法和实现了禁忌搜索算法．当干扰发生时,前者用于无可替代机床情况下对受影响工序的开工时间和完工时间的调整;后者用于有可替代机床情况下对在替代机床上加工工件的排序．实验表明,它们能较好地解决各种情况下生产作业计划再生问题．     

一种求解柔性作业车间调度问题的改进灰狼优化算法

针对柔性作业车间调度问题,以最大完工时间最小化为目标提出了一种改进灰狼优化算法(IGWO),采用两段式的编码方式来构造算法个体位置与调度方案之间的关系,使用基于启发式规则的初始化种群方法来提高初始解的质量.为了平衡算法的全局搜索与局部搜索,提出一种基于双曲正切函数的非线性收敛因子公式,并在算法的个体更新阶段提出了一种基于适应度值的加权方法,在算法决策层嵌入了变邻域搜索算法.通过仿真实验表明,算法在求解柔性作业车间调度问题上是有效的.     

误工排序问题的研究

误工排序问题是经典排序论中最基本和最重要的问题.40年来国内外许多学者对其进行研究的兴趣有增无减,深刻的成果不断涌现.本文阐述2006年以来重庆师范大学运筹学与控制论专业的硕士研究生在研究误工排序问题上得到的成果及其意义.这些成果包括研究经典的和推广的误工问题,包括某些工件必须不误工,或者工件的就绪时间不相同、与交货期有一致性的,或者带权的误工排序问题,或者工件的加工时间与工件的权有反向一致性,或者多台平行机误工排序问题等等得到的成果.     

单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

带准备时间的任务单机学习效应排序问题

具有学习效应的任务的加工时间和带有准备时间的任务问题是排序论中的重要研究内容,它们对任务的完工时间有重要影响．研究了具有学习效应且带有准备时间的任务单机排序问题,其中学习效应指的是任务的实际加工时间是该已经排好的任务对数加工时间的递减函数,目标函数为最小化总完工时间．这个问题是NP-难问题．用分支定界法给出了此问题的最优解,为了提高分支定界法的运行效率,同时给出了一个启发式算法、几个优势性质和两个下界．计算结果表明分支定界法和启发式算法求解此问题非常有效．     

半开放式多车场车辆路径问题

基于现代物流业发展的实际需要,提出半开放式多车场车辆路径问题,并建立了数学模型.由于半开放式多车场车辆路径问题具有NP-hard性质,为了有效求解,基于车辆路径问题中的经典路径构造算法和局域搜索算法,设计了求解所提出问题的节约算法、顺序插入算法和并行后悔插入算法.利用标准算例进行数值试验,分析了3种算法中的参数和所嵌入局域搜索方法对求解结果的影响,并对不同算法的求解结果进行了对比分析.关