工件加工时间是开工时间的简单线性函数的Flow Shop调度问题研究

研究工件加工时间是开工时间的简单线性函数的Flow ShoP调度问题。在这类问题中机器间满足某种优势关系。当目标函数是极小化加权完工时间和时．尽管比相应的经典问题复杂，但仍存在多项式时间算法。同时对工件的各工序无等待问题和机器无空闲问题也给出多项式时间算法。     

模糊加工时间调度问题的研究

提出模糊加工时间调度问题,隶属函数建立在工件的模糊加工时间上,隶属度表示工件在一段加工时间下属于完工集合的程度,在假设工件的隶属函数是单调递增的情况下,的多个工件所迭加的联合隶属函数所对应的性质,根据迪些性质研究了一种单机模糊加工时间的调度模型。     

加工时间服从指数分布单机随机调度

讨论加工时间服从指数分布的单机随机调度问题，目标是实现工件完成时间与公共交货期偏差的加权和期望最小化。此问题是JIT（Just-In-Time)生产环境下的典型调度模型。结果表明问题的最优解关于权值与加工时间均值的商具有∧形特征。     

带有交货期窗口模糊加工时间的Flow-shop调度问题

研究了处理时间不确定且具有不同交货期窗口F low-shop的提前/拖期调度问题。采用三角模糊数表示不确定性信息,运用模糊数的加法和取大运算建立了问题的模糊规划模型。通过“Lee-L i”法转化为精确的目标,采用遗传算法寻优。仿真实验验证了算法的有效性。     

柔性Flow shop加权完成时间调度问题的启发式算法

使用单机松弛方法证明了,即使对于柔性F low shop加权完成时间调度问题,基于加权最短处理时间需求的启发式算法也是渐近最优的。     

带机器准备时间的同类机调度问题的启发式算法

研究了带机器准备时间的同类机最大完工时间调度问题, 首先证明了工件互换的四个性质, 进而提出了一种启发式算法, 此算法以LPT算法得到的序列作为初始解, 利用互换性质重复对最大完工时间最大和最大完工时间最小的两台机器上的工件进行交换, 以提高解的质量. 实验结果证明了此算法的有效性.     

敏捷卫星调度的时间约束推理方法

敏捷卫星机动能力的增强带来观测机会的增多和观测时间窗口的增长,具有很大的应用潜能。但管控中由于观测开始时间是一个具有连续值域的变量,传统非敏捷卫星调度问题的组合优化建模方法不再适用。本文介绍了敏捷卫星的时间依赖、可控与不可控事件混合、资源过度受限等特性;给出了时间约束网络概念及敏捷卫星调度中的时间约束推理问题描述;分析时间约束网络与距离图的等价性,借鉴Johnson 算法对稀疏网络的特殊处理,采用重赋权技术,提出针对敏捷卫星调度的改进循环检测算法检查时间约束;建立了分支剪枝搜索算法,以约束规划方式获得时间一致解。最后通过实例验证本文方法的有效性,实验结果表明本文方法能够较好地实现敏捷卫星调度的时间约束的一致性检验和搜索求解。     

调整时间与顺序相关的flowshop调度的精确算法

调整时间与顺序相关的流水车间调度问题（flowshop scheduling with sequence dependent setup times,FSSDST)在过程制造业中有着广泛的应用背景，是一类比较复杂的调度问题，对目标函数是最小化最大流程时间（makespan)的同排列流水车间FSSDST调度问题进行了研究，建立了FSSDST的混合整数线性规划模型（MILP），提出了两种确定原问题的下界方法：（1）按照第m台机器（最后一台机器）定界；（2）按照全部机器定界，根据这两个下界，提出并实现了分支定界算法，为了提高分支定界算法的效率，提出了两种改进上界的策略：（1）改进初始上界法；（2）改进动态上界法，实现了上述所有算法，并通过随机产生的例子获得了各种算法的性能。     

线性加工时间的树约束单机排序问题

研究工件具有线性加工时间、工件间优先约束为树约束的单机排序问题。目标函数为极小化加权完工时间和。在工件加工时间是其开工时间的线性函数的条件下，本文证明了最大家庭树中的工件优先于家庭树中的其它工件的加工，并且其工件连续加工所得到的排序为最优排序。     

树约束线性加工时间的单机排序问题

