具有恶化效应与可控加工时间的工期指派排序问题研究

研究工件同时具有恶化效应与可控加工时间的单机排序问题,其中工件的加工时间与其开工时间和所用资源都有关系。在共同工期和松弛工期指派方法下,目标是确定工件的最优排序、最优资源分配和共同工期(松弛工期)使所有工件的排序费用(包括提前时间、延误时间、共同工期(松弛工期))和资源的消耗费用的线性加权和最小。对此问题给出了一些性质,并证明了此问题可以多项式时间内解决。

加工能力受扰的可控排序干扰管理

在加工时间可控的单机排序中,面对随机发生的干扰事件,研究了初始加工时间表的制定问题。对于干扰事件造成的影响采用匹配时间排序的应对策略,在干扰事件发生后,通过压缩工件加工时间,使新时间表在某时间点后完全恢复到初始加工时间表。基于工件吸收干扰事件影响的能力,设计复合排序规则来决定工件的优先级。由于问题内在的复杂性,在复合排序规则中,应用遗传算法来确定某给定待处理工件集的最优参数。使用概率分布表示干扰事件的发生时刻和持续时间,并综合概率信息和工件的优先级来制定初始加工时间表。最后,通过随机数值试验模拟,发现本文设计的初始时间表优于根据最短加工时间优先规则制定的初始时间表,验证了方法对于处理干扰事件影响的有效性。

一种求解加工时间离散可控作业车间调度问题的混合算法

加工时间离散可控作业车间调度问题(Job-shop scheduling problem with discretely controllable processing times,JSP-DCPT)是经典作业车间调度问题(Job-shop scheduling problem,JSP)的一类扩展问题。为避免通过多项式时间近似方法求解JSP-DCPT的近似问题,提出一种混合算法直接求解JSP-DCPT。该算法基于分解方法,嵌套一种禁忌搜索模拟退火混合算法TSSA和一种快速精英保留非支配排序遗传算法NSGA-II,以分别高效求解JSP-DCPT分解所得的JSP子问题和离散时间—成本权衡子问题。基于JSP标准算例FT06,FT10和FT20构造3个不同问题规模的测试算例,试验仿真结果表明,混合算法能够得到收敛的帕累托边界。

加工时间可控的多主体调度问题

为了解决加工时间可控条件下的并行机调度问题,设计了一种基于重复叫价组合拍卖的多主体调度机制。该机制将组合拍卖的一般形式与机器调度的建模技术相结合,将可控加工时间引入竞胜标模型,使生产资源得到更加有效的配置;在价格更新方法上,设计了一种基于次梯度的自适应价格更新机制,提高了拍卖的收敛速度。对该机制进行了仿真实验。结果表明,与传统的"刚性"加工时间的调度模型相比,该机制在提高资源拥有者收益的同时,使生产资源得到了更加充分的利用。

面向加工时间可控的柔性作业车间节能调度问题建模

针对制造车间能量利用率较低、节能潜力巨大的现状,以最小化车间总能耗和最大完工时间为目标,研究了考虑关机/重启节能策略和加工时间可控的柔性作业车间调度问题(FJSP)。首先,对考虑关机/重启节能策略和加工时间可控FJSP车间能耗进行了分析与建模;然后,根据加工时间可控FJSP特性,分别基于空闲时间与空闲能耗的建模思想,提出两个考虑关机/重启节能策略的混合整数线性规划(MILP)模型;最后,使用CPLEX求解器对20组测试实例进行求解,分别从尺寸复杂度与计算复杂度两方面对所提出的两个MILP进行对比评估。实验结果表明,所提出的两个MILP模型都是有效的,基于空闲能耗的MILP模型效果好于基于空闲时间的MILP模型。基于ε-约束法,将最大完工时间目标转换为约束条件,获得了问题的Pareto解,并进一步对所求解甘特图进行分析,挖掘了节能规则。

加工时间可控单机加权总完工时间Pareto优化研究

针对单机环境最优化加权总完工时间问题,当工件加工时间可通过分配资源进行压缩时,研究对工件的加工次序和时间压缩量的优化,从而权衡调度性能目标和资源成本目标。调度性能目标为压缩后工件的加权总完工时间,资源成本目标为工件压缩量的线性函数。此问题复杂性已被证明为NP-hard,为弥补较少有研究从Pareto优化角度求解该问题有效前沿的不足,针对经典NSGA-II求解时易早熟收敛的特点,采用算法混合方式进行优化方法研究。融合归档式多目标模拟退火算法跳出局部极值的优势,启用外部存档策略提升种群的多样性,采用主从模式的并行结构提升求解效率。最后为检验优化方法的有效性,一方面通过对Benchmark测试函数ZDT1-6的求解,表明混合算法对不同结构和形状目标函数兼具普适性和有效性;另一方面结合问题特点设计有效编码方式,针对随机生成算例进行求解。通过分析有效前沿收敛性和多样性,验证了所提方法对于优化加工时间可控单机加权总完工时间问题的有效性。

