發(fā)布時間：2018-06-05 23:47

  本文選題：排序 + 單機　； 參考：《重慶師范大學》2017年碩士論文

【摘要】：本文研究在單機和平行機環(huán)境下具有時間效應和位置效應以及維修限制的排序問題,其中平行機環(huán)境下僅僅考慮恒同機和無關機.主要研究結果如下:單機排序問題1)研究工件的實際加工操作時間同時具有時間和位置效應,且在機器的加工操作中由于機器磨損而不得不進行維修活動的排序問題,其中維修區(qū)間的長度跟工件的開始加工作業(yè)的時刻相關,目標函數(shù)分別為最大完工時間和總完工時間.通過簡化目標函數(shù),使用匹配算法最后得到其多項式算法.2)證明當工件的實際加工操作時間只受到本組工件的實際加工操作時間的總和的影響、位置效應僅與工件在生產(chǎn)中的排列順序有關和維修區(qū)間長度為常數(shù)的問題滿足組平衡規(guī)則.當目標函數(shù)為最大完工時間時,得到此排序問題有多項式時間解,并得出其復雜度為O(n2logn).平行機排序問題1)研究工件的實際加工操作時間同時受到位置和時間效應的影響,且在工件的加工過程中,由于機器老化而不得不進行維修活動的無關機排序問題.其中問題的目標函數(shù)是由最大完工時間的總和、總完工時間的總和與總等待時間的總和所共同組成的,讓其轉化為指派問題,能求得多項式時間解,時間復雜度為O(nk+2/(k-1)!).2)研究工件的實際加工操作時間同時受到位置和時間效應的影響,且在工件的加工過程中,由于機器老化而不得不進行維修活動的恒同機問題.其中目標函數(shù)由最大完工時間的總和、總完工時間的總和與總等待時間的總和一起組成的,通過轉化目標函數(shù),使用匹配算法得出排序問題有多項式時間解,時間復雜度為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

【參考文獻】

相關期刊論文 前2條

1 謝秋蓮;張新功;;帶有線性位置惡化及維修區(qū)間的單機排序問題[J];重慶師范大學學報(自然科學版);2015年05期

2 張新功;;具有多個維修區(qū)間的單機調度問題[J];計算機工程與應用;2014年15期

，

本文編號：1983955