具有周期维护的最小化工件完成时刻之和的平行机调度问题

考虑具有周期维护的m台平行机调度问题,一组给定的工件在这些机器上加工,目标是给出工件完成时刻和最小的调度方案。基于经典的SPT(最短加工时间优先)算法,提出了名为MSPT的启发式算法,并证明了该算法优于SPT算法。     

基于交替迭代遗传算法的多级车间生产计划与调度的集成优化

为了提高多级生产系统的运作效率,研究了一类多周期的多级车间生产计划与调度的集成优化问题,该生产系统由一级混批Job-shop车间和一级混流装配车间串联而成.首先建立了该类集成优化问题的混合整数规划模型,该模型从上下游生产车间的需求关系出发,综合考虑上下游车间的物料平衡、设备负荷以及开工位置等约束条件,同时满足优化上下游生产线的费用目标.然后提出了一种交替式混合遗传协调优化算法求解该集成优化问题,其主要思想是给定计划用一种混合遗传算法求调度,反过来给定已求调度用另一种混合遗传算法求取新计划,如此不断交替使用2种混合遗传算法实现计划与调度的同时优化.仿真结果证明了该方法的可行性和有效性.     

带有可控性维护的单机调度问题研究

为在附加费用不大的条件下,通过最小化工件完成时间之和来减小work-in-process中的库存,尽可能使工件按期交付,在将工件调度与机器维护统一进行考虑的模型基础上,提出了带有预防性维护的单机调度问题,并对其进行了建模.将机器的维护周期适当放宽,以便在保证总的附加费用不超出预先给定的一个常数的前提下,实现工件的完成时间和的最小化.对工件加工允许中断的情况给出时间复杂度为O(n*ln(n));对工件加工不允许中断的情况给出一个启发式算法,其时间复杂度为O(n2).由该启发式算法很容易得到问题的可行解,从而为问题的进一步研究打下了基础.     

No-Wait流水车间调度问题的MDIS算法研究

No-Wait流水车间调度问题的特性是工件加工一旦开始,必须连续进行,不允许工件完成某一加工工序后在机器上滞留等待.本文针对目标函数为Makespan的No-Wait流水车间调度问题,从对目标函数结构的分析入手,提出了一种基于最小化工件间距离的初始排序策略和插入方法的启发式算法.通过对大量典型算例的实验后验证了提出的算法的有效性.     

基于生产费用的柔性作业车间调度优化

考虑在制品库存费用、机床工时费、直接工人的工资费用、工件的提前和拖期完工造成的损失费用,提出了一种双资源柔性作业车间调度的生产费用计算方法.将模拟退火算法嵌入遗传算法中,设计了一种新的混合遗传算法.该算法首先利用遗传算法快速搜索一组较好的解,然后利用模拟退火算法进行群体寻优.采用基于工序的编码和一种新的解码方法,并运用多种交叉方法使得算法能够在解空间中尽可能地搜索最优解.为了避免最优解在进化过程中损失,采用择优操作将每代中的最优解保留下来,并不断更新.仿真结果表明:该方法是可行的,并具有一定的优越性.     

一种求解制造／再制造混合系统车间调度的启发式算法

针对传统方法在求解制造／再制造混合系统车间调度时存在的问题,根据制造／再制造混合系统车间调度的特点,提出了最早交货期一最长加工时间（earliest deliverydate-longest processing time fist,EDD-LPT）的启发式算法。首先,将全部工件按照交货期的时间非减排列,对于交货期相同的工件,则按照再制造修复时间非增排列。然后,依次将工件安排在修复费用最小的设备上。对于再制造修复费用和延迟交货费用之和大于新品制造费用的工件,则采用新品制造替换。最后,给出了EDD-LPT启发式算法的最坏误差界。实例研究表明,EDD-LPT启发式算法较传统方法在计算时长方面具有更好的性能。     

基于时间与费用双优化的虚拟企业调度算法

基于合理抽象虚拟企业模型和任务模型,建立虚拟企业生产任务计划的数学模型,并提出了一种时间与费用双优化的调度算法.该算法分别针对虚拟企业生产调度的时间与费用2个目标提出启发式优化算法,并以调度优化的结果作为遗传算法的初始染色体,通过对遗传算法运算的重新定义来优化虚拟企业生产计划调度,充分发挥遗传算法良好的全局搜索能力和能有效避免陷入局部极小的优点,提高了算法的全局寻优能力.实验结果表明,启发式优化算法与遗传算法相结合的优化技术能够降低虚拟企业生产费用,使企业具有较好的生产敏捷性.     

柔性作业车间多目标调度优化研究

研究了多目标柔性作业车间调度问题(FJSP),提出了一种基于Pareto的混合遗传算法,并建立了包括生产周期、总拖期时间和机床负载在内的多目标优化模型.该算法采用基于工序的编码方式和活动化解码方法,将Pareto排序策略与Pareto竞争方法结合起来.为了保证解的多样性,采用小生境技术并同时使用多种交叉方法,用Pareto解集过滤器保存进化过程中的最优个体,防止最优解的遗失.算法最后给出问题的Pareto最优解集.仿真试验证明,提出的混合遗传算法可以有效解决多目标FJSP.     

具有双重时间窗约束的作业车间调度算法

为解决实际生产调度中等待时间受限引起的工件加工时间窗约束和设备能力有限引起的机器可加工时间窗约束,以工件完工率最大为优化目标,建立了具有双重时间窗约束的作业车间调度模型,提出了求解该模型的基于启发式规则的禁忌搜索算法。在分析优化目标与约束条件关系的基础上,提出了工件选择和机器分配的启发式规则,并利用启发性规则生成初始调度方案;设计具有块邻域结构的禁忌搜索算法,减小了邻域规模,通过迭代优化最终获得较优的调度方案。选择多种不同规模的算例与传统算法进行对比分析,实验结果表明了所提算法的可行性和有效性。     

