【摘要】：制造和物流系統(tǒng)中的物流時間與空間調度問題可以歸結為整數(shù)規(guī)劃問題。Branch-and-Cut算法是目前最優(yōu)求解整數(shù)規(guī)劃問題的有效算法之一,其基本思想為利用分支定界算法的框架結構,在其構建的分支定界樹中的葉子節(jié)點處增加有效不等式用以動態(tài)提升下界(最小化問題),達到減少分支定界樹分支個數(shù),提高算法求解效率的目的。由于整數(shù)規(guī)劃問題大多屬于NP-難題,因此,研究Branch-and-Cut算法的改進對整數(shù)規(guī)劃的最優(yōu)求解的規(guī)模和效率的提升具有重要意義。本文首先以物流系統(tǒng)時間調度中的典型吊機調度問題為背景,對Branch-and-Cut算法進行了方法研究,以工廠吊機調度為背景進行了方法的應用研究。然后,以圖論中的經典圖著色問題為背景,對Branch-and-Cut算法進行了方法研究,并以物流系統(tǒng)的空間調度中的板坯入庫垛位決策問題為背景進行了應用研究。論文主要工作及研究成果概述如下：1)典型吊機調度問題：對于由M個吊機完成N(MN)個去向已知的待運任務,需要確定任務在吊機上的分配以及在所分配吊機上的執(zhí)行順序,在保證吊機任務之間的優(yōu)先關系要求以及避免吊機間發(fā)生交叉和碰撞的同時,使得完成全部任務所需的時間最短。對該問題的整數(shù)線性規(guī)劃模型采用Branch-and-Cut算法求解�；趩栴}特點的分析提出了有效不等式,并設計了改進的基于禁忌搜索方法的分離策略用于有效不等式的發(fā)現(xiàn)。數(shù)值實驗的結果表明了所提算法的有效性。2)板坯庫吊機調度問題：對于由M個吊機完成N(MN)個工件的出庫操作,將每個工件的連續(xù)(不中斷)出庫操作定義為一個任務,需要決策出庫操作是否中斷及全部任務在吊機上的分配及執(zhí)行順序,在滿足完工順序、避免吊機間交叉和碰撞、任務在緩沖垛位的服務規(guī)則等要求的情況下,使得所有任務的完成時間短。針對該問題建立了初始的整數(shù)規(guī)劃模型,基于對問題性質分析對模型進行重建。基于具有緊下界的重建模型,設計了Branch-and-Cut算法求解。在算法實施中,提出了多類有效不等式用于提升問題下界,同時,引進變量降低技術以有效降低搜索域,進而提高算法的搜索效率�；诠I(yè)實際數(shù)據的數(shù)值實驗證明了所提出算法能夠在合理的時間內獲得工業(yè)問題規(guī)模的最優(yōu)解,其性能明顯優(yōu)于商業(yè)優(yōu)化求解軟件CPLEX,驗證了提出的模型和算法的有效性。3)典型圖論優(yōu)化問題——圖著色問題：對給定的圖內的每一個頂點著一種顏色,在保證任意相連的兩點著不同顏色的要求下,決策所需要的最少顏色個數(shù)。針對該問題建立了整數(shù)線性規(guī)劃模型,設計了Branch-and-Cut算法進行最優(yōu)求解。針對此問題,提出了變量固定策略用于削減可行域,構造了基于動態(tài)規(guī)劃的有效不等式,嵌入了基于獨立集的有效不等式、基于團的有效不等式,有效地提高了Branch-and-Cut算法收斂速度。通過Benchmark標準測試數(shù)據的實驗結果表明了提出的算法的有效性。4)基于圖著色的板坯入庫垛位決策問題：對于板坯庫入庫的板坯,需要決策存放的垛位位置,在保證板坯按照出庫順序提取時不產生倒垛操作的要求下,使得占用的垛位數(shù)最少。該問題通過歸結為圖著色問題進行建模,將入庫板坯定義為頂點,板坯入出庫順序定義為邊,同一垛位的板坯集合定義為圖中著同樣顏色的點的集合,最少占用垛位數(shù)對應于最少使用的顏色數(shù)。通過圖著色問題建立的板坯入庫垛位決策問題模型,可以直接應用提出的Branch-and-Cut算法進行求解。數(shù)值實驗驗證了該問題基于圖著色建模方法的有效性。5)以國內某大型鋼鐵企業(yè)的板坯庫物流作業(yè)為背景,以上述板坯庫吊機調度問題和板坯入庫垛位決策問題模型和算法為內核,開發(fā)了板坯庫物流優(yōu)化決策支持系統(tǒng)。通過實際數(shù)據的應用驗證,數(shù)值結果表明了所開發(fā)的模型及算法的性能優(yōu)于流行的商業(yè)軟件和手工編制作業(yè)方法。
[Abstract]:The problem of logistics time and spatial scheduling in manufacturing and logistics systems can be attributed to the integer programming problem..Branch-and-Cut algorithm is one of the most effective algorithms to solve the problem of integer programming. The basic idea is to use the framework of the branch and bound algorithm to increase the effectiveness of the leaf nodes in the branch and bound tree. The equation is used to dynamically elevate the lower bound (minimization problem) to reduce the number of branches of the branch and bound tree and improve the efficiency of the algorithm. As the integer programming problem is most of the NP- problem, it is of great significance to study the improvement of the Branch-and-Cut algorithm for the improvement of the scale and efficiency of the optimal solution of integer programming. Taking the typical crane scheduling problem in the time scheduling of logistics system as the background, the method of Branch-and-Cut algorithm is studied. The application of the method is studied with the factory crane scheduling as the background. Then, with the background of the classic graph coloring problem in the graph theory, the method of Branch-and-Cut calculation is studied, and the space of the logistics system is used. The main work of the paper and the research results are summarized as follows: 1) the scheduling problem of typical crane: for the M crane to complete the known N (MN) task, it is necessary to determine the assignment of the task on the crane and the order of execution on the distributed crane. The priority relation between the tasks of the crane and the avoidance of crossover and collision between the cranes, the shortest time needed to complete the complete task is made. The integer linear programming model of this problem is solved by Branch-and-Cut algorithm. An effective inequality based on the analysis of the problem characteristics is proposed, and an improved taboo based on the taboo is designed. The separation strategy of the search method is used for the discovery of effective inequalities. The results of the numerical experiment show the effectiveness of the proposed algorithm.2) the scheduling problem of the slab crane crane: the continuous (uninterrupted) outgoing operation of each work piece is defined as a task for the output of the N (MN) workpieces by the M crane. The distribution and execution order of the interruption and all tasks on the crane, in order to satisfy the completion order, avoid the intersect and collision between the hoists and the requirements of the service rules of the buffer stacks, make the completion time of all the tasks short. Row reconstruction. Based on the reconstruction model with tight lower bounds, the Branch-and-Cut algorithm is designed. In the implementation of the algorithm, a multi class effective inequality is proposed to improve the lower bounds of the problem. At the same time, the introduction of variable reduction technology is introduced to effectively reduce the search domain and improve the search efficiency. Numerical experiments based on industrial actual data prove that It is proposed that the algorithm can obtain the optimal solution of the scale of the industrial problem in a reasonable time, its performance is obviously superior to the commercial optimization solution software CPLEX, validates the validity of the proposed model and algorithm.3) the typical graph theory optimization problem - the graph coloring problem: a color for each vertex in a given graph is guaranteed to be arbitrarily connected. At the request of different colors, the least number of colors required by the decision is required. An integer linear programming model is established for the problem. The optimal solution of the Branch-and-Cut algorithm is designed. A variable fixed strategy is proposed to reduce the feasible domain and constructs an effective inequality based on dynamic programming. The effective inequalities of the erect set, based on the effective inequality of the regiment, effectively improve the convergence speed of the Branch-and-Cut algorithm. The experimental results of the Benchmark standard test data show the effectiveness of the proposed algorithm.4) based on the graph coloured slab entry position decision problem: the slab storage for the slab library needs decision storage Position position, in order to ensure that the slab is extracted in the order of out of the storehouse, does not produce the reverse stacking operation, which makes the occupying digits least. The problem is modeled by the graph coloring problem, and the storeboard is defined as the vertex, the slab is defined as the edge, and the stack of the same stacks is defined as the point in the same color. The minimum occupancy of the stacking number corresponds to the least used color number. The model of the slab storage position decision problem established by the graph coloring problem can be solved directly by the proposed Branch-and-Cut algorithm. The numerical experiment shows that the problem is based on the validity of the graph coloring modeling method.5) in a large steel enterprise in China. In the background of slab storehouse logistics operation, the logistics optimization decision support system of slab storehouse is developed based on the scheduling problem of slab hanger crane and the model and algorithm of slab storage staging decision problem. The application verification of actual data shows that the performance of the developed model and algorithm is superior to the popular commercial software and hand. The manufacturing method of the industrial editor.
【學位授予單位】：東北大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：F402;F252;TP301.6

