几类加工时间与位置相关的单机排序问题

发布时间：2018-10-12 11:43

【摘要】：在传统的排序中,工件的加工时间是一个固定不变的参数,工件在机器上依次加工。但根据实际的需要,工件的实际加工时间已不再是固定不变的参数,而是与实际问题相关的函数。本文主要研究工件的加工时间是可变的单机排序问题。其中,工件的实际加工时间是与工件位置和开始加工时间有关的函数。本文具体研究内容概括如下:1)在工件同时带有学习效应和恶化效应的单机排序问题中,工件的学习效应是与工件的实际加工位置相关的函数,工件的恶化效应是与工件的开始加工时间相关的线性函数。讨论单机情况下工件最大完工时间、总完工时间及总完工时间的绝对差之和的问题,证明了这些问题都是多项式时间可解的。进一步,在线性资源分配情况下,讨论了带有学习效应、恶化效应和资源分配的工期指派问题,工件有一个共同的工期。目的为确定最优工期、最优资源分配量及工件加工顺序,使公共工期、提前、延误和资源分配之和为最小。通过将其转化为指派问题,证明了带有学习效应、恶化效应和资源分配的工期指派问题是多项式时间可解的。2)工件的学习效应是与工件的实际加工位置相关的一般函数,工件的恶化效应是与工件的开始加工时间相关的线性函数,分别得到了最大完工时间、总完工时间及总完工时间的绝对差之和问题的多项式时间算法。3)在机器在恶化维修时间的情况下,工件的实际加工时间是与工件基本加工时间和工件实际加工位置相关的一般函数。确定了最优工期、加工顺序及机器维修位置,使提前、延误和工期的之和最小。通过将这个问题转化为指派问题,证明了该问题在多项式时间内是可解的,并给出此问题的一种特殊情况的最优算法。
[Abstract]:In the traditional sorting, the processing time of the workpiece is a fixed and invariant parameter, and the workpiece is processed on the machine in turn. However, according to the actual needs, the actual processing time of the workpiece is no longer a fixed parameter, but a function related to the actual problem. This paper focuses on the single machine scheduling problem in which the processing time of the workpiece is variable. The actual processing time of the workpiece is a function related to the position and the starting time of the workpiece. The specific contents of this paper are summarized as follows: 1) in the single machine scheduling problem where the workpiece has both learning effect and deterioration effect, the learning effect of the workpiece is a function related to the actual processing position of the workpiece. The deterioration effect of the workpiece is a linear function related to the starting time of the workpiece. This paper discusses the sum of the absolute difference between the maximum completion time, the total completion time and the total completion time of the workpiece in the case of single machine, and proves that these problems are solvable with polynomial time. Furthermore, in the case of linear resource allocation, the assignment problem with learning effect, deterioration effect and resource allocation is discussed. The workpiece has a common duration. In order to determine the optimal time limit, the optimal allocation of resources and the processing order of the workpiece, the sum of common time limit, advance time, delay and resource allocation is minimized. By transforming it into assignment problem, it is proved that the assignment problem with learning effect, deterioration effect and resource allocation is polynomial time solvable. 2) the learning effect of workpiece is a general function related to the actual processing position of workpiece. The deterioration effect of the workpiece is a linear function related to the starting time of the workpiece, and the maximum completion time is obtained respectively. A polynomial time algorithm for summing the absolute difference between the total completion time and the total completion time. 3) when the machine is deteriorating the maintenance time, The actual processing time of the workpiece is a general function related to the basic processing time of the workpiece and the actual machining position of the workpiece. The optimal duration, processing sequence and machine maintenance position are determined to minimize the sum of advance, delay and duration. By transforming the problem into an assignment problem, it is proved that the problem is solvable in polynomial time, and an optimal algorithm for the special case of the problem is given.
【学位授予单位】：沈阳师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223

【相似文献】