差异工件且容量不同的批调度启发式算法研究

发布时间：2018-01-16 08:29

本文关键词：差异工件且容量不同的批调度启发式算法研究　出处：《安徽大学》2015年硕士论文　论文类型：学位论文

【摘要】：生产调度问题是一种应用背景非常广泛的组合优化问题,如今已经被应用到许多实际生产及生活领域,如物流、现代通讯、生产制造及通信网络等。它是指在一段时间中,对共享资源进行合适的排序分配,且在生产过程中对各个任务进行合理的规划和分配以达到某项或者多项目标最优化的过程,而合理的调度方案可以提高资源的利用率及生产效率,并降低生产成本,从而提高企业的竞争力,推动社会的发展。批处理机调度是对经典调度问题的一个重要扩展,在批处理机调度中,允许多个工件同时在一台机器上进行加工,且由于批调度广泛应用于大规模的实践活动中,因而已成为当前生产调度领域的一个研究热点。批调度问题根据不同的约束条件还会分出一些新的分支,例如,差异工件的批处理机调度,是考虑加工时间和尺寸均有差异的工件在批处理机上进行加工的调度问题；动态批调度是针对带有到达时间的工件在进行加工时,由于工件不是机器开始加工时即可用,因而各工件的的加工还要受到不同的影响。这些调度问题往往更加接近真实的生产加工环境,但也因为要优化的目标函数种类多、各种约束条件多及它的不确定性等特征而更加复杂,且其中有许多问题已经被证明是NP-难的。因此针对复杂的生产环境,如何去设计一个简单而又高效的调度求解算法始终是批调度研究领域的一个重点。本文首先简要介绍了生产调度问题的相关概念,例如调度问题通用的三参数表示法及调度问题的分类。其次,对批调度问题、差异工件批调度问题及工件动态到达的差异工件批调度问题分别进行了介绍；再从单机环境、并行机环境和车间环境分别介绍了批处理机调度问题的研究现状,并指出了当前研究存在的问题。然后详细的介绍了求解批调度问题的方法,并同时给出了各类求解算法的具体例子,如FFLPT、BFLPT等经典的启发式算法和蚁群算法、遗传算法及模拟退火算法等元启发式算法。接着,探讨了本文研究的动态环境及机器容量不同的约束下差异工件批调度问题。当前关于多机批调度的研究中,其约束条件及加工环境都是比较简单的,如工件到达时间为0且机器容量相同,即静态调度环境。本文针对工件动态到达的差异工件且机器容量不同的批调度问题进行研究,给出了几种启发式优化算法对其分别进行求解。将本文的问题分为两个子问题：首先采用FFLPT和BFLPT启发式规则将所有工件进行分批；然后针对工件分组所得的批集合,分别采用FFLPT和BFLPT算法进行批调度,将批集合分配到机器上进行加工。此外,在批调度过程中,通过MultiFit算法来优化目标函数。通过仿真实验对文中所提的启发式算法和下界LB进行比较,验证性能并进行了性能分析,实验结果表明本文所给几种算法的有效性,其中BB(BFLPT-BFLPT)算法的性能明显优于其他几种算法。最后,总结本文的研究内容,并对今后的研究方向进行了展望。
[Abstract]:The production scheduling problem is combinatorial optimization problem with a very wide application background, has now been applied to many practical production and life field, such as modern logistics, communications, manufacturing and communication network. It refers to a period of time, sort the appropriate allocation of shared resources, and in the production process rational planning and allocation of tasks to achieve a number of goals or process optimization, and a reasonable control scheme can improve the resource utilization rate and production efficiency, and reduce the production cost, so as to improve the competitiveness of enterprises, promote the development of the society. A batch scheduling is an important extension of the classical scheduling problem in the batch processor scheduling, allowing a plurality of workpieces processed simultaneously on a single machine, and because the batch scheduling is widely used in large-scale practice, which has become the current students A research hotspot in production scheduling field. Batch scheduling problem with different constraints, but also from some new branches, for example, a batch scheduling between the workpiece, is the scheduling problem considering the processing time and size were different processed in batch processor; dynamic batch scheduling is to arrive at the workpiece with time when processing the workpiece, due not to start processing machine is available, so the processing of parts have different effects. These scheduling problems tend to be more close to the real production environment, but also because of the objective function to optimize the multi species, multi constraints and its uncertainty and other characteristics are more complex, and there are many problems have been proved to be NP- hard. So according to the complex production environment, how to design a simple and efficient scheduling algorithm Batch scheduling is always one of the most important research field. This paper firstly introduces the related concepts of the production scheduling problems, such as scheduling problems with three parameters general representation classification and scheduling problem. Secondly, the batch scheduling problem, different workpiece batch scheduling problem and the workpiece to the different workpiece dynamic batch scheduling problem were carried out introduction; from single environment, research status of a batch scheduling problem is introduced parallel machine environment and workshop environment respectively, and points out the problems in current research. Then it introduces the method to solve the batch scheduling problem, and gives specific examples, different algorithms such as FFLPT, BFLPT and other classical heuristic algorithm and ant colony algorithm, genetic algorithm and simulated annealing algorithm and heuristic algorithm. Then, discusses the dynamic environment and the capacity of the machine is studied in this paper under different constraints difference Different batch scheduling problem. The current research on multi machine batch scheduling, the constraints and the processing environment is relatively simple, such as the arrival time is 0 and the capacity of the machine is the same, namely static scheduling environment. This paper studies the dynamic job arrivals different workpieces and machine capacity is not the same batch scheduling problem given several heuristic optimization algorithm to solve them respectively. This problem is divided into two sub problems: first of all the jobs into batches using FFLPT and BFLPT heuristic rules; then according to the number of work grouping sets, respectively using FFLPT and BFLPT algorithm for batch scheduling, the number of sets assigned to the machine. In addition, in the process of batch scheduling, optimization of objective function by the MultiFit algorithm. Based on the proposed heuristic algorithm and the lower bound of LB for simulation, verification of And the performance analysis is carried out. The experimental results show the effectiveness of several algorithms. The performance of BB (BFLPT-BFLPT) algorithm is obviously better than the other algorithms. Finally, the research contents of this paper are summarized, and the future research directions are prospected.

【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：F273;TP18

【参考文献】