【相似文獻】

相關期刊論文 前10條

1 劉文濤,張群,孫肅清;關于煉鋼廠重調度問題的研究[J];冶金自動化;2004年06期

2 張居陽 ,禮欣 ,孫吉貴;基于約束的調度研究和實現(xiàn)[J];計算機工程與應用;2004年33期

3 劉琳;谷寒雨;席裕庚;;工件到達時間未知的動態(tài)車間滾動重調度[J];機械工程學報;2008年05期

4 黃峰;丁亞武;;人機協(xié)同模式下的手工調度技術研究[J];黑龍江科技信息;2011年35期

5 郭艷東;黃敏;王慶;;鎖定初始調度的緊急工作單機重調度問題[J];東北大學學報(自然科學版);2013年05期

6 姜洋;孫偉;丁秋雷;張旭;;考慮行為主體的單機調度干擾管理模型[J];機械工程學報;2013年14期

7 李向軍,王書振;網絡化集成制造模式下調度問題的混合遺傳算法[J];西安聯(lián)合大學學報;2002年04期

8 王中杰,吳啟迪,有杰;基于多目標的半導體生產線滿意調度[J];控制與決策;2002年06期

9 李云峰;凌曉冬;武小悅;;調度問題中的沖突研究[J];兵工自動化;2007年06期

