【作者】 卢超；

【导师】 高亮； 李新宇；

【作者基本信息】 华中科技大学 ， 工业工程， 2017， 博士

【摘要】 车间调度问题是现代制造系统中亟需解决的组合优化问题之一。在传统车间调度的研究中,工件加工时间通常被假定为常量,但是实际生产中的工件加工时间是可变的,它可通过消耗可用的额外资源(如,燃料、人力、机器、能耗以及资金等)加以控制。同时,由于压缩工件加工时间可在一定程度上提高生产效率,所以实际生产中工件加工时间往往会有所调整。因此,考虑加工时间可控的车间调度更加符合实际生产。然而,相比于传统车间调度问题,由于考虑了加工时间可控的特性,该问题的求解难度会更大,这也导致了针对该问题的研究进展缓慢。尽管相关研究可追溯到1980年,但是多数研究主要集中在相对简单的单机调度类型上,缺乏针对更复杂车间调度类型的研究成果。因此,亟需对加工时间可控的车间调度问题进行更系统和深入的研究。此外,由于控制加工时间需消耗额外资源,会导致成本的增加,所以该问题本质上是一个多目标优化问题。基于上述原因,本文对多种类型的加工时间可控的多目标车间调度问题开展了系统深入地研究。本文的主要工作如下:针对加工时间可控的单机调度问题,建立了以同时最小化总加工延迟时间和额外资源总消耗量为目标的数学模型,提出了一种基于遗传算法(GeneticAlgorithm,GA)与灰狼优化算法(Grey Wolf Optimizer,GWO)相混合的MODGWO方法。结合问题的特点,设计了一种新的离散编码机制,该编码机制包含了工件排序向量和工件实际加工时间向量两层信息,通过实验证明了该编码方式的可行性和有效性。为了提高算法的搜索多样性和收敛性,提出了两种策略来改善算法性能。为了测试MODGWO算法的性能,将MODGWO与NSGA-Ⅱ、PAES及SPEA2进行了实验对比。实验结果表明MODGWO在大多数问题上要优于其它算法。针对加工时间可控的不相关并行机调度问题,建立了以同时最小化Makespan和额外资源总消耗为目标的数学模型,该模型考虑了依赖工件序列的准备时间。为了求解该类调度问题,本文提出了一种基于GA与病毒优化算法(Virus Optimization Algorithm,VOA)相结合的MODVOA方法。结合问题的特点,设计了一种新的离散编码机制。为了评价MODVOA算法的性能,将MODVOA与NSGA-Ⅱ、SPEA2及MODGWO进行了实验结果对比。实验结果表明提出的MODVOA算法在大多数问题上要好于其它对比算法。针对加工时间可控的流水车间调度问题,首先建立了以同时最小化Makespan和机器负载总惩罚量为目标的数学模型,该模型考虑了依赖工件序列的准备时间与依赖工件的传输时间。由于单机调度与流水车间调度有相似的特点(均需对工序进行排序),所以以提出的单机调度算法为基础,开发了一种多目标离散灰狼优化算法(MODGWO)来求解加工时间可控的流水车间调度问题。同时,根据问题的属性,引入了一种机器负载降低策略。为了评价MODGWO的性能,将MODGWO与NSGA-Ⅱ、SPEA2及MODVOA进行了实验对比,实验结果表明MODGWO在求解该类调度问题上要显著地优于其它算法。针对加工时间可控的柔性作业车间调度问题,构建了此类车间调度问题的数学模型,该模型的目标是同时最小化Makespan和额外附加资源总消耗。由于并行机调度与柔性作业车间调度有相似特点(均考虑机器可选),以先前提出的并行机调度算法为基础,开发了一种混合多目标离散病毒优化算法,即MODVOA。该算法的创新点有:每个解包含了三层表达信息、改进的初始种群以及集成的更新操作算子。同时,在算法的搜索后期,采用了基于问题知识的开采机制操作以改善算法的局部搜索性能。为了评价MODVOA的性能,将MODVOA与其它MOEAs(如NSGA-Ⅱ、SPEA2和MODGWO)进行了实验对比,实验结果表明MODVOA在求解该类调度问题上要优于其它算法。本文结合上述理论成果和焊接车间以及发动机冷却风扇加工车间的生产情况,分析了实际车间中存在的加工时间可控的多目标调度问题,将本文的理论成果应用于实际车间的生产,结果表明本文提出的多目标调度优化算法的实用性。最后对全文的成果以及创新之处进行了总结,并展望了未来的研究方向。更多还原

