运输能力有限混合流水车间调度的改进拉格朗日松弛算法

为改善在制品库存和能耗问题,研究了从钢铁实际生产环境提炼出的运输能力有限的动态混合流水车间调度问题.将运输机视为虚拟机器,可将原问题转换成与其等价的不考虑运输能力但在偶数阶段机器有不可用时间段的动态混合流水车间调度问题,其中机器不可用时间段取决于其运送的工件.对转换后的问题建立数学模型,提出基于阶段分解的拉格朗日松弛算法进行求解,该算法将优先级约束松弛到目标函数中,将拉格朗日松弛问题分解为多个阶段级子问题,进而设计了动态规划求解这些带任意权重和机器不可用时间段的并行同构机调度子问题.对不同问题规模的测试结果表明,所提算法能够在较短的运行时间内获得满意的近优解.     

多目标混合流水车间机器故障重调度问题研究

在数字化转型过程中,如何解决好生产调度问题是研究者关注的问题。混合流水车间机器故障是在生产调度过程中常遇到的问题。为此,需要为快速解决机器故障的重调度问题找到方法。在解决机器故障重调度过程中,主要考虑的因素为加工时间不能确定、物流装卸时间以及生产设备布局限制,从而提出这种多种重调度组合的重调度方法。首先建立双目标数学模型,系统中植入NSGA-II算法求解初始调度方案,算法采用启发式规则和随机化的方式生成初始解,利用仿真的方法对调度方案进行评价。其次,将多种重调度方式融合在一起,通过设备故障仿真验证重调度方法,试验验证启发式规则作为初始解的一部分,可以非常好地提高算法的搜索效率,所研究的重调度方法能够有效解决混合流水车间机器故障问题,具有重要的意义。     

常规混合流水车间调度问题的等价变换

常规混合流水车间调度问题具有多阶段、同速平行机、总完工时间最小化等特征,它是研究混合流水车间调度问题最为自然的起点。对于此类NP难问题的基本性质的研究还不够充分,其算法设计缺乏系统的理论知识指导。因此,针对常规混合流水车间调度问题的性质展开研究,探讨了调度问题的可逆性特征,并在此基础上分析了基于逆序变换进行问题求解的可行性,为算法设计提供了理论依据。     

具有随机加工时间和机器故障的流水车间调度

不同的流水车间往往具有不同的生产方式,为提高调度方案对不同生产方式下随机因素的处理能力,重点考虑了2种生产方式下3种不同情况的随机调度。针对这3种情况,以最小化最大完工时间为目标,研究了具有随机加工时间和随机机器故障的置换流水车间调度问题,提出了处理不同生产方式下随机因素的3种计算方法,通过预测机器的期望故障时刻来计算每个任务的完工时间。采用启发式规则和遗传算法相结合的方法,确定出最佳调度方案,并进行了实验分析和比较。     

带多处理器任务的动态混合流水车间调度问题

研究了具有多处理器任务的混合流水车间调度问题,且考虑相邻两阶段之间的运输时间、机器故障和工件动态到达的实际生产特征。由于该问题不但求解非常复杂,对它的不同部分的简化还会使其变成其他不同的典型调度问题,探讨该类问题的近似解法具有挑战性和广义性。据此分别采用结合次梯度算法的拉格朗日松弛算法、结合次梯度和bundle算法的交替算法（交替S＆B算法）的拉格朗日松驰算法进行求解。对多达100个工件的问题进行测试,结果表明,所设计的算法能够在合理的CPU时间内产生较好的时间表。     

基于GEP-DES的柔性流水车间机器与AGV集成实时调度方法

智能制造背景下，考虑机器与AGV集成实时调度对整个生产系统效率提高具有重要的意义。针对工件动态到达、加工时间存在波动的情况，提出一种将基因表达式编程算法与离散事件仿真(GEP-DES)相结合的实时调度方法以解决基于最小化最大完工时间为目标的机器与AGV集成调度模型。该方法在离线阶段设计三段式编码的GEP算法以描述机器与AGV集成运作过程，借助DES过程获取目标函数值以对GEP指标性能进行评估，最终挖掘出高质量的调度规则。挖掘出的调度规则与在线阶段车间实时工况信息交互以实现机器与AGV集成的实时调度。最后，将所提方法与传统调度规则方法进行对比，实验结果验证了所提方法的有效性与优越性。研究成果为快速响应柔性流水车间生产中的机器与AGV集成实时调度提供了方法支持。     

