平行机环境下批处理机调度问题研究

发布时间：2020-06-14 04:42

【摘要】：批处理机调度(或简称批调度)是一类具有很强应用背景的新型调度优化问题,在生产制造过程中具有广泛应用。经典生产调度中通常有机器单件加工的假设,批调度打破了该假设,允许多个工件组成一批同时进行加工。因而在批调度问题的求解中,不仅需要考虑选择加工机器的问题,还需要考虑工件成批问题。批调度问题相对于经典调度而言更为复杂,目前,很多批调度问题均已经被证明是NP难的。因而对这类调度问题进行研究在理论和实践上均有重要的意义。目前,已经有不少针对批处理机调度问题的研究,但主要集中在单机以及相同平行机的加工环境,随着柔性制造等生产制造模式的兴起和发展,将批处理机调度问题扩展到多机环境下更为一般的情况将显得越发必要。本文对平行机环境中相同平行机、同类平行机和不相关平行机加工环境下的批处理机调度问题以最小化制造跨度(Makespan)为优化目标做了研究。论文主要工作与创新点如下： 1)将批处理机调度问题扩展到分布式环境下,提出了批调度问题的一个新模型。在该模型中,工件动态到达各批处理机,且在加工之前和之后需要有运输时间。证明了该模型是NP难的,并通过问题的一个下界来衡量各算法性能。给出了分布式环境下批分配的一个启发式算法AR(assignment rule)以及一个分批准则BR(batching rule),在此基础上对问题的求解提出了若干启发式算法。仿真实验表明各算法均可以对问题进行有效的求解,加入分批准则对于算法有进一步的优化作用。 2)对同类机加工环境下具有不同尺寸工件的批处理机调度问题进行了研究。同类机环境中机器具有不同加工速率,并且每台机器相对所有工件加工速率相同。由于该问题是NP难解的,论文给出了一个下界以衡量所提启发式算法的性能,并证明了该下界的有效性。提出批的“隐性加工时间”概念,并以此为基础提出一个新的局部优化算法LORPT (Local Optimization with Recessive Processing Time)对最大最小蚁群算法(MMAS)进行改进。使用启发式算法MMAS-LPTUM(Longest Processing Time for Uniform Machines)对同类机环境下批调度问题进行求解。通过仿真实验将MMAS和遗传算法(Genetic Algorithm)、微粒群优化算法(Particle Swarm Optimization)及BFLPT(BestFit Longest Processing Time)等做了比较和性能分析。 3)对同类机环境下工件动态到达的批处理机调度问题做了研究,优化目标为最小化Makespan,提出若干启发式算法对问题进行求解。将分批准则BR扩展到同类机环境以优化工件成批过程。成批完成后,使用ARUM(Assignment Rule for Uniform parallel Machines)将批分配到同类机。文章同时给出一个下界以衡量算法性能。仿真实验表明,所提启发式算法算法可以有效求解调度问题,分批准则BR对各启发式算法具有明显改进效果。 4)对不相关机加工环境下最小化Makespan的批处理机调度问题给出若干启发式算法进行求解。不相关机加工环境下,各机器对任一工件具有不相关的加工速度。根据不同调度机制提出两组启发式算法对问题进行求解。给出一下界以衡量所提启发式算法性能。仿真实验结果表明,相对于其它启发式算法J_SC-BFLPT具有更优的求解性能及更好的鲁棒性。 【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TH186

【引证文献】