基于图卷积网络求解开放车间调度问题的方法

传统的元启发式算法难以有效求解大规模开放车间调度问题(OSSP),为此提出了一种基于图卷积网络GCN求解OSSP的方法。首先,设计了基于GCN的开放车间调度模型,将OSSP的工序节点特征嵌入图中并对其进行多层卷积操作,有效获取了工序节点之间复杂的依赖关系。然后,为了提高求解大规模OSSP的效率和质量,提出了一种基于GCN的开放车间调度算法。实验结果表明,该方法能有效求解不同规模的OSSP实例,与元启发式算法相比,在求解大规模OSSP实例时该方法表现出更优秀的求解质量和效率。

考虑设备预防性维护的开放车间调度问题

依据实际生产车间的运行情况,建立了带设备预防性维护的开放车间调度模型,并设计一种混合遗传禁忌搜索算法来求解该问题。根据问题的特点,设计了混合算法的遗传编码、解码、改进交叉和变异等操作,以及禁忌搜索算法的邻域结构,使算法在集中搜索与分散搜索中达到平衡。所提算法在开放车间调度Taillard基准实例和带预防性维护的开放车间调度案例中的应用验证了其高效性和有效性。

基于仿真的双目标并行机开放车间自适应动态调度

针对工件到达时间与加工时间不确定,且存在紧急工件的并行机开放车间调度问题,以TWC(total weighted completion time)与TWT(total weighted tardiness)为优化目标,设计了一种集成FlexSim仿真模型与NSGA-Ⅱ算法的自适应动态调度方法。该方法以FlexSim模型仿真工件的生成和加工为基础,根据车间实时负荷确定动态调度周期,对紧急工件进行右移重调度,利用NSGA-Ⅱ算法生成双目标优化的调度方案。某晶粒拣选车间生产数据的实验结果表明,相较于利用规则的实时动态调度与固定周期重调度,提出的方法能够在最小化调度偏离度的同时获得满意解。

基于多目标蜉蝣算法的求解云制造环境下柔性开放车间调度问题研究

针对云制造环境下柔性开放车间调度特点,综合考虑企业内云任务和自有任务协同调度、能源消耗和剩余制造资源利用情况,建立以最小化总加权完工时间、最小化总加工能耗成本、最大化机器利用率为优化目标的生产调度模型。基于多目标蜉蝣算法(muti-objectivemayfly algomithm,MMA)设计工序和机器的双层编码方案、种群进化策略,通过仿真实验,验证上述模型和MMA的有效性。

带AGV开放车间调度的析取图模型与求解

随着AGV小车在制造系统的广泛应用,其路线规划与生产调度集成可大大提高生产效率,降低运输能耗。这里以开放车间为研究对象,考虑AGV的物料搬运特性,提出了一种考虑最大完工时间和AGV能耗的双目标析取图模型,剖析问题特征,提取问题的关键弧特性;其次,设计了基于关键弧的多种邻域结构,融合遗传算法的全局搜索能力和变邻域结构的局部探索能力实现问题的寻优。最后,标杆案例测试结果表明,所提出算法可有效解决带AGV开放车间调度问题,多种邻域结构设计显著地提升了算法求解性能。

并行多机开放车间调度问题的模型与算法

发光二极管制造过程中,晶粒分类拣选工序的调度问题是典型的并行多机开放车间调度问题,属于NP-hard问题。研究了该调度问题以最小化总加权完工时间为目标的求解模型与算法。根据问题特性构建了可获得最优解的混合整数规划模型,并设计了同时考虑质量与求解效率的启发式算法和改进粒子群优化算法。仿真结果显示,启发式算法和改进粒子群优化算法都能在合理的时间内迅速有效地获得较佳的调度解。

基于网络流的多并行机可中断开放车间调度算法

为提高开放车间的生产效率,研究了多并行机可中断开放车间调度问题,提出了基于网络流的调度算法。针对车间的特点,建立了以制造期最短为目标的整数规划模型,提出了工件有就绪时间约束时制造期下界的计算方法。采用网络流理论表示机器与工件间的分配关系和时间约束,建立了开放车间的网络流模型,将调度问题转换为最大流问题。引入最小负载优先和最大工作量优先两条启发式规则,设计了基于预流推进的最大流算法,并针对最大流算法中存在的局部优化问题,提出了最大流优化方法,得到机器资源的分配结果。在此基础上,建立了加工时间矩阵及减量集合,求得各机器上工件的加工顺序。使用两组随机数据对算法进行了实验,通过与制造期下界的对比,验证了算法的正确性。