加工时间可可控控的炼钢调调度度问题两阶段模型及优化算法

炼钢–精炼–连铸是钢铁产品的关键生产工序,其有效的调度对生产过程中减少热能消耗、提高生产效率具有重要意义.根据生产过程中工序加工时间可控性和主要工艺约束提出了分散搜索(scatter search,SS)算法和数学规划相结合的两阶段求解算法.第1阶段应用SS算法基于各阶段正常的加工时间,确定炼钢–精炼生产阶段各设备的加工炉次集和各炉次的加工顺序.第2阶段将SS求得的解转化为时间约束网络图,建立了以炉次等待设备时间和设备等待炉次时间及最大完成时间最小为调度目标,工序加工时间可控的混合整数规划模型,应用CPLEX求解模型确定各炉次的加工时间和开始时间.基于国内某钢铁企业炼钢–精炼–连铸生产过程的实绩生成了14个不同规模的测试案例,对钢厂生产实绩效果与本文两阶段求解算法的优化效果进行了对比,分析了不同等待时间权重对两阶段算法性能的影响,并与采用遗传局域搜索(genetic local search,GLS)算法与数学规划相结合的求解算法的优化效果进行了比较.实验结果表明本文给出的模型和两阶段求解算法对加工时间可控的炼钢–精炼–连铸调度问题的优化效果很好.

加工时间随机可控Job Shop前摄调度研究

针对Job Shop环境中工序加工时间的不确定性,建立加工时间随机可控Job Shop调度问题随机模型。采用效率指标和鲁棒性指标对调度方案进行双目标评价。提出一种分层求解策略实现双目标优化,并采用嵌入最优计算量分配策略的遗传算法求解模型。仿真实验证明了所提出模型及优化算法的可行性。通过与直接采用均值-方差模型进行双目标优化得到的结果进行比较,证明了所提出的分层求解策略和算法可以获得综合性能更好的调度方案。

凸二次规划松弛方法研究离散加工时间可控排序问题

离散加工时间可控的排序问题,得到界为3/2的多项式时间近似算法。

带有交货期窗口和加工时间可控的排序问题

讨论了带有交货期窗口和加工时间可控的单机排序问题。工件的加工时间是关于分配资源量的凸函数模型。工件若在交货期窗口前完工,则产生提前费用;若在交货期窗口后完工,则产生延误费用。分别研究了多窗口问题和单窗口问题。目标是在关于提前、延误、交货期窗口开始时间、交货期窗口大小和最大完工时间的函数约束条件下,确定工件的最优加工顺序、最优加工时间、极小化资源费用函数。通过将2个问题分别转化为指派问题,证明了2个问题是多项式时间可解的,问题的计算复杂性是O(n3)。

带有学习效应和加工时间可控的排序问题

考虑了带有学习效应和加工时间可控的交货期窗口的单机排序问题。工件的加工时间是关于所分配资源的线性函数或凸函数。其中每一个工件均有一个交货期窗口且窗口大小相同,若工件在窗口之前或之后完工则会产生相应的惩罚,若工件在窗口中完工则无惩罚,目标是通过极小化包括提前,误工工件数、窗口的开始时间、窗口大小和资源消耗的总惩罚函数确定工件的最优排序、最优加工时间和最优资源分配量。在加工时间是线性资源函数的情况下,通过将问题转化为一系列指派问题,构造一个多项式时间算法;在加工时间是凸资源函数的情况下,构造了一个在多项式时间内可解的动态规划算法。

带有学习效应的加工时间可控退化工件单机排序问题

讨论了带有学习效应、加工时间可控的退化工件的单机排序问题。工件的实际加工时间是一个关于所排位置、开始加工时间和所分配资源的函数。加工时间可控是指工件的实际加工时间是一个依赖资源分配量的函数。目标是确定工件的最优排序、最优加工时间和最优资源分配量、极小化最大完工时间、总完工时间、完工时间差和资源消耗的总费用。考虑了2种情形:学习因子与工件有关的线性资源函数;将学习效应与工件的实际加工时间、依赖开始时间结合在一起的凸资源函数。通过分析最优解的一些重要性质,将这2个问题分别转化为指派问题,给出了2个计算复杂性为O(n3)的最优算法,证明了该问题是多项式时间可解的。