混合Flowshop双目标调度问题的双向仿真方法

针对JIT生产方式的混合Flowshop系统双目标调度问题，提出一种基于前向和反向仿真组合的双向仿真调度方法。用启发式算法进行前向仿真获得工件离开系统的时刻，并将其作为反向仿真的开工时刻。按工件的反向路由（加工顺序）进行反向仿真，以获得工件正向进入系统的较好时刻，从而减少工件的等待和平均的flowtime。仿真结果表明，该方法 能够较好地解决混合Flowshop的双目标调度问题。     

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

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

具有加工顺序约束和非对称模糊加工时间的工期指派调度方法

研究了工件加工时间是非对称模糊数、工件间具有优先加工顺序约束、目标函数为极小化提前完工惩罚和拖期完工惩罚和的均值的单机工期指派调度优化问题.证明了当模糊加工时间具有相同宽度比、优先加工约束关系为树状约束时,该问题是多项式可解的.进一步,当优先加工顺序为一般约束时,基于线性规划松弛技术,设计了近似比为2的近似算法.      

带有扩充链优先约束工件的分批排序问题

提出一种工具之间带有扩充链的优先约束的分批排序问题,这种扩充链上既有优先序工件又有无约束工件(工件个数不定)。目标为极小化最大完工时间。优先约束为有m个优先约束集,其中一个"扩充链"上有n个工件,其余m-1条链上的工件数为常数,工件的加工不可中断。问题1chains,B=mCmax为多项式可解,同时给出了问题的一个多项式算法。     

TS求解多机成组工件调度

讨论并行多机成组工件的极小化最大通过时间调度问题·它是一个非常复杂的组合优化问题,是NP难题·为了解决此类问题,采用了两种智能优化算法方法·通过大量的仿真实验,将两种方法进行了比较·结果证明:禁忌搜索结合启发式的智能优化算法可靠性高、运算速度快,有能力有效地解决大规模实际问题·     

改进遗传算法求解柔性job-shop调度问题

本文提出了一种改进遗传算法用于求解柔性作业调度问题(FJSP).针对工序在不同的机器上加工的差异性,我们提出了用能力系数来表征机器的加工能力,不仅可以简化处理而且也较为符合实际情况.该改进算法通过轮换的方法,将加工任务分配到不同的并行机器上去执行,有利于机器的负载平衡.同时,在方法的实现过程中,利用面向对象的思想,将问题进行抽象,用不同的类封装车间,机器和工序信息,这不仅符合现代编程风格,简化编程,也有利于系统的扩展和重构.仿真结果表明,不仅整个加工过程的执行时间得到了优化,而且各类机器完成的操作数相同,使用的时间也较为平均,达到了设计目标.同时该方法的计算速度也较快,适用于较大规模作业车间调度问题的求解.     

带有单服务器的并行机调度问题

研究了一类具有准备时间和移出时间约束的单服务器并行机调度问题.这个问题概括了工件仅需要准备操作的经典单服务器并行机调度问题.在该问题中,服务器不仅需要在每个工件加工之前将其装载到一台机器上,而且在工件加工结束后,将其从机器上卸载下来,装载和卸载操作需要一定的时间.目标函数为最小化最大完工时间.主要研究指定机器加工的情况,针对这种情况,构建了多项式时间内可解的启发式算法.该启发式的值与最优值的比值为2,且证明了该界为紧界.     

退化工件2台机器异序车间作业排序问题

：文章讨论退化工件2台机器异序车间作业排序问题。在异序车间作业环境中,每个工件由一些工序组成,工序的个数未必与机器数相同。此外,每个工件有各自的工序加工顺序。工件可能多次在某些机器上加工,也可能根本不在某些机器上加工。假设工件的实际加工时间是其开始时间的比例函数,目标函数是极小化最大完工时间。首先证明了具有任意工序的问题是强意义下NP-难的;然后对每个工件最多只有2个工序的问题给出了多项式算法;最后证明了只有2个工序具有准备时间或截止工期的问题是普通意义NP-难的。     

加工时间依赖于开工时间的单机排序问题

讨论了加工时间依赖于开工时间的单机排序问题．在这一模型中每个工件具有一个基本加工时间，当工件的开工时间超过某个共同的工期后，工件会有一个时间惩罚．本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论，对某些特殊情况给出了多项式算法.     

一类加工时间与位置有关的单机排序问题

研究一类工件加工时间和位置有关的单机排序问题．在这一问题中。全部工件有一个待定的共同工期d，目标函数是提前时间，延误时间和工期的加权和达到最小，即惩罚函数最小．通过对问题的分析，将其转化为指派问题，从而证明该问题具有多项式算法．并用一个例子作了说明。     

带有线性退化工件和退化维护时间的单机窗口排序

排序问题是一类重要的组合最优化问题,它的深刻的实际背景和广阔的应用前景,引起了广泛的关注。排序问题的一大特点是模型繁多,适用于某一模型的算法,只要将模型的条件稍加变化,该算法就可能不适用。在经典排序问题中,通常假设工件的加工时间是不变的,然而,在许多实际问题中,工件的加工时间受到加工机器设备、工件本身、加工顺序等许多因素的影响而未必是恒定的。文章提出一类新型的排序问题——带有工期窗口和维护时间的线性退化工件的单机排序问题,目标是寻找:1)最优维护的开始时间;2)工期窗口的位置和大小;3)工件的最优排序使得提前完工、误工、工期窗口开始时间和窗口宽度的总费用最小。文章最后给出了这个问题的最优算法,其时间复杂性是O(n2logn)。