【Abstract】 Shop scheduling problem with controllable processing times(CPT)is one of the most crucial combinatorial optimization problems to be solved urgently in the modern manufacturing systems.In the traditional shop scheduling problems,job processing times are usually deemed to be fixed.However,job processing times can be controlled by allocating available resources(e.g.,fuel,human resouce,machine,energy and finance)in the practical production.Meanwhile,compressing job processing times can improve production efficiency to some extend,thus,job processing times are usually adjusted in the practical production.Obviously,condsideration of controllable processing times in shop scheduling problems is more close to the practical production.However,compared with the traditional shop scheduling problems,it will increase the difficulty of problem-sloving because of considering the controllable processing times.For this reason,the first study on this field can be traced back to 1980,but most research is mainly focused on relatively simple signle machine environment.Obviously,there is few studies reported on the complex shop scheduling problems.Additionally,controlling processing times need to consume extra resources,which also leads to the increase of the cost.Therefore,the shop scheduling problem with controllable processing times is a multi-objective optimization problem in nature.Based on the above reasons,this paper makes a system and deep research on various types of multi-objective shop scheduling problems with controllable processing times.The main work of this paper is as follows:For the single machine scheduling problem with controllable processing times,this paper constructs a mathematical model for minimizing the total tardiness and total extra resource consumption,and proposes a hybrid algorithm(MODGWO)based on genetic algorithm(GA)and grey wolf optimizer(GWO).According to the characteristic of such a problem,a new discrete encoding schema is designed.This encoding schema contains two layers information:job sequence vector and the job practical processing time vector.The feasibility and effectiveness of this encoding schema has been validated by conducting an experiment.To improve the diversity and convergence of the proposed algorithm,two kinds of strategies are proposed to enhance its performance.To evaluate the performance of MODGWO,it is compared with other classical MOEAs including NSGA-Ⅱ,SPEA2 and PAES.Experimental results show that the MODGWO is superior to other MOEAs on most problems.For the unrelated parallel machine scheduling problem with controllable processing times,this paper formulates a mathematical model considering sequence-dependent setup times(SDST).The objectives of this problems are to minimize the makespan and total extra resource consumption simultaneously.To solve this problem,this paper presents a hybrid algorithm based on GA and virus optimization algorithm(MODVOA).To adapt to the characteristic of such a problem,a new discrete encoding schema is designed.To evaluate the performance of MODVOA,it is compared with other MOEAs including NSGA-II,SPEA2 and MODGWO.Experimental results show that MODVOA is superior to other MOEAs on most problems.For the flow shop scheduling problem with controllable processing times,this paper first formulates a mathematical model for minimizing makespan and total machine load.This model considers SDST and job dependent transportation times(JDTT).Single machine scheduling and flow shop scheduling problems have the common characteristic(i.e.,both need to perform the job permutation).Therefore,based on the proposed algorithm in the single machine scheduling problem with controllable processing times,we propose a multi-objective discrete grey wolf optimizer(MODGWO)to address such a scheduling problem.According to the characteristic of this problem,one reduction machine load strategy is used to adjust the number of machines aiming to minimize the machine load.To evaluate the effectiveness of the proposed MODGWO,we compare it with other well-known multi-objective evolutionary algorithms including NSGA-Ⅱ、SPEA2 and MODVOA on a set of instances.Experimental results demonstrate that the proposed MODGWO is significantly better than its compared algorithms on most instances.For the flexible job shop scheduling problem with controllable processing times,this study formulates a mathematical model with the objectives of minimizing both the makespan and the total additional resource consumption.Unrelated parallel machine scheduling and flexible job shop scheduling problems have one common characteristic(i.e.,both need to select available machine).Therefore,based on the proposed algorithm in the unrelated parallel machine scheduling problem with controllable processing times,we design a new multi-objective discrete virus optimization algorithm(MODVOA)with a three-part representation for each virus,an improved method for yielding the initial population,and an ensemble of operators for updating each virus.To further improve the exploitation,a problem-specific exploitation mechanism is implemented in the later stage of the search process.Finally,to evaluate the effectiveness of the MODVOA,the MODVOA is compared with other well-known multi-objective evolutionary algorithms including NSGA-Ⅱ、SPEA2 and MODGWO.Experimental results on randomly generated instances demonstrate that the proposed MODVOA can achieve a better performance than other algorithms for solving such problems.Based on the above theoretical fruits and the workshop production situation,this paper analyses the existing multi-objective scheduling problems with controllable processing times in the practical production applications.Then,the theoretical fruits are applied to the practical applications.Experimental results certify the effectiveness of the proposed multi-objective scheduling optimization algorithm.Finally,the above work and novel points are summarized,and the future research directions are discussed.更多还原