多目标混合进化算法求解加工时间可控的开放车间调度问题

开放车间调度问题属于典型的NP-hard问题。目前的相关研究大多假设工序在机器上具有固定的加工时间。然而,在大多数现实生产场景中,机床的加工时间可以通过调节加工功率加以控制。同时优化完工时间和总能耗两个冲突目标对高效、节能的开放车间生产具有重要意义。为此,研究了可控加工时间的多目标开放车间调度问题(MOOSPCPT),以最小化完工时间和总额外能耗为目标构建了混合整数规划模型,并提出一种多目标混合进化算法(MOHEA)用于求解MOOSPCPT。在MOHEA中提出多个策略:(1)改进生物地理学优化算法中的迁移策略和变异策略用于全局搜索,有效地提高了种群的多样性;(2)基于关键路径设计一种自调整变邻域搜索策略,增强了算法的局部搜索能力;(3)设计了一种加工时间重置算子,从而显著提升了算法的搜索效率。仿真实验结果表明:所提出的策略有效地提升了算法性能;相较于NSGA-Ⅱ(Non-dominated Sorting Genetic AlgorithmⅡ)、NSGA-Ⅲ(Non-dominated Sorting Genetic Algorithm Ⅲ)和SPEA2(Strength Pareto Evolutionary Algorithm 2),MOHEA能够更有效地解决MOOSPCPT。

具有学习效应和加工时间可控的平行机排序问题

本文研究了一类不相关平行机的排序问题,在该问题中工件的加工时间既具有学习效应,又资源可控,也就是说在该问题模型中,工件的实际加工时间为其正常的加工时间、加工过程中工件所处位置以及加工时间可控这些变量的函数。该研究的目的是为使得总机器负载和总的控制费用的加权和最小以及总的完工时间和总的控制费用的加权和最小。文章通过对问题的相关性质的分析和证明找到了一个解决问题的最优化算法,并且也证明了在处理机的数量给定的条件下,该问题的时间复杂性为O(n^(m+2)),最后也给出了相应的数值例子来阐述该问题。

基于启发式遗传算法求解加工时间可控单台机器

对NP—Hard的加工时间可控单机排序问题提出一种启发式遗传算法求解其次优解。在介绍该问题数学模型后，利用二维编码描述加工次序与加工时间，染色体的第一行用整数编码来表示工件加工次序，染色体第二行用实数编码表示实际加工时间。根据启发式知识定义了新的交叉与变异操作，这样不仅容易产生优良的初始解，而且缩小了搜索范围，提高了搜索速度和精度。算例仿真研究验证了提出算法的有效性。

考虑工件恶化效应和加工时间可控的装配作业车间调度问题研究

针对AJSP,同时考虑工件恶化效应及加工时间可控对车间调度性能的影响,以优化车间内工件最大完工时间为目标,提出一种HGA进行求解。根据问题的特点,分别对各遗传算子进行了有针对性的设计。此外,还嵌入了一种VNS算法,用于增强算法搜索能力。最后,大量仿真实验结果验证了算法的有效性。

带有退化维修和交货期窗口的加工时间分别可控的单机排序问题

本文讨论了带有退化维修和交货期窗口的加工时间分别可控的单机排序问题。每个工件有多个可能的加工时间,不同的加工时间会产生不同的费用。为了提高机器的生产效率,进行一次退化维修。考虑了两个不同的问题:所有工件有一个共同的交货期窗口;每个工件有属于自己的交货期窗口。目标是确定最优的工件加工顺序、维修活动位置、交货期窗口位置以及极小化总费用函数,给出了多项式时间算法,证明了该问题是多项式时间可解。

加工时间可控的单台机器排序问题研究及应用

针对算法复杂度很高的加工时间可控单机排序问题,提出一种基于二维遗传算法求解其次优解的方法。在介绍这一问题的数学模型后,利用二维编码描述加工次序与加工时间,染色体的第一行用整数编码来表示工件加工次序,染色体第二行用实数编码来表示实际加工时间。根据问题特点定义了新的遗传操作,这样不仅容易产生优良的初始解,而且缩小了搜索范围,提高了搜索速度和精度。算例仿真研究验证了所提出算法的有效性。

1/r,p_j≡1/L_(max)在应交工时间可控时有效点集的求解

对应交工时间可控时的排序问题１／ｒ，ｐｊ≡１／Ｌｍａｘ，以Ｆ１表示Ｌｍａｘ，Ｆ２表示应交工时间滞后和，Ｆ１、Ｆ２同时极小化。