【作者】 胡常伟；

【导师】 陈新；

【作者基本信息】 广东工业大学 ， 机械电子工程， 2013， 博士

【摘要】 精铸作为一种面向复杂型腔模具及模具小批量制造的新方法,在一些模具企业得到了很好的应用。铝合金熔炼是精铸的关键工序之一,对铝合金熔炼任务合理组批调度,对于企业节能减排、降低成本、提高模具制造效率具有重要意义。在熔炼工序中,熔炼任务批调度是一个具有不同任务到达时间和不一致重量任务的批调度问题,其熔炼任务批工时与熔炼任务重量为单调递增函数关系。面向单机或同型机的、以批中最大任务工时为批工时的并行批调度算法不能直接应用于此问题求解。本文以不一致熔炼任务平行机批调度问题为研究背景,系统的研究了单机、同型机、同类机、不相关机批调度问题,重点研究批调度问题的任务分批规则、调度优化规则及其求解算法。主要工作内容如下：(1)面向模具精铸中铝合金熔炼过程,研究熔炼任务批特征,以最小化最大完工时间为目标,建立不一致熔炼任务的平行机批调度统一模型。(2)不一致熔炼任务的单机批调度算法研究。单机批调度是平行机批调度问题的基础。结合单机环境下不一致熔炼任务的特点,首先将统一模型简化为单机批调度模型；建立了考虑任务同时投放情形下基于批重量匹配(BWF)分批规则的遗传算法；考虑任务动态投放情形,提出了基于批投放时间优先(BRF)分批规则和批任务左移(JLS)优化规则的遗传算法；仿真实验表明该算法计算效率优于模拟退火算法。(3)不一致熔炼任务的同型机批调度算法研究。针对同型机熔炼约束相同的特征,采用先将任务分批、再将任务批分配到批处理机并排序的两阶段遗传算法求解思路。首先采用BWF、BRF分批规则对任务分批,然后采用通常的最长加工时间(LPT)、最早投放时间(ERT)规则将任务批分配到批处理机并排序,并对该优化结果采用最小同型机完工时间差(MCDPM)、同型机最后完工批任务调整(JALBPMR)优化规则进行进一步优化,可有效避免遗传算法的过早收敛。(4)不一致熔炼任务的同类机批调度算法研究。考虑到同类机容量约束相同、加工速度不同的特点,对同型机批调度算法进行改进,提出了以最小同类机完工时间差(MCDQM)代替MCDPM、以同类机最后完工批任务调整(JALBQMR)优化规则代替JALBPMR建立同类机批调度遗传算法。针对任务同时投放及动态投放两种情形的仿真实验表明,算法具有良好的求解质量及效率。(5)不一致熔炼任务的不相关机批调度算法研究。由于批处理机容量不一致,前述同型机、同类机的分阶段求解思路不再适应。针对任务同时到达情况,综合考虑任务分批与批分配到批处理机的过程,提出机器最早完工时间与批首次匹配(MECT-BFF)调度规则；针对任务动态到达情况,借鉴BWF、BRF分批规则先随机分批然后再进行批调整的思路,采用最大批处理机容量约束作为批修复的判断依据,并将从需修复批中调整出来的任务,按最小容量约束组批,在此基础上提出了最早投放时间与机器最早完工时间(ERT-MECT)调度规则。基于提出的规则设计了混合粒子群算法,实验结果表明算法具有很好的求解质量。(6)熔炼炉批调度模块的设计开发和应用。基于本文提出算法开发的熔炼炉批调度管理模块,已嵌入到团队开发的模具生产计划与调度系统中，并在一家大型模具企业得到应用,应用效果良好。总之,本文针对不一致熔炼任务批调度问题进行了较为系统、深入的研究,建立了该类问题的平行机调度统一模型,提出了BWF、BRF分批规则以及MCDPM、 MCDQM、JALBPMR、JALBQMR优化规则,针对复杂的不相关机问题提出了MECT-BFF、ERT-MECT调度规则,并在此基础上针对各种机器环境提出了有效的求解算法,丰富了批调度的理论研究和应用领域。更多还原

