具有等间隔工期的2台机器流水作业调度问题的强NP难性

考虑3个具有等间隔工期的双机流水作业调度问题,其中按照调度方案中工件的加工顺序给每个工期分配工件,且2个连续工期之间的间隔长度相同,目标分别为最小化最大延误、总延误和总误工工件数。证明了此三问题均为强NP-难的。此外,结果表明,如果P≠NP,那么这些问题没有伪多项式时间算法和完全多项式时间近似方案(FPTAS)。

基于灰数描述的不确定工时作业车间E/T调度优化

针对不确定加工时间的作业车间调度问题,考虑每个工件的交货期窗口,旨在最小化工件提前/拖期成本和机器空闲成本。分别采用基本遗传算法和混合遗传算法进行求解,并比较两种算法的求解质量。通过灰色理论和模糊数理论对不确定加工时间分别建立调度模型,分析两种模型的优化程度和稳定性。结果表明,与基本遗传算法相比,引入按指定邻域结构进行局部搜索的混合遗传算法具有更好收敛能力;与模糊数方式相比,采用灰色理论能够更好地描述不确定加工时间,且在求解过程中也具有更好的适应性和稳定性。

一类新的单机工期指派模糊调度算法研究

研究了单机模糊环境下,如何安排工件加工顺序和指定工件工期,使得提前完工和拖期完工惩罚总费用均值最小的工期指派调度优化问题。在该类调度问题中,工件的加工时间为非对称三角模糊数;总费用的均值用模糊数的加权可能性均值来计算。针对一类权函数族,给出了该类权函数族下的工件最优工期的计算方法,基于该最优工期,给出了排序的最优调度算法,并证明了该类工期设定问题是多项式可解的。数值实验中针对工件完工时间服从不同的非对称分布的情形,与现有的方法比较,结果表明给出的方法能更有效的降低费用。

具有位置相关权重的工期分配排序问题研究

针对具有位置相关权重的工期分配排序问题进行了研究,其目标是在共同工期分配/松弛工期分配两种模式下,找到最优的工件加工序列以极小化工件工期与工件延误的线性加权和,其中权重是与位置相关的权重。通过证明一系列性质得到工期的计算方法,进而将所要研究的两类工期分配问题转换为与工件加工时间有关的函数。根据每个工件对应的系数来给出具体求解算法从而得到最优的工件序列,以及对应的最优共同工期/最优松弛工期。通过具体的算例验证了此算法可在多项式时间内求解。

考虑可配送时间和柔性时间期限的电动车路径问题

随着低碳绿色、节能环保的经济发展理念越来越受到重视,电动车逐渐成为物流配送的主要运输工具,且物流配送服务的灵活性也越来越受到重视。在传统的车辆路径问题中,通常假设客户需要在指定的时间窗口内接收货物,如果未能按时送达,则会被视为违约,造成客户满意度下降。然而,在实际应用中,大部分客户接受在截止日期后一定时间内延迟接收货物,但这种灵活性通常伴随着额外的成本。针对货物具有可配送时间和柔性时间期限的情况,研究了考虑可配送时间和柔性时间期限的电动车车辆路径问题。构建了以车辆数量、行驶成本和违反时间期限的惩罚成本最小化为目标的混合整数规划模型,设计了改进的自适应大邻域搜索算法对其求解,基于问题特性设计了高效的破坏算子和修复算子以扩大解的搜索空间、运用自适应策略选择高效的搜索算子以及引入模拟退火新解接受策略避免陷入局部最优。通过对随机生成的算例进行计算验证了模型和算法的有效性,并分析了是否考虑柔性时间期限约束及不同的违反时间期限惩罚系数对总成本的影响,本研究为物流配送企业电动车车辆路径规划提供参考依据。

以瓶颈为中心多层次负荷集成的订单交货期预测方法

针对MTO(make-to-order)生产环境下的订单交货期预测问题,提出了一种集成订单接收、订单投放与车间调度等多层次负荷,以瓶颈为中心的订单交货期预测(bottleneck driven due-date forecasting, BDDF)方法。该方法先根据订单是否通过瓶颈,分类估计“鼓链”与“非鼓链”订单在不同层次的负荷,同时利用Little’s法则估计各个层次的通过时间,求和得到订单的交货期。运用FlexSim建模仿真比较了BDDF方法与两种经典交货期预测方法在不同订单池排序规则、车间调度规则以及保护产能水平组合下的系统绩效。结果表明,BDDF方法在拖期率、平均拖期以及延期标准差指标上均优于两种经典方法。同时,订单池排序规则、调度规则以及保护产能水平都会影响BDDF方法的系统绩效,需要根据实际情况选择合适的参数,以更好地控制订单交货期,避免订单延期。

