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

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

【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

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

2 張新功;;具有多個(gè)維修區(qū)間的單機(jī)調(diào)度問(wèn)題[J];計(jì)算機(jī)工程與應(yīng)用;2014年15期

，

本文編號(hào)：1983954