柔性流水车间调度模型与混合引力算法

针对柔性流水车间调度问题,利用机器特定事件点来描述工件的机器选择,再以最小化最大完工为目标,考虑工艺约束和时间约束构建了柔性流水车间调度的混合整数线性规划模型,用GAMS/Cplex找到小规模问题的全局最优解。为快速求解大规模问题的近优解,提出了结合瓶颈启发式的引力搜索算法,利用瓶颈移动技术和John Son方法的解码机制,寻找最小化最大完工时间的最优调度方案。实验结果表明,所提出的模型及算法能高效地求解以最小化最大完工时间为目标的柔性流水车间调度问题。     

柔性流水车间调度问题综述

智能制造是我国工厂发展的必然趋势,而流水车间在提高工厂生产效率方面起到至关重要的作用。柔性流水车间作为流水车间的扩展,在多道工序上增加多台并行机器,提高了车间的生产效率和灵活性,是目前大量学者关注的热点问题。根据不同的特征和性质对柔性流水车间调度问题进行系统性介绍;从总体上阐述了传统柔性流水车间和扩展柔性流水车间的相关研究,并按照问题的优化目标数量来进行分类描述;最后根据研究现状和当前行业发展需要提出了若干未来研究方向。     

一类已知概率分布下的混合车间鲁棒调度问题研究

为解决一类产品生产需经上游作业车间的零部件加工和下游流水车间的零部件总装的调度问题,在研究生产调度文献的基础上,给出了混合车间调度问题;给出一类已知概率分布下的混合车间鲁棒调度方法,并建立鲁棒调度模型;采用遗传算法求解鲁棒调度模型。最后进行了实证研究,证明所建模型以及遗传算法在求解混合车间调度问题上是有效的。     

等待时间受限的HFSP及其拉格朗日松弛算法

等待时间受限的混合流水车间调度问题(HFSP)广泛存在于钢铁生产,玻璃加工和塑料等行业。目前,关于等待时间受限的HFSP的研究较少。首先建立了等待时间受限的混合流水车间调度问题模型,然后设计了基于工件分解策略的拉格朗日松弛算法来进行求解。该算法通过将机器容量约束松弛到目标函数中,将得到的松弛问题进而分解为一系列易于求解的工件级子问题来进行求解。最后对设计的算法进行仿真验证,测试结果表明所设计的拉格朗日松弛算法能够在较短的时间内产生较好的近优解。     

制造系统通用作业计划与蚁群算法优化

分析了基本作业方式的“通用-特例”关系,提出了全面研究上述基本作业方式的通用作业计划的概念,建立了通用作业计划非连接图模型及基于蚁群算法的优化方法。算例研究假定一制造系统包含开放作业、异顺序作业、混杂流水作业三种作业方式,将其按照通用作业计划方式采用蚁群算法进行优化,所得的近优加工流程时间显著优于采用穷举法对三种作业方式分别优化所得的最优解。     

A robust simulated annealing heuristic for flow shop scheduling problems

The flow-shop scheduling problem is one of the most well-known problems in the area of scheduling. The objective of minimising the makespan is often employed as a criterion for flow shop scheduling since Johnson’s work on the subject. The problem is strongly NP-hard and therefore many approximation algorithms have been developed to provide a good solution in reasonable run times. In this research, a mechanism that records the good solution’s characteristics is designed and introduced into simulated annealing to make the searching procedure more robust. Computational experiments show that simulated annealing with a designed mechanism can make the solution quality more robust than it is without the mechanism. In addition, the proposed simulated annealing procedure is also compared with some previously published algorithms in regard to performance. Results show that the proposed simulated annealing procedure performs well with respect to solution and efficiency.     

MODIFIED BOTTLENECK-BASED PROCEDURE FOR LARGE-SCALE FLOW-SHOP SCHEDULING PROBLEMS WITH BOTTLENECK