带强制工期的双机开放车间排序问题

讨论了强制工期相等的n个工件在双机开放车间加工。在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小。由于工件不允许延迟,问题可能会无可行排序。先讨论了问题的可行性。如果问题可行,找出一个可行序列作为预排序列,并提出了一个算法计算每个工件尽可能迟的开工时间。而后,提出了一个多项式时间最优算法,在预排序列的基础上,通过调整两台机器上最先加工的工件来获得最优排序。

基于文化基因算法的开放车间调度问题研究

针对开放车间调度问题,运用了文化基因算法进行优化求解。在文化基因算法的框架中,既有种群中的全局搜索,又包含针对问题自身特点的局部搜索,为解决开放车间调度问题提供了一种新的算法。按照文化基因算法的思想和特点,将爬山法作为局部搜索策略加入到全局搜索策略所用到的遗传算法中,通过对开放车间调度问题的邻域结构进行研究,加入爬山搜索法进行优化求解。基于40个标准算例,通过与下界值的比较,验证了所提算法在解决具有较大搜索空间的调度问题时,其拥有更出色的算法性能。

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

开放车间调度问题属于典型的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。

资源布局可变条件下的开放车间柔性制造单元构建技术研究

单元制造是在当今小批量、多品种的生产环境下的提高生产柔性和效率的一种有效手段。在单元制造的基础上,提出了一种融合物理制造单元和逻辑制造单元的柔性单元构建方法,并建立了相应的混合整数规划模型。通过在物理制造单元与逻辑制造单元设计思想之间寻求折衷来提高系统的柔性并减少制造成本。在模型设计中,考虑了制造资源布局、加工路径选择以及加工批量设置问题。以最小化加工成本、加工车间之间和之内的运输成本、跨单元操作成本和机器移动成本为目标,通过将制造资源重新布局在给定的加工地点(加工车间),形成若干敏捷柔性制造单元。数值实验结果表明了的这一设计思路的有效性。

基于多样性增强的自适应遗传算法的开放式车间调度优化

针对开放式车间调度问题,提出了基于多样性增强的自适应遗传算法进行优化求解。设计了多样性判定增强算子、自适应交叉变异算子、多元竞争选择算子等五个算子,以提高遗传算法的进化效率和进化质量;通过分析算法各算子的时间复杂度,发现所提算子并未增加算法复杂度;采用正交试验确定了各算子的最优参数;设计了三组实验,分析了所提算子对算法的影响,结果表明多样性增强算子提高了求解质量,自适应交叉变异算子加快了收敛速度;基于60个标准算例,通过与已有5种算法比较,验证了所提算法的有效性和稳定性。采用100个算例,分析了算例规模对调度性能的影响规律。

基于粒子群优化的开放式车间调度

开放式车间调度(OSP)是重要的调度问题,它在制造领域中的应用非常广泛。优化调度算法是调度理论的重要研究内容。基于人工智能的元启发式算法是解决该问题的常用方法。分析了一种新的元启发式算法——粒子群优化(PSO)在信息共享机制上的缺陷,提出新的基于群体智能的信息共享机制。在该信息共享机制的基础上, 设计新的基于PSO的元启发式调度算法——PSO-OSP。该算法利用问题的邻域知识指导局部搜索,可克服元启发式算法随机性引起的盲目搜索。该算法应用于开放式车间调度问题的标准测试实例。仿真结果显示,PSO-OSP算法在加快收敛速度的同时提高了开放式车间调度解的质量。

一种常见干扰条件下的开放式车间重调度研究

在开放式车间中,针对由机器持续不可用干扰(MUAD)及其引发的工时缩减现象,致力于研究如何有效、及时地实施重调度活动.其中,重调度性能由总完工期来度量,而重调度稳定性则体现在序位偏差与结束时间偏差上.基于右移、受影响工序、全局三种典型的重调度策略分别提出并实现了三种特定的重调度方法(即sRSR,sAOR与sTR_GOS)以响应所关注的干扰条件.在仿真实验中通过模拟大量的重调度情景,考察了原调度生成机制的选取问题并对比了三种方法在相同情景下的各自指标绩效.实验结果显示:当MUAD干扰持续较短时间且以"中断—可续"模式恢复被中断工序时,推荐选用sAOR实施重调度;当MUAD干扰发生在晚期、工时低幅缩减、算例较小且中断模式为"中断—不可续"时,适宜采取sTR_GOS实施重调度.

单一机器干扰下的开放式车间重调度

在开放式车间中面对以单一形式出现的机器不可用干扰,研究了如何高效率、低成本地执行重调度的问题。其中,重调度性能由完工期来衡量;重调度稳定性则体现在工序开始时间偏差和序位偏差上。基于右移、受影响工序和全局重调度三种典型策略,分别提出并实现了三种专门的重调度方法,以修复初始调度或重新生成新可行调度。仿真实验通过模拟大量不同的重调度情景,考察和比较了三种方法在相同情景下的各自指标表现。实验结果统计性地揭示出若干在特定重调度情景下有关重调度方法选取的适用性建议。

急件到达干扰下开放式车间重调度方法

针对开放式车间中突发的急件到达干扰,研究如何有效地执行扰后重新调度任务。基于匹配式调度策略探索扰后实施重调度的具体方法;为了形成四种可行的重调度实施方案,不仅兼顾了面向分离、连续空闲时间的两种重调度时域确定方式,还在约简式调度阶段设计了两种特效的启发式算法。仿真实验模拟了大量急件干扰下的重调度情景,并从完工期、急件的相对完工时间及序位相似性三方面分别设定了重调度绩效指标,进而对四种所提方案进行了同情景独立观测。实验结果显示,急件到达干扰越晚出现,所提重调度方案的整体应对效果越好;此外,通过统计分析不同实施方案所对应的观测结果,得出了若干有关扰后重调度方案选取的适用性建议。

多机器总完成时间和makespan近似最优的开放式车间调度方法

研究了多机器开放式车间调度问题,采用离散事件系统调度使makespan最小化和总完成时间最小.给出了在确定处理机器的条件下,不同批次的作业总完成时间最优的排序定理,以及选择机器处理作业的指标优化定理,利用给出的若干定理建立了总完成时间最优的调度方法.作者利用加权总完成时间最优算法来近似求解makespan最小化和总完成时间最优的调度问题.作者也利用论文的理论结果给出了一个三机器开放式车间情况的实际算例.

无人计量实验室中的车间调度问题优化与仿真

针对北京东方计量测试研究所无人计量实验室中的开放式车间调度问题,提出了一种基于适应度和距离评估标准的离散灰狼优化算法。提出的算法使用适应度和距离评估标准,来选取不同种群的最优领导个体,从而来保持种群的多样性、降低种群早熟风险、提高发现最优解的概率。仿真结果表明,离散灰狼优化算法在求解开放式车间调度问题时有较好的有效性和稳定性。另外,离散灰狼优化算法可以满足无人计量实验室的日常实际计量检测需求。

基于改进遗传算法的充电桩检测调度优化

充电桩作为电动汽车的主要充电设备引起广泛关注。充电桩的安全性和可靠性是促进电动汽车发展的重要因素。在充电桩出厂前对其进行检测非常关键。充电桩检测的项目多,耗时较长。为了提高充电桩检测效率,文章将充电桩检测完成时间最小化设为目标函数,建立一种充电桩检测调度优化模型,同时,为了克服经典遗传算法的局限性,设计了一种基于工序和设备变异的双变异算子,最大限度使种群多样化,进而提出了一种添加初始化因子和精英策略的改进遗传算法。实验结果表明,采用改进遗传算法求解充电桩检测调度优化问题,总检测时间较人工检测降低了33.26%,较经典遗传算法降低了14.84%,提升了充电桩检测效率。

缩短患者候检时间的检查序列优化算法的设计和应用

目的探讨有效缩短患者候检时间累加和的优化算法,充分挖掘医院现有资源的服务能力。方法以门诊患者候检时间累加和为目标函数,建立门诊检查的混合开放车间作业模型。计算各检查部门设备的服务检查负荷,确定瓶颈部门;提出了基于瓶颈部门的半在线优化算法,并在上海交通大学医学院附属第九人民医院的20批门诊患者的候诊过程中进行数据验证。结果通过基于瓶颈的半在线检查项目序列优化算法,20批门诊患者的候诊时间累加和减少了10.5%。结论与患者随机生成检查序列相比,优化算法可以明显缩短患者的候检时间累加和,提高医院现有资源的服务能力。