具有分段惡化效應(yīng)生產(chǎn)過程的智能優(yōu)化調(diào)度研究
發(fā)布時(shí)間：2018-07-17 15:02
【摘要】：調(diào)度問題旨在將有限的資源分配給各項(xiàng)不同的任務(wù),同時(shí)滿足特定的需求和約束,其廣泛存在于各類生產(chǎn)制造系統(tǒng)中。生產(chǎn)調(diào)度是制造系統(tǒng)中關(guān)鍵的決策過程之一,對其進(jìn)行優(yōu)化是車間管理的主要研究內(nèi)容。采用合理的調(diào)度方案安排生產(chǎn)是提高制造系統(tǒng)作業(yè)效率的有效手段。在傳統(tǒng)的生產(chǎn)調(diào)度問題中,通常認(rèn)為工件的加工時(shí)間固定不變。然而在某些實(shí)際制造和服務(wù)過程中,工件的加工時(shí)間會(huì)因其開工時(shí)刻、加工位置的不同而發(fā)生變化,與傳統(tǒng)調(diào)度問題相比生產(chǎn)過程具有惡化效應(yīng),由此產(chǎn)生了一類新的調(diào)度問題。該類問題中工件的加工時(shí)問由開工時(shí)刻、加工位置等因素的函數(shù)描述。若工件的加工時(shí)間由其開工時(shí)刻的分段線性函數(shù)和階梯函數(shù)刻畫,則稱其具有分段惡化效應(yīng)。此類問題較之傳統(tǒng)調(diào)度問題更加復(fù)雜,絕大多數(shù)是NP-hard的,通常無法在合理的時(shí)間內(nèi)求得最優(yōu)解,對這類調(diào)度問題設(shè)計(jì)有效的調(diào)度優(yōu)化方法具有重要的理論和現(xiàn)實(shí)意義。本文研究了分段線性惡化和階梯惡化這兩類效應(yīng)作用下的四個(gè)生產(chǎn)調(diào)度問題,給出了它們的復(fù)雜性分析。由于這些問題均是NP-hard的,難以在多項(xiàng)式時(shí)間內(nèi)獲得最優(yōu)解,為此基于最優(yōu)調(diào)度方案的結(jié)構(gòu)特征和性質(zhì)分析,設(shè)計(jì)了啟發(fā)式調(diào)度優(yōu)化算法。論文的主要研究內(nèi)容有：(1)研究了分段線性惡化效應(yīng)作用下以最大完工時(shí)間最小化為目標(biāo)的單機(jī)調(diào)度問題。此問題是強(qiáng)NP-hard的,無法通過多項(xiàng)式算法求解。在最優(yōu)解的結(jié)構(gòu)特征分析的基礎(chǔ)上,提出了基于SPT排序規(guī)則的啟發(fā)式算法DSPT-PI,同時(shí)引入了遺傳算法以獲得更高質(zhì)量的解。該遺傳算法使用DSPT和隨機(jī)序列相結(jié)合的方式產(chǎn)生初始種群,采用線性順序交叉算子和交換變異算子,并融入了成對互換搜索。基于隨機(jī)數(shù)值算例的仿真結(jié)果表明,啟發(fā)式算法DSPT-PI總體求解性能明顯好于已有的啟發(fā)式算法,遺傳算法的求解精度優(yōu)于模擬退火算法。(2)對于具有階梯惡化效應(yīng)的單機(jī)調(diào)度問題,研究了總延誤及總加權(quán)延誤兩種目標(biāo)函數(shù)。針對該問題,建立了混合整數(shù)規(guī)劃模型,證明了總延誤最小化問題為NP-hard的,分析了最優(yōu)解的性質(zhì),設(shè)計(jì)了基于修正交貨期的啟發(fā)式算法IMDD和簡單加權(quán)搜索算法SWSP。同時(shí)還證明了總加權(quán)延誤最小化問題為強(qiáng)NP-hard的,提出了通用變鄰域搜索算法GVNS進(jìn)行求解。利用隨機(jī)算例對算法的性能進(jìn)行了評估,分析發(fā)現(xiàn)GVNS能夠有效地求解該問題,當(dāng)求解大規(guī)模問題時(shí)給出的解的相對百分偏差為0.78%,相對平均偏差為0.81%。(3)研究了具有階梯惡化效應(yīng)的并行機(jī)調(diào)度問題,構(gòu)建了以總完工時(shí)間最小化為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型,研究了不同建模方式下優(yōu)化模型的求解效率。針對該問題,提出了改進(jìn)加權(quán)組合搜索算法MWCSA,并設(shè)計(jì)了基于工件序列編碼的變鄰域搜索算法VNS。同時(shí)為了提高搜索速度,利用MWCSA為VNS產(chǎn)生初始解以形成改進(jìn)算法VNS+MWCSA�；陔S機(jī)算例的大量仿真結(jié)果表明,混合整數(shù)規(guī)劃模型的求解效率依賴于惡化工期的取值區(qū)間,VNS+MWCSA算法的性能優(yōu)于其他算法。(4)研究了帶調(diào)整時(shí)間和階梯惡化效應(yīng)的并行機(jī)調(diào)度問題,以最小化總延誤為目標(biāo)函數(shù),建立了混合整數(shù)規(guī)劃模型。針對該問題,提出了一種混合離散布谷鳥搜索(HDCS)算法。該算法采用基于工件排列的離散編碼解碼方案,在種群初始化過程中融合了啟發(fā)式算法MBHG,在搜索過程中將種群劃分為普通解集和精英解集,對普通解實(shí)施基于CS的離散搜索,對精英解實(shí)施基于變鄰域下降的局部搜索。為了保持種群的多樣性,對部分個(gè)體采用了Restarting策略。算例求解結(jié)果表明混合算法HDCS是十分有效的,其求解效率受惡化工期取值的影響極小。本文針對分段惡化效應(yīng)作用下的生產(chǎn)過程,以單機(jī)和同速并行機(jī)為加工環(huán)境,考慮了最大完工時(shí)間、總延誤和總完工時(shí)間為優(yōu)化指標(biāo)的調(diào)度模型,并提出了相應(yīng)的求解方法。本文的研究豐富了具有惡化效應(yīng)調(diào)度問題的研究內(nèi)容,拓寬了此類問題的求解途徑,有助于推動(dòng)生產(chǎn)調(diào)度理論的發(fā)展,具有重要的理論意義和積極的實(shí)際意義。
[Abstract]:Scheduling problem is designed to allocate limited resources to different tasks and meet specific requirements and constraints. It is widely used in all kinds of manufacturing systems. Production scheduling is one of the key decision-making processes in the manufacturing system. Optimization is the main research content of workshop management. Production is an effective means to improve the efficiency of the manufacturing system. In the traditional production scheduling problem, the processing time of the workpiece is usually fixed. However, in some actual manufacturing and service processes, the processing time of the work piece will vary with the start time and the processing position, and the production process is compared with the traditional scheduling problem. A new kind of scheduling problem is produced. In this kind of problem, the processing time of the workpiece is described by the function description of the factors such as the start time and the machining position. If the processing time of the workpiece is depicted by the piecewise linear function and the ladder function at the start time of the work piece, it is called the piecewise deterioration effect. This kind of problem is compared with the traditional scheduling problem. The problem is more complex, most of which are NP-hard, usually can not obtain the optimal solution in a reasonable time. It is of great theoretical and practical significance to design an effective scheduling optimization method for this kind of scheduling problem. This paper studies four production scheduling problems under the action of piecewise linear deterioration and ladder deterioration, and gives it. Because these problems are all NP-hard, it is difficult to obtain the optimal solution in polynomial time. Therefore, based on the structural characteristics and properties of the optimal scheduling scheme, a heuristic scheduling optimization algorithm is designed. The main contents of this paper are as follows: (1) the maximum completion time under the effect of piecewise linear deterioration is studied. A single machine scheduling problem is minimized as a target. This problem is strong NP-hard and can not be solved by polynomial algorithm. Based on the analysis of the structural features of the optimal solution, a heuristic algorithm DSPT-PI based on the SPT ordering rule is proposed, and the genetic algorithm is introduced to obtain a higher qualitative solution. The genetic algorithm uses DSPT and random sequence. The initial population is generated by the combination of the linear sequence crossover operator and the exchange mutation operator. The simulation results based on the random numerical example show that the overall solution performance of the heuristic algorithm DSPT-PI is better than the existing heuristic algorithm, and the accuracy of the legacy algorithm is better than that of the simulated annealing algorithm (2). For the single machine scheduling problem with staircase degradation, two objective functions of total delay and total weighted delay are studied. A mixed integer programming model is established for this problem. It is proved that the problem of minimizing the total delay is NP-hard. The properties of the optimal solution are analyzed, and the heuristic algorithm IMDD and simple weighting for the base Yu Xiuzheng delivery period are designed. The search algorithm SWSP. also proves that the total weighted delay minimization problem is strong NP-hard. A general variable neighborhood search algorithm GVNS is proposed to solve the problem. The performance of the algorithm is evaluated by a random example. It is found that the GVNS can solve the problem effectively. The relative percentile deviation of the solution is 0. when the problem of the large norm model is solved. 78%, the relative average deviation is 0.81%. (3), the parallel machine scheduling problem with staircase degradation is studied. A mixed integer programming model is built to minimize the total completion time as the objective function. The efficiency of the optimization model is studied under different modeling methods. An improved weighted combination search algorithm (MWCSA) is proposed and the design of the improved weighted combination search algorithm is proposed. In order to improve the search speed based on the sequence coding of the work piece, VNS., in order to improve the search speed, produces an initial solution for VNS by MWCSA to form an improved algorithm, which is based on a large number of simulation results based on random examples. The efficiency of the mixed integer programming model is dependent on the value interval of the deteriorating period, and the performance of the VNS+MWCSA algorithm is excellent. In other algorithms (4) the parallel machine scheduling problem with adjustment time and staircase degradation is studied. In order to minimize the total delay as the objective function, a mixed integer programming model is established. A hybrid discrete cuckoo search (HDCS) algorithm is proposed for this problem. In the process of group initialization, the heuristic algorithm MBHG is fused. In the search process, the population is divided into common solution set and elite solution set. CS based discrete search is applied to ordinary solutions, and local search based on variable neighborhood descent is implemented for the elite solution. In order to maintain the diversity of the population, some individuals are used in Restarting strategy. The results show that the hybrid algorithm HDCS is very effective and its efficiency is very little affected by the time of the deteriorating work. In this paper, a scheduling model with the maximum completion time, the total delay and the total completion time is considered, and the corresponding scheduling model is taken into consideration in the production process under the effect of piecewise deterioration effect. The research in this paper enriches the research content of the problem of deteriorating effect scheduling, broadens the way to solve such problems, and helps to promote the development of production scheduling theory, which has important theoretical significance and positive practical significance.
【學(xué)位授予單位】：西南交通大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：TB497
本文編號：2130022
[Abstract]:Scheduling problem is designed to allocate limited resources to different tasks and meet specific requirements and constraints. It is widely used in all kinds of manufacturing systems. Production scheduling is one of the key decision-making processes in the manufacturing system. Optimization is the main research content of workshop management. Production is an effective means to improve the efficiency of the manufacturing system. In the traditional production scheduling problem, the processing time of the workpiece is usually fixed. However, in some actual manufacturing and service processes, the processing time of the work piece will vary with the start time and the processing position, and the production process is compared with the traditional scheduling problem. A new kind of scheduling problem is produced. In this kind of problem, the processing time of the workpiece is described by the function description of the factors such as the start time and the machining position. If the processing time of the workpiece is depicted by the piecewise linear function and the ladder function at the start time of the work piece, it is called the piecewise deterioration effect. This kind of problem is compared with the traditional scheduling problem. The problem is more complex, most of which are NP-hard, usually can not obtain the optimal solution in a reasonable time. It is of great theoretical and practical significance to design an effective scheduling optimization method for this kind of scheduling problem. This paper studies four production scheduling problems under the action of piecewise linear deterioration and ladder deterioration, and gives it. Because these problems are all NP-hard, it is difficult to obtain the optimal solution in polynomial time. Therefore, based on the structural characteristics and properties of the optimal scheduling scheme, a heuristic scheduling optimization algorithm is designed. The main contents of this paper are as follows: (1) the maximum completion time under the effect of piecewise linear deterioration is studied. A single machine scheduling problem is minimized as a target. This problem is strong NP-hard and can not be solved by polynomial algorithm. Based on the analysis of the structural features of the optimal solution, a heuristic algorithm DSPT-PI based on the SPT ordering rule is proposed, and the genetic algorithm is introduced to obtain a higher qualitative solution. The genetic algorithm uses DSPT and random sequence. The initial population is generated by the combination of the linear sequence crossover operator and the exchange mutation operator. The simulation results based on the random numerical example show that the overall solution performance of the heuristic algorithm DSPT-PI is better than the existing heuristic algorithm, and the accuracy of the legacy algorithm is better than that of the simulated annealing algorithm (2). For the single machine scheduling problem with staircase degradation, two objective functions of total delay and total weighted delay are studied. A mixed integer programming model is established for this problem. It is proved that the problem of minimizing the total delay is NP-hard. The properties of the optimal solution are analyzed, and the heuristic algorithm IMDD and simple weighting for the base Yu Xiuzheng delivery period are designed. The search algorithm SWSP. also proves that the total weighted delay minimization problem is strong NP-hard. A general variable neighborhood search algorithm GVNS is proposed to solve the problem. The performance of the algorithm is evaluated by a random example. It is found that the GVNS can solve the problem effectively. The relative percentile deviation of the solution is 0. when the problem of the large norm model is solved. 78%, the relative average deviation is 0.81%. (3), the parallel machine scheduling problem with staircase degradation is studied. A mixed integer programming model is built to minimize the total completion time as the objective function. The efficiency of the optimization model is studied under different modeling methods. An improved weighted combination search algorithm (MWCSA) is proposed and the design of the improved weighted combination search algorithm is proposed. In order to improve the search speed based on the sequence coding of the work piece, VNS., in order to improve the search speed, produces an initial solution for VNS by MWCSA to form an improved algorithm, which is based on a large number of simulation results based on random examples. The efficiency of the mixed integer programming model is dependent on the value interval of the deteriorating period, and the performance of the VNS+MWCSA algorithm is excellent. In other algorithms (4) the parallel machine scheduling problem with adjustment time and staircase degradation is studied. In order to minimize the total delay as the objective function, a mixed integer programming model is established. A hybrid discrete cuckoo search (HDCS) algorithm is proposed for this problem. In the process of group initialization, the heuristic algorithm MBHG is fused. In the search process, the population is divided into common solution set and elite solution set. CS based discrete search is applied to ordinary solutions, and local search based on variable neighborhood descent is implemented for the elite solution. In order to maintain the diversity of the population, some individuals are used in Restarting strategy. The results show that the hybrid algorithm HDCS is very effective and its efficiency is very little affected by the time of the deteriorating work. In this paper, a scheduling model with the maximum completion time, the total delay and the total completion time is considered, and the corresponding scheduling model is taken into consideration in the production process under the effect of piecewise deterioration effect. The research in this paper enriches the research content of the problem of deteriorating effect scheduling, broadens the way to solve such problems, and helps to promote the development of production scheduling theory, which has important theoretical significance and positive practical significance.
【學(xué)位授予單位】：西南交通大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：TB497
【參考文獻(xiàn)】
相關(guān)期刊論文 前8條
1 侯福均;吳祈宗;;應(yīng)用遺傳算法求解模糊參數(shù)的單機(jī)調(diào)度問題[J];北京理工大學(xué)學(xué)報(bào);2006年03期
2 王吉波,夏尊銓;工件加工時(shí)間是開工時(shí)間的簡單線性函數(shù)的Flow Shop調(diào)度問題研究[J];系統(tǒng)工程;2004年08期
3 于海斌,薛勁松,王浩波,徐心和;基于遺傳算法的單機(jī)提前/拖期調(diào)度方法研究[J];控制理論與應(yīng)用;2000年02期
4 劉民;;基于數(shù)據(jù)的生產(chǎn)過程調(diào)度方法研究綜述[J];自動(dòng)化學(xué)報(bào);2009年06期
5 杜利敏;阮奇;馮登科;;基于共軛梯度的布谷鳥搜索算法[J];計(jì)算機(jī)與應(yīng)用化學(xué);2013年04期
6 葉強(qiáng);劉心報(bào);程浩;;改進(jìn)蟻群算法求解單機(jī)總加權(quán)延遲調(diào)度問題[J];系統(tǒng)仿真學(xué)報(bào);2008年08期
7 馬英;左春榮;楊善林;;帶不可用時(shí)間段和惡化加工時(shí)間的單機(jī)調(diào)度[J];系統(tǒng)工程學(xué)報(bào);2010年03期
8 劉鵬;周曉曄;衣娜;;帶有減少線性惡化效應(yīng)的雙代理調(diào)度問題[J];系統(tǒng)工程學(xué)報(bào);2011年03期
相關(guān)博士學(xué)位論文 前1條
1 張新功;加工時(shí)間非常數(shù)的排序與調(diào)度模型研究[D];上海理工大學(xué);2010年
，本文編號：2130022
本文鏈接：http://sikaile.net/guanlilunwen/gongchengguanli/2130022.html
最近更新
教材專著
