基于设备工序紧凑的综合调度算法的研究

发布时间：2018-01-02 00:25

本文关键词：基于设备工序紧凑的综合调度算法的研究　出处：《哈尔滨理工大学》2011年硕士论文　论文类型：学位论文

【摘要】：由于传统车间调度算法是以工件为单位,解决的是纯加工或纯装配问题,这些方法比较适于解决品种单一、批量较大的产品调度。随着社会的进步和发展,人们的需求越来越多元化,即多品种小批量产品的生产越来越盛行,再运用传统的调度算法必然会导致资源(人力资源和设备资源等)分配的困难等,从而增加总加工时间,降低产品的生产效率,使传统方法失去其优势,因此,研究多品种小批量产品的生产,即复杂产品的综合调度问题,更具有理论价值和实际意义。复杂产品综合调度是以产品为单位,同时进行产品的加工和装配,以提高产品的生产效率。以往的复杂多产品综合调度算法,严格按产品工艺次序调度,即先调度儿子结点工序再调度父结点工序,是多对一的关系,如果先调度父结点工序再调度其儿子结点工序,则对应关系是一对多,因此本文首先提出了基于设备工序紧凑的逆序动态关键路径综合调度算法,该算法将逆序思想与综合调度相结合,在充分考虑了长路径影响产品总加工时间的同时,利用设备工序紧凑法减少设备空闲时间。又由于以往的复杂产品综合调度算法只考虑了当前需调度产品以及在调度过程中又有新产品到达的情况,忽略了各产品的开始时间和交货期都已知的情况,因此本文又提出了基于交货期紧迫度的综合调度算法,该算法根据时间紧迫度确定各产品的调度次序,并利用长路径和短用时策略提高工序加工的并行程度,理论分析和实例表明,该算法可在二次复杂度内给出开始时间与交货期都不相同的多品种小批量复杂产品较合理的综合调度方案。最后针对不同产品在并行时间段内争夺设备资源的情况,提出了按交货期由前到后确定产品调度次序的综合调度算法。该算法综合了层优先、长路径、短用时调度策略和设备工序紧凑法的优点,并用实例进行了验证。本文对复杂产品综合调度问题中的单产品和多产品(开始时间与交货期都已知)提出了相应的算法,通过理论分析和实例证明,算法复杂度都是二次的,且近优效果好,因此,具有一定的理论和现实意义。
[Abstract]:Because the traditional shop scheduling algorithm is to solve the workpiece as a unit, is pure processing or pure assembly problems, these methods are suitable for solving single species, large quantities of product scheduling. With the development of the society, people demand more and more diversified, multi varieties and small batch product production is more and more popular, and then use the scheduling the traditional algorithm will inevitably lead to resources (human resources and equipment resources) distribution difficulties, thus increasing the total processing time, reduce the production efficiency, so that the traditional way to lose its advantage, therefore, the research of multi varieties and small batch production, integrated scheduling of complex product problems, it has theoretical value and practical meaning. Integrated scheduling of complex product is a product for the unit, simultaneously carry on the processing and assembly of products, to improve production efficiency.
Integrated scheduling of complex multi product algorithm in the past, in strict accordance with the product order scheduling, the first node scheduling process scheduling son parent process, is many to one relationship, if the first parent node scheduling process scheduling process is the son node, corresponding relationship is one to many, so this paper proposes the reverse dynamic key path scheduling algorithm based on the compact equipment in the process, the algorithm will reverse thinking and comprehensive combination of scheduling, in full consideration of the total processing time of the long path effect of products at the same time, the use of equipment in the process of compact method to reduce the idle time of equipment.
Because of complex product integrated previous scheduling algorithms only consider the current need for scheduling and products in the process of scheduling and new product arrivals, ignoring the start time of each product and delivery are known, so the paper also puts forward the urgent delivery based on integrated scheduling algorithm, the algorithm based on time to determine the degree of each product scheduling sequence, and the use of long path and short time strategy to improve the parallel degree of process, theoretical analysis and examples show that the algorithm can start comprehensive scheduling scheme and delivery time are not the same as the many varieties of small batch of complex products is reasonable in two time complexity is given.
Finally, according to different products scramble for resources in parallel time, put forward according to the delivery date determined by the front to rear the integrated scheduling product scheduling sequence algorithm. The algorithm combines layer first, long path, advantages of short-time strategy and compact process method, and verified in this paper. The scheduling problem of complex products in a single product and multi product (start time and delivery time are known) the corresponding algorithm is proposed. Through theoretical analysis and examples show that the complexity of the algorithm is two times, and get good result, therefore, has a certain theoretical and practical significance.

【学位授予单位】：哈尔滨理工大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TH186;TP391.73

【相似文献】