具有时间与位置相关的两种机器排序问题研究

发布时间：2018-06-05 23:47

本文选题：排序 + 单机　；参考：《重庆师范大学》2017年硕士论文

【摘要】：本文研究在单机和平行机环境下具有时间效应和位置效应以及维修限制的排序问题,其中平行机环境下仅仅考虑恒同机和无关机.主要研究结果如下:单机排序问题1)研究工件的实际加工操作时间同时具有时间和位置效应,且在机器的加工操作中由于机器磨损而不得不进行维修活动的排序问题,其中维修区间的长度跟工件的开始加工作业的时刻相关,目标函数分别为最大完工时间和总完工时间.通过简化目标函数,使用匹配算法最后得到其多项式算法.2)证明当工件的实际加工操作时间只受到本组工件的实际加工操作时间的总和的影响、位置效应仅与工件在生产中的排列顺序有关和维修区间长度为常数的问题满足组平衡规则.当目标函数为最大完工时间时,得到此排序问题有多项式时间解,并得出其复杂度为O(n2logn).平行机排序问题1)研究工件的实际加工操作时间同时受到位置和时间效应的影响,且在工件的加工过程中,由于机器老化而不得不进行维修活动的无关机排序问题.其中问题的目标函数是由最大完工时间的总和、总完工时间的总和与总等待时间的总和所共同组成的,让其转化为指派问题,能求得多项式时间解,时间复杂度为O(nk+2/(k-1)!).2)研究工件的实际加工操作时间同时受到位置和时间效应的影响,且在工件的加工过程中,由于机器老化而不得不进行维修活动的恒同机问题.其中目标函数由最大完工时间的总和、总完工时间的总和与总等待时间的总和一起组成的,通过转化目标函数,使用匹配算法得出排序问题有多项式时间解,时间复杂度为O((2n+k+nlogn)nk-1/(k-1)!).
[Abstract]:In this paper, we study the scheduling problem with time effect, position effect and maintenance limitation in single machine and parallel machine environment, in which only constant and unshut down machines are considered in parallel machine environment. The main results are as follows: 1) the actual processing operation time of workpiece has both time and position effects, and the scheduling problem of maintenance activities has to be carried out in machine operation due to machine wear. The length of the maintenance section is related to the time when the workpiece is started, and the objective function is the maximum completion time and the total completion time respectively. By simplifying the objective function and using the matching algorithm to obtain its polynomial algorithm. 2) it is proved that when the actual processing operation time of the workpiece is only affected by the sum of the actual processing operation time of the workpiece, The position effect is only related to the arrangement order of the workpiece in production and the maintenance interval length is constant to satisfy the group equilibrium rule. When the objective function is the maximum completion time, the polynomial time solution is obtained and the complexity is obtained. Parallel machine scheduling problem 1) the actual processing operation time of the workpiece is affected by the position and time effect at the same time, and in the process of the workpiece processing, it has to carry on the maintenance activity unshut-down scheduling problem because of the machine aging. The objective function of the problem is composed of the sum of the maximum completion time, the sum of the total completion time and the total waiting time, so that the problem can be transformed into an assignment problem and the polynomial time solution can be obtained. The time complexity is O _ nk _ 2 / K ~ (-1). 2) the actual processing operation time of workpiece is affected by position and time effect at the same time, and in the process of workpiece processing, the machine has to carry on the constant same machine problem because of the machine aging. The objective function consists of the summation of the maximum completion time, the sum of the total completion time and the total waiting time. By transforming the objective function, the polynomial time solution of the sorting problem is obtained by using the matching algorithm. The time complexity is 2n k nlognnk-nk-1 / 1.
【学位授予单位】：重庆师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223

【参考文献】