一种新调度类型及其在作业车间调度中的应用

研究改进遗传算法解决作业车间调度问题,问题染色体的编码采用基于工序的编码。针对传统的调度类型的局限性,提出全主动调度及其基于工序编码的产生机制。为了克服传统遗传算法求解调度问题易于早熟收敛的缺点,设计基于优先工序交叉(Precedence operation crossover,POX)和改进子代产生模式的遗传算法。用改进的遗传算法求解传统调度问题、交货期调度问题和提前/拖期(Earliness/Tardiness,E/T)调度问题,研究半主动、主动和全主动三种不同的调度解码机制对遗传算法提供解质量的影响。

一种新型的单件小批量生产车间调度方法

提出了解决具有开完工限制的约束Job -shop生产调度问题的一种新方法 ,该方法将粗细排算法有机结合起来 ,在粗排算法中 ,系统优先安排机床虚拟工序队列集合中剩余加工时间最大的工序 ,得到一个初始可行方案 ,该方案使工件在系统中的流通时间最短。细排算法以粗排算法所得方案为基础 ,以工件的提前 /拖期时间最大的工艺块为调整目标 ,通过交换工艺块中相邻工序位置的调整策略 ,得到一个优化的生产作业计划。经分析实例验证 ,该算法易于实现 ,具有一定的优度 ,并且在工程中是可行的。

基于车间实时状态的订单完工周期预测方法

提出了一种针对多制造资源、多产品类型、离散生产系统中订单完工期的经验回归预测方法。先确定并量化描述影响订单完工期的两类主要因素,即车间实时状态和订单构成信息,基于ExSpect平台构建车间生产过程的高级Petri网仿真模型,通过随机模拟和仿真运行收集样本数据,训练出若干个体神经网络;然后采用基于误差聚类的改进Bagging方法建立神经网络集成预测模型;最后通过实例讨论了订单完工期预测的完整过程。结果表明,采用该方法能得到理想的预测结果。

同时具有学习和恶化效应的不同工期指派问题研究

讨论工件同时具有学习和恶化效应的单机排序模型,其中工件的实际加工时间是其基本加工时间、开工时间和所排位置的函数,每个工件都有自己的工期。目标是确定工件的加工顺序和工期,使工件的提前成本、延迟成本和工期的机会成本的加权和最小。证明此问题在工件引入学习和恶化效应后,依然多项式时间可解,同时给出了求解算法和实例来说明如何最优的求解这个问题。

随机环境下的模具项目交货期预测方法

针对模具制造项目由不确定性因素导致的交货期难以预测的问题,分析了模具生产过程中的几种主要随机因素,并提出多模式的概念。结合车间动态负荷控制的理念,建立了在制项目的交货期随机预测模型。在该模型的基础上,通过融入多模式资源受限项目调度优先规则,对在制项目进行演化,得到项目交货期数学分布,同时用动态规划求解最优策略集,以使项目群拖期惩罚最小。在演化计算过程中,为有效减少计算负荷,采用马氏链粗演化及屏蔽低概率状态的方法缩小系统状态空间。开发了一个项目管理模块,成功地对一个项目群进行演化,获得了项目交货期概率分布及最佳策略,结果表明了该预测模型的实用性。

可变机器约束的模糊作业车间调度问题研究

在车间实际加工中,工件的加工时间和交货期是一个模糊数,而且工件的某道工序有多台机器可供选择。针对这类作业的车间调度,提出了以极大化最小客户满意度为指标的可变机器约束的模糊作业车间调度模型,并给出了算法设计。应用遗传算法在适应度函数处理中引入模糊数处理方法,解决作业车间模糊调度问题,实现调度优化。仿真实验结果表明了该调度方法的有效性,为可变机器约束的模糊作业车间调度提供了一种实现途径。

神经网络集成方法在产品完工期预测中的应用