A new bottleneck-based heuristic for large-scale flow-shop scheduling problems with a bottleneck is proposed, which is simpler but more tailored than the shifting bottleneck (SB) procedure. In this algorithm, a schedule for the bottleneck machine is first constructed optimally and then the non-bottleneck machines are scheduled around the bottleneck schedule by some effective dispatching rules. Computational results show that the modified bottleneck-based procedure can achieve a tradeoff between solution quality and computational time comparing with SB procedure for medium-size problems. Furthermore it can obtain a good solution in quite short time for large-scale scheduling problems.     

半导体生产线控制与调度研究

研究半导体生产线的控制与调度对微电子企业的生产具有重大价值。总结了国内外半导体生产线控制与调度问题的研究现状，分析并比较了各种调度策略，论述了对调度问题赖以存在的模型基础，指出了存在的问题，并探讨了可能的研究方向。     

加工装配式流水车间节能调度建模与优化

为解决具有加工装配一体化的流水车间节能调度问题,以加工机器最小能耗为优化目标,建立加工装配式流水车间节能调度模型。该模型将装配线视为具有特殊约束的加工生产线,再结合考虑车间工件工序、装配工序、装配子件加工等约束条件。分别针对简单和复杂装配约束的问题,采用混合差分进化算法求解最小能耗下工件调度方案,并与自适应差分算法对比。实验结果证明了混合差分进化算法求解该问题的有效性。     

基于免疫遗传算法的车间动态调度

提出了一种求解车间动态调度问题的免疫遗传算法。该方法在遗传操作过程中,运用免疫机理提取疫苗,并对进化种群进行免疫操作,从而有效地抑制了遗传算法的“早熟”和搜索效率低下的问题;此外,该算法在解码操作过程中引入设备能力空间的概念,从而将设备的加工能力作为约束条件动态引入,有效地解决了车间动态调度和再调度方案的一致性和连续性问题。实例表明该算法能够满足车间动态调度的要求。     

含有混合中间存储策略的模糊流水车间调度方法

针对中间产品在相邻加工步骤间存在不同存储策略的流水车间调度问题,提出了一种含有混合中间存储策略的流水车间调度模型。在该模型中,考虑无限中间产品存储、有限中间产品存储、无中间产品存储3种策略同时存在的情况下对调度问题的影响,采用三角模糊数来描述生产过程中操作时间的不确定性;通过对三角模糊数的操作,并利用面积补偿的比较方法,将原有的模糊调度模型转化为确定性的调度模型;应用双倍体遗传算法对问题进行优化求解。仿真结果证明了模型和算法的有效性。     

混合流水车间调度问题的果蝇优化算法求解

针对不相关并行机混合流水车间调度问题，根据果蝇优化算法种群更新方式的特点，采用基于权重的编码方式进行编码操作，通过增加权重系数来提高算法的随机搜索能力。对算法参数的设置进行了分析，得到了最优参数组合。采用标杆实例进行仿真验证并与经典算法进行对比，验证了果蝇优化算法的有效性。     

虚拟车间的异地协同调度

阐述研究基于未来敏捷制造模式的虚拟车间调度问题的重要性和必要性,说明了基于互联网并具有多智能体结构的网络信息系统是实现虚拟车间调度的基础。针对由项目驱动的虚拟车间,提出一些尚待研究的问题,内容涉及虚拟车间的项目异地规划、异地作业计划协同编,以及基础上进程异地协同监控等。特别强调了它们与传统的车间作业计划、调度与监控问题的主要差别。指出虚拟车间异地调度的主要问题,并提出建议。     

基于过滤定向搜索的Job-Shop调度算法及评价

对以Makespan最小为目标的Job Shop调度问题进行了研究。首先对Job Shop调度问题进行了描述,在此基础上建立了一种求解Job Shop调度问题的启发式优化算法———基于过滤定向搜索的算法,同时结合实例对算法的优化过程作了具体描述。最后通过不同规模的Benchmark实例对该算法进行了仿真评价,结果表明基于过滤定向搜索的算法搜索效率高,解的性能好,是一种有效的优化算法。