讨论工件具有线性加工时间,工件间优先约束为树约束的单机排序问题。当目标函数为极小化加权完工时间和时,问题比相应的经典排序问题复杂,在工件间优先约束为出、入树2种情况下,分别给出了该问题最优排序的多项式算法。     

极小化不可行量函数的Flow Shop变异问题

讨论一类Flowshop的变异问题。在这类变异问题中 ,给定一个截止工期 ,该工期比Flowshop最优调度中的最大完工时间小。讨论的问题是在全部工件的完工时间不超过截止工期的限制下 ,极小化不可行量函数。这类问题与矩阵函数因子分解有着密切联系。基于对问题的分析 ,证明了这一问题等价于单机调度中极小化类似的延迟量函数。推广了已有的结论。     

不确定条件下不同交货期窗口的Flow Shop调度

研究了具有不同交货期窗口的Flow Shop的提前／拖期调度问题，并考虑了处理时间的不确定性。采用三角模糊数表示不确定性信息，引入两种模糊运算，建立了问题的模糊规划模型，并采用“中间值最大隶属度”的算法将模糊规划模型转化为清晰的非线性规划模型。针对清晰的数学模型提出了基于遗传算法的优化方法，最小化对所有工件提前／拖期惩罚。最后，大量仿真实验验证了算法的有效性。     

解决中间存储时间受限的间歇式调度问题的算法

生产调度问题是企业生产过程中的重要组成部分,合理、有效的调度方案尤其对提高间歇过程的生产效率和经济效益具有重要的意义.针对中间存储时间受限的间歇式调度问题,考虑了它本身具有的特殊性,提出了不同的约束条件,建立了相应的数学模型,并且结合基于生物免疫体系理论的智能方法———免疫算法的特点,提出了解决此类问题的免疫调度算法.通过仿真试验,表明了模型的有效性和算法的可行性.     

具有跨工位操作的汽车总装车间调度仿真问题

研究了一类从汽车总装车间作业中提炼出的新的流水车间调度问题.该问题具有跨工位操作、停线操作以及加工时间波动的特点,这些特点使得调度问题变得相当复杂.首先,建立了该调度问题的数学模型;然后,针对此模型以最小化最大完工时间为目标,采用遗传算法和模拟退火算法相结合的方法确定出最佳调度方案;最后通过二维的动画仿真对调度结果进行验证与分析.利用北京某汽车企业总装车间实际生产数据测试和分析了上述方法,结果表明了该方法的有效性.     

具有优势机器和恶化工件的流水作业排序问题

针对流水作业排序问题,建立了具有优势机器和恶化工件并且有无空闲限制的排序模型.在该排序模型中,机器加工工件时,工件的相邻加工工序之间不允许出现空闲,工件的加工时间是其开工时间的严格增加线性函数.其中讨论的优势机器有2种情况:机器形成增减增优势关系和机器形成减增减优势关系.考虑了多台机器的流水作业排序问题,其中,目标函数分别为极小化最大完工时间和极小化总完工时间,对于这两类问题分别给出了求解最优排序的多项式算法和它们的计算复杂性,并通过证明证实了算法的有效性.     

多目标Flow Shop调度问题的改进TA求解算法

提出一种根据搜索进展自适应设定门槛值和邻域搜索次数的改进TA算法．对无优先级双目标FlowShop问题进行求解,并与现有启发式算法进行了比较．计算比较结果表明：所提算法可以求得稳定、高质量的解．     

考虑区间工时的多目标柔性作业车间节能调度

在综合考虑经济指标和环境因素基础上,研究了工件加工时间不确定的多目标柔性作业车间节能调度问题。将工件不确定加工时间描述为区间数,并以最小化最大区间完工时间、区间总能耗为目标构建区间柔性作业车间调度节能问题优化模型。同时,依据区间可能度的支配关系,设计了一种有效求解该问题的区间多目标进化算法。通过15组测试问题,分别对区间多目标进化算法、SPEA-II及NSGA-II进行仿真实验,并采用反转世代距离(inverse generation distance, IGD)和覆盖集测度(C测度)两种性能指标验证了所提算法的可行性和有效性。     

折扣加权总完工时间的调整时间可分离无等待Flow Shop排序问题

研究3台机器调整时间可分离的无等待F1ow Shop排序问题，目标函数为极小化折扣加权总完工时间。对某些特殊情况，给出问题存在多项式最优算法的充分条件。在此条件下得到求解调整时间可分离的无等待F1ow Shop排序问题的分派规则。