【作者】 聂黎；

【导师】 高亮； 李培根；

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

【摘要】 随着经济的快速发展,制造企业之间的竞争越来越激烈。为了提高自身的竞争力,制造企业越来越关注如何对车间中复杂多变的生产活动进行高效的调度,以满足多样化的客户需求。车间动态调度问题成为制造系统研究领域的热点之一。本文将基因表达式编程(Gene Expression Programming, GEP),一种新的进化算法,引入到车间动态调度问题的研究中,探索先进的车间动态调度方法,以提高车间对动态事件的反应能力及调度质量。由于客户的需求多样多变,生产车间具有动态事件频发的特点,如何快速响应动态事件,并作出合理的调度决策是非常重要的。本文在深入研究GEP基本原理的基础上,结合车间动态调度问题的特征,提出基于GEP的车间动态调度框架,以实现对车间生产活动的实时、高效调度。该框架将车间调度过程分成离线学习和在线调度两个阶段：GEP通过离线学习自动构造高效调度规则；调度规则与在线启发式算法相结合,快速制定合理的在线调度决策。在该框架中,GEP构造调度规则的学习过程被归结为GEP的搜索过程。如何设计适合车间动态调度问题的有效染色体编码方案是关键问题之一。本文提出一种将调度规则映射为GEP串行染色体的间接编码方式,有效减少染色体的存储空间,提高染色体编码的利用效率。另外,如何对染色体进行正确的评价同样重要。通过分析已有适应度函数的不足,提出一种适用于非监督学习的适应度函数,有效降低算法搜索能力对领域知识的依赖程度。考虑到单机调度问题是车间调度中最基本的一类问题,本文围绕上述车间动态调度框架,以工件动态到达这类典型的动态事件为例,深入研究基于GEP的单机动态调度方法。为了实时地对动态到达的工件进行合理调度,提出一种单机动态调度在线启发式算法,通过改进候选工件集合构造方法,提高该算法的效率。结合该在线启发式算法,采用单基因染色体结构,设计染色体编码和解码方案,提出基于GEP的单机动态调度规则构造方法。通过仿真实验,与其它方法进行比较,验证基于GEP的单机动态调度方法的有效性和高效性。作业车间调度问题是研究得最为广泛的一类经典调度问题,是典型的NP-难问题。借鉴上述单机动态调度方法,深入研究基于GEP的作业车间动态调度方法。由于工序约束和机器约束是导致作业车间动态调度问题求解困难的重要原因,提出作业车间动态调度在线启发式算法,有效地处理各种约束条件,并协调各机器之间的动作。根据作业车间动态调度问题的特点,采用多基因染色体结构,设计染色体的编码和解码方案,提出利用GEP构造作业车间动态调度规则的方法。利用仿真实验对所提出的作业车间动态方法的性能进行测试。实验结果表明,该方法学习效率高,构造的调度规则鲁棒性强。柔性作业车间调度问题是作业车间调度问题的一种扩展,是一类更加难以求解的调度问题。通过借鉴作业车间动态调度方法,深入研究基于GEP的柔性作业车间动态调度方法。考虑到柔性作业车间中机器具有加工柔性,提出柔性作业车间动态调度在线启发式算法,将柔性作业车间调度问题分解为路径子问题和排序子问题,有效地降低该问题的求解难度。结合该在线启发式算法,设计二元组染色体结构,将路径子问题和排序子问题的解分开表示,并使它们能够协同进化。同时该染色体结构无需修改已有的遗传算子,有效地保证GEP的搜索效率。通过仿真实验对提出的柔性作业车间动态调度方法的性能进行测试,实验结果表明该方法的性能明显优于其它方法。在以上研究成果的基础上,结合实际应用对象,设计和开发车间动态调度原型系统,并通过实例在该原型系统中对本文所提出的方法进行验证。最后,对全文工作进行总结,并对今后研究方向进行展望。更多还原

【Abstract】 With the increasing rapid development of global economy, the competition between manufacturing enterprises is more intense. In order to enhance their competitiveness, manufacturing enterprises inereasingly concern on how to sehedule the activities in the shop floor so that custormer demands are satisfied. Dynamic scheduling problems have become one of the hot topics in the research of manufacturing system. Gene Expression Programming (GEP) is a new envolutionary algorithm proposed recently.In the paper, GEP is introduced into the research of dynamic scheduling approaches in order to improve the agility, steadiness and robustness of schedules in shop floor.Dynamic events always occur in the shop floor because of the variational custormer demands. It is important to respond to dynamic events rapidly and to make reasonable scheduling decisions. A dynamic scheduling framework which is based on the basic evolution principle of GEP is proposed. According with the framework, GEP learns to construct efficient scheduling rules (SRs) off line. Then, the GEP-constructed SRs are used to implement the reactive scheduling in shop floor in the combination with on-line heuristics. In order to solve the encoding problem, an indirect encoding scheme which maps a SR into a GEP chromosome is proposed. In addition, a fitness function which is suitable for unsupervisory learning is proposed in order to evaluate the fitness of chromosomes.Single machine scheduling problem is the basic scheduling problem. Based on the dynamic scheduling framework proposed above, the approach for dynamic scheduling problem with job release dates on single machie (DSMP) is investigated. An on-line heuristic for DSMP is proposed, in which the constructing method for the candidate job set is improved. GEP-based method for the construction of SRs is also proposed, in which the chromosome is encoding and decoding with the single-gene chromosome, which makes the SRs consturted quickly and expressed compactly. Simulation experiments are conducted to evaluate the performance of the proposed method. Experiment results show that it is efficient and superior to other methods.Job shop scheduling problem is the classical scheduling problem, which is researched extensively. The dynamic scheduling approach for DSMP is extended and applied to the dynamic scheduling problem with job release dates in job shop (DJSP). An on-line heuristic for DJSP is proposed, which decomposes the original DJSP into a number of sub problems. Each sub problem, in fact, is a dynamic single machine scheduling problem with job release dates. The on-line heuristic for DJSP not only makes the constraint conditions in job shop satisfied, but also harmonizes the actions between multiple machines based on the states and constraints in the system. GEP-based SRs constructing method is also proposed, in which the chromosome is encoding and decoding with the multi-gene chromosome, which makes the excellent segments of gene builded easily and transferred to offspring extensively. Simulation experiments are conducted to evaluate the performance of the proposed method in the comparison with other methods. Results show that the proposed method is effective and overperform other methods.Flexible job shop scheduling problem is one of the extension of job shop scheduling problem and its complexity is higher. The dynamic scheduling method for DJSP is extended and applied to the dynamic scheduling problem with job release dates in flexible job shop (DFJSP). An on-line heuristic for DFJSP is proposed, which decomposes the original DFJSP into two sub problems:routing problem and sequencing problem. Therefore, the complexiby of the original scheduling problem is reduced. GEP-based SRs constructing method is also proposed, in which the chromosome is encoding and decoding with the two-sub component chromosome, which makes the exsit genetic operators applied directly on the chromosomes without illegal offspring creating. In order to evaluate the performance of the proposed dynamic scheduling approach, a variety of processing conditions are considered in the simulation experiments. The results show that GEP-based approach can construct simultaneously more efficient machine assignment rules and job dispatching rules for DFJSP than other approaches.Based on the research work mentioned above, dynamic scheduling prototype system oriented to real-world production workshop is designed and developed. The system architecture and function modules are described briefly. In additioan, the application example of the system is exhibited.Finally, the research results achieved in the dissertation is summarized and future work is prospected.更多还原