针对单个神经网络模型易出现过拟合而导致泛化能力较弱的缺点,引入了神经网络集成方法,对传统的Bagging方法进行改进,提出了一种基于0.632误差聚类的Bagging方法。通过实验对比和假设检验,证实了该方法的优越性,并探讨了最佳聚类数目。最后,通过应用实例展示了利用集成神经网络进行产品完工期预测的全过程。实验结果显示,该方法明显地提高了预测精度。

基于能力验证的模具交货期可行性分析方法

针对模具企业在订单洽谈阶段难以确定交货期可行性这一实际问题,建立了基于能力验证方法的交货期可行性验证模型。首先在新模项目关键路径的关键工序中,构建了资源范畴这一能力验证对象,并给出了能力需求和已有负荷的计算方法,然后建立了关键负荷指数这一资源负荷评价指标。基于上述理论基础,构造了启发式算法,并通过算例说明了算法的实用性。最后,针对算法中涉及的接收概率具有不确定性的问题进行了敏感度分析。

带交货期的工件族生产与配送的排序问题

本文考虑了多个客户订购不同种类的工件,工件生产完后需要运输到客户的单机供应链排序问题。由于工件属于不同的种类,在加工不同种类工件前要有一个准备时间。每个客户分布在不同位置,客户的每个工件都有一个交货期,工件是分批配送的,每一批配送需要花费一定的时间及费用。考虑了两个与交货期有关的目标函数,分别给出了它们的最优算法。

模糊作业车间调度中的提前/拖期问题的研究

首先介绍了现实作业车间调度中的模糊加工时间和模糊交货期问题,并阐述了模糊理论中有符号距离、区间数距离等相关概念;然后给出了以遗传算法为框架的基于有符号距离和区间数距离的作业车间调度模型以解决调度中的提前/拖期惩罚问题,并且通过实例验证了模型的可行性和有效性.

求解模糊资源受限项目调度问题的遗传算法

本文研究了以排序健壮性最大为优化目标的具有模糊加工时间和模糊交货期的资源受限项目调度问题,采用六点模糊数表示模糊加工时间和模糊交货期,引入了2种模糊数的弱比较方法,即重心距离法和积分值法.针对这一优化问题设计了一种基于任务链表编码形式的遗传算法.数值实验结果表明该算法优于文献中的相关算法,同时实验结果也表明基于2种模糊数的弱比较方法对算法性能影响较弱.

基于遗传算法的作业车间模糊调度问题的研究

在研究作业车间模糊调度问题的基础上 ,建立了两种作业车间模糊调度模型。对于只考虑模糊加工时间的问题 ,以最小完工时间作为优化目标 ;对于同时考虑模糊加工时间和模糊交货期的问题 ,以平均满意度最大作为优化目标。模糊加工时间用三角模糊数和梯形模糊数来表示 ,模糊交货期用梯形模糊数和六点模糊数来表示 ,给出了两种模糊数比较方法。应用遗传算法来求解最优调度顺序 ,并对遗传算法编码、初始种群的产生办法、解码、交叉及变异方法等方面做了研究。最后 ,给出了仿真实验结果和结论。

基于货物运到期限的列车运行线选择优化研究

采用规划型运输组织模式,根据货运市场动态需求,基于实施日进行铁路货物列车运行图编制是提高铁路货物运输时效性、实现铁路货运改革创新的关键。实现流线结合,对于动态的车流合理选择运行线进行挂运,即将车流指派到运行线对应的列车上,是确定货物运输方案的核心工作。确定的运行线不同,货物运输时间则不同,基于此,可为货主提供多种运到期限选择方案。以车流在途运输时间最小为优化目标,以货物列车运输能力、技术站有调中转作业时间等为约束条件,构建基于货物运到期限的列车运行线选择0-1整数规划模型;模型采用模拟退火算法求解,并提出了运行线选择的k短路算法;最后通过算例分析,验证了模型及算法的有效性。

基于知识进化粒子群算法的模糊交货期流水车间调度问题

针对模糊交货期的流水车间调度问题的特点,提出采用知识进化算法和粒子群优化的混合算法来求解问题。该算法首先在多个群体空间内采用粒子群优化寻找局部最优解,然后利用知识进化算法的猜测操作和反驳操作建立以群体空间知识为基础的一个知识空间,最后通过知识空间的协同进化更新其中的社会知识,从而形成问题的最优解。通过采用所提算法对带模糊交货期的流水车间调度问题的实例进行测试,并比对遗传算法和粒子群优化算法,表明了混合算法的可行性和有效性。