【Abstract】 Precision casting is a new method for mold manufacturing, and is applied in some mold enterprises with demands for small batch manufacturing and more complex mold cavities. Aluminum alloy melting is one of the key processes of precision casting. Reasonable scheduling of melting jobs in batches has important significance for saving energies, reducing emissions, reducing costs and improving the efficiency of mold manufacturing.The melting jobs scheduling is a batch scheduling with non-identical jobs and unequal release times, and there is a monotone increasing function relationship between the processing time and the weight of melting batches. Algorithms of parallel batch scheduling on single machine and identical parallel machines cannot be directly applied to melting batch scheduling because the processing time of parallel batches is the maximum processing time of all the jobs in the batch. Base on scheduling problems of parallel batch processing machines with non-identical melting jobs, the researches focused on batch rules, scheduling optimization rules and efficient solution algorithms on single machine, identical parallel machines, uniform parallel machines and unrelated parallel machines. The main works were as follows:(1) For melting aluminum alloy in precision casting of molds, the features of melting batch were studied, and batch scheduling unified model of parallel batch processing machines with non-identical melting jobs to minimize the maximum completion time.(2) Scheduling algorithm of single batch processing machine with non-identical melting jobs. Scheduling single batch processing machine is a base of scheduling parallel batch processing machines. According to the characteristics of melting jobs, the unified model was simplified as a model of single batch processing machine. With the equal release times, based on the batch weight fit (BWF) rule, the genetic algorithm was proposed. With the unequal release times, the genetic algorithm was proposed by the batch release time first (BRF) and job left shift (JLS) heuristic rulers. Simulation experiments showed that algorithms were more efficient than the simulated annealing algorithms. (3) Scheduling algorithm of identical batch processing machines with non-identical melting jobs. The method of two phases was adopted that jobs were grouped to batches, and then batches were assigned to batch processing machines. Firstly, BWF、BRF rulers could be used to form batches because of the same type machine capacity constraints. Secondly, the longest processing time (LPT) and the earliest release time (ERT) heuristic rulers could be adopted to assign to batch processing machines. Then, the minimum completion time difference for identical parallel batch-processing machines (MCDPM) and the job adjustment of the latest batch for identical parallel batch-processing machines with unequal release times (JALBPMR) optimization rules were proposed to further optimize the batch scheduling results by LPT and ERT rulers. The optimization rules could effectively avoid premature convergence of genetic algorithms.(4) Scheduling algorithm of uniform batch processing machines with non-identical melting jobs. Based the features of identical capacities and non-identical speeds, for improvement of scheduling algorithms of identical batch processing machines, genetic algorithms of uniform batch processing machines were proposed that MCDPM was replaced by the minimum completion time difference for uniform parallel batch-processing machines (MCDQM) rule and JALBPMR was replaced by the job adjustment of the latest batch for uniform parallel batch-processing machines with unequal release times (JALBQMR) rule. With equal and unequal release times, simulation experiments demonstrated that algorithms had good solution qualities and efficiencies.(5) Scheduling algorithm of unrelated batch processing machines with non-identical melting jobs. Because capacities of the machines are not equal, the solved methods of identical and uniform batch processing machines didn’t fit. With the equal release times, the machine earliest completion time and batch first fit (MECT-BFF) heuristic was proposed to group jobs into batches and assign batches to machines at the same time. With the unequal release times, referenced the BWF and BRF batches ruler, the maximum capacity constraints were used to judge whether a batch need to be repaired, and the minimum capacity constraints were used to group jobs to new batches that jobs came from batches repaired. Then the earliest release time and machine earliest completion time (ERT-MECT) heuristic was proposed to group jobs into batches and assign batches to machines. Hybrid particale swarm optimization algorithms were proposed, and experiment results showed that the algorithms had good solution qualities.(6) The scheduling module of melting jobs developed and applied. The scheduling module of melting jobs based on the research results of the paper were embedded in the production planning and control system. The system was applied successfully in the enterprises.In conclusion, scheduling problems of parallel batch processing machines with non-identical melting jobs were systematically, deeply studied. Scheduling unified model was established. Some rulers were proposed, such as BWF, BRF batch rules, JLS, MCDPM, MCDQM, JALBPMR, JALBQMR optimization rules and MECT-BFF, ERT-MECT scheduling rules. Based on various machine environments, some efficient solution algorithms were proposed. The researches had enriched the theory researches and application fields of batch scheduling.更多还原