10 徐群嶺;;基于免疫優(yōu)化的公交駕駛員調度問題[J];計算機工程;2010年24期

相關會議論文 前10條

1 李建更;涂凍生;馬海濤;;單機拖后時間總和問題交付期擾動時最優(yōu)調度不變范圍的一種求法[A];第十九屆中國控制會議論文集（一）[C];2000年

2 劉海龍;黃小原;;總的未完工費用最小的多機調度問題[A];1995中國控制與決策學術年會論文集[C];1995年

3 沈吟東;曾西洋;;公共交通駕駛員調度的復雜性及解決方法[A];’2004計算機應用技術交流會議論文集[C];2004年

4 李兵;蔣慰孫;;Job shop問題的建模及調度[A];1996中國控制與決策學術年會論文集[C];1996年

5 王海星;申金升;;智能蟻群算法解決公交區(qū)域調度問題研究[A];2006年首屆ICT大會信息、知識、智能及其轉換理論第一次高峰論壇會議論文集[C];2006年

6 王成堯;汪定偉;;模糊加工時間的單機調度問題[A];1996中國控制與決策學術年會論文集[C];1996年

7 齊向彤;涂奉生;;雙交付期E／T調度問題[A];1997年中國控制會議論文集[C];1997年

8 吳斌;方葉祥;崔志勇;;基于人工蜂群算法的越庫調度問題研究[A];第25屆中國控制與決策會議論文集[C];2013年

9 方濤;吳受章;;FMS的自適應調度:結構與算法研究[A];1992年中國控制與決策學術年會論文集[C];1992年

10 劉興初;趙千川;鄭大鐘;;具有不同準備時間和交付期的單機E／T調度問題研究[A];1998年中國控制會議論文集[C];1998年

相關重要報紙文章 前2條

1 本報記者 賈科華;火電機組叫苦調度不合理[N];中國能源報;2012年

2 本報記者 高芳;牽住“牛鼻子” 巧解“推進難”[N];湖南經濟報;2008年

相關博士學位論文 前10條

1 郭鵬;具有分段惡化效應生產過程的智能優(yōu)化調度研究[D];西南交通大學;2014年

2 元野;基于圖著色模型的零擔物流調度優(yōu)化問題研究[D];哈爾濱工業(yè)大學;2015年

3 李雪松;模糊環(huán)境下若干單機批加工調度問題的模型及其算法研究[D];哈爾濱工業(yè)大學;2015年

4 湯雅連;關聯(lián)物流運輸調度問題研究[D];廣東工業(yè)大學;2015年

5 周理;高效可重構陣列計算：體系結構，設計方法與程序映射技術研究[D];國防科學技術大學;2014年

6 馮大光;一類批處理機調度的理論和方法研究[D];東北大學;2011年

7 孟盈;鋼鐵企業(yè)并行批生產決策與調度問題研究[D];東北大學;2011年

8 楊磊;內容網絡中內容調度技術研究[D];重慶大學;2015年

9 李亞志;流水制造單元調度智能優(yōu)化方法[D];東南大學;2015年

10 丁寧;若干調度問題的算法研究[D];大連理工大學;2016年

相關碩士學位論文 前10條

1 張亮;云計算環(huán)境下的資源調度技術的研究[D];江南大學;2015年

2 馮卓鵬;重載運輸卸車組織優(yōu)化研究[D];西南交通大學;2015年

3 崔雪源;基于遺傳模擬退火算法的航班著陸調度問題[D];華中師范大學;2015年

4 王翠;基于超圖模型和相繼干擾消除的鏈路調度問題的研究[D];曲阜師范大學;2015年

5 張勇;帶拒絕和釋放時間的單機批調度問題[D];山東大學;2015年

6 吳凡;基于粒子群優(yōu)化算法的風電-火電機組組合調度研究[D];華北電力大學;2015年

7 趙虎;MTO模式下的制造企業(yè)穩(wěn)健型調度問題研究[D];重慶理工大學;2015年

8 吉佳紅;基于細菌覓食算法的改進及應用研究[D];江蘇科技大學;2015年

9 周超;柔性作業(yè)車間批量問題研究[D];寧波大學;2014年

10 趙興野;工序順序柔性作業(yè)車間描述與調度研究[D];大連理工大學;2015年

，

本文編號：2159232