發(fā)布時(shí)間：2018-08-02 11:08

【摘要】：制造和物流系統(tǒng)中的物流時(shí)間與空間調(diào)度問題可以歸結(jié)為整數(shù)規(guī)劃問題。Branch-and-Cut算法是目前最優(yōu)求解整數(shù)規(guī)劃問題的有效算法之一,其基本思想為利用分支定界算法的框架結(jié)構(gòu),在其構(gòu)建的分支定界樹中的葉子節(jié)點(diǎn)處增加有效不等式用以動態(tài)提升下界(最小化問題),達(dá)到減少分支定界樹分支個(gè)數(shù),提高算法求解效率的目的。由于整數(shù)規(guī)劃問題大多屬于NP-難題,因此,研究Branch-and-Cut算法的改進(jìn)對整數(shù)規(guī)劃的最優(yōu)求解的規(guī)模和效率的提升具有重要意義。本文首先以物流系統(tǒng)時(shí)間調(diào)度中的典型吊機(jī)調(diào)度問題為背景,對Branch-and-Cut算法進(jìn)行了方法研究,以工廠吊機(jī)調(diào)度為背景進(jìn)行了方法的應(yīng)用研究。然后,以圖論中的經(jīng)典圖著色問題為背景,對Branch-and-Cut算法進(jìn)行了方法研究,并以物流系統(tǒng)的空間調(diào)度中的板坯入庫垛位決策問題為背景進(jìn)行了應(yīng)用研究。論文主要工作及研究成果概述如下：1)典型吊機(jī)調(diào)度問題：對于由M個(gè)吊機(jī)完成N(MN)個(gè)去向已知的待運(yùn)任務(wù),需要確定任務(wù)在吊機(jī)上的分配以及在所分配吊機(jī)上的執(zhí)行順序,在保證吊機(jī)任務(wù)之間的優(yōu)先關(guān)系要求以及避免吊機(jī)間發(fā)生交叉和碰撞的同時(shí),使得完成全部任務(wù)所需的時(shí)間最短。對該問題的整數(shù)線性規(guī)劃模型采用Branch-and-Cut算法求解�；�于問題特點(diǎn)的分析提出了有效不等式,并設(shè)計(jì)了改進(jìn)的基于禁忌搜索方法的分離策略用于有效不等式的發(fā)現(xiàn)。數(shù)值實(shí)驗(yàn)的結(jié)果表明了所提算法的有效性。2)板坯庫吊機(jī)調(diào)度問題：對于由M個(gè)吊機(jī)完成N(MN)個(gè)工件的出庫操作,將每個(gè)工件的連續(xù)(不中斷)出庫操作定義為一個(gè)任務(wù),需要決策出庫操作是否中斷及全部任務(wù)在吊機(jī)上的分配及執(zhí)行順序,在滿足完工順序、避免吊機(jī)間交叉和碰撞、任務(wù)在緩沖垛位的服務(wù)規(guī)則等要求的情況下,使得所有任務(wù)的完成時(shí)間短。針對該問題建立了初始的整數(shù)規(guī)劃模型,基于對問題性質(zhì)分析對模型進(jìn)行重建�；�于具有緊下界的重建模型,設(shè)計(jì)了Branch-and-Cut算法求解。在算法實(shí)施中,提出了多類有效不等式用于提升問題下界,同時(shí),引進(jìn)變量降低技術(shù)以有效降低搜索域,進(jìn)而提高算法的搜索效率�；�于工業(yè)實(shí)際數(shù)據(jù)的數(shù)值實(shí)驗(yàn)證明了所提出算法能夠在合理的時(shí)間內(nèi)獲得工業(yè)問題規(guī)模的最優(yōu)解,其性能明顯優(yōu)于商業(yè)優(yōu)化求解軟件CPLEX,驗(yàn)證了提出的模型和算法的有效性。3)典型圖論優(yōu)化問題——圖著色問題：對給定的圖內(nèi)的每一個(gè)頂點(diǎn)著一種顏色,在保證任意相連的兩點(diǎn)著不同顏色的要求下,決策所需要的最少顏色個(gè)數(shù)。針對該問題建立了整數(shù)線性規(guī)劃模型,設(shè)計(jì)了Branch-and-Cut算法進(jìn)行最優(yōu)求解。針對此問題,提出了變量固定策略用于削減可行域,構(gòu)造了基于動態(tài)規(guī)劃的有效不等式,嵌入了基于獨(dú)立集的有效不等式、基于團(tuán)的有效不等式,有效地提高了Branch-and-Cut算法收斂速度。通過Benchmark標(biāo)準(zhǔn)測試數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明了提出的算法的有效性。4)基于圖著色的板坯入庫垛位決策問題：對于板坯庫入庫的板坯,需要決策存放的垛位位置,在保證板坯按照出庫順序提取時(shí)不產(chǎn)生倒垛操作的要求下,使得占用的垛位數(shù)最少。該問題通過歸結(jié)為圖著色問題進(jìn)行建模,將入庫板坯定義為頂點(diǎn),板坯入出庫順序定義為邊,同一垛位的板坯集合定義為圖中著同樣顏色的點(diǎn)的集合,最少占用垛位數(shù)對應(yīng)于最少使用的顏色數(shù)。通過圖著色問題建立的板坯入庫垛位決策問題模型,可以直接應(yīng)用提出的Branch-and-Cut算法進(jìn)行求解。數(shù)值實(shí)驗(yàn)驗(yàn)證了該問題基于圖著色建模方法的有效性。5)以國內(nèi)某大型鋼鐵企業(yè)的板坯庫物流作業(yè)為背景,以上述板坯庫吊機(jī)調(diào)度問題和板坯入庫垛位決策問題模型和算法為內(nèi)核,開發(fā)了板坯庫物流優(yōu)化決策支持系統(tǒng)。通過實(shí)際數(shù)據(jù)的應(yīng)用驗(yàn)證,數(shù)值結(jié)果表明了所開發(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.
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：F402;F252;TP301.6

【相似文獻(xiàn)】

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

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

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

3 劉琳;谷寒雨;席裕庚;;工件到達(dá)時(shí)間未知的動態(tài)車間滾動重調(diào)度[J];機(jī)械工程學(xué)報(bào);2008年05期

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

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

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

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

8 王中杰,吳啟迪,有杰;基于多目標(biāo)的半導(dǎo)體生產(chǎn)線滿意調(diào)度[J];控制與決策;2002年06期

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

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

相關(guān)會議論文 前10條

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

2 劉海龍;黃小原;;總的未完工費(fèi)用最小的多機(jī)調(diào)度問題[A];1995中國控制與決策學(xué)術(shù)年會論文集[C];1995年

3 沈吟東;曾西洋;;公共交通駕駛員調(diào)度的復(fù)雜性及解決方法[A];’2004計(jì)算機(jī)應(yīng)用技術(shù)交流會議論文集[C];2004年

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

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

6 王成堯;汪定偉;;模糊加工時(shí)間的單機(jī)調(diào)度問題[A];1996中國控制與決策學(xué)術(shù)年會論文集[C];1996年

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

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

9 方濤;吳受章;;FMS的自適應(yīng)調(diào)度:結(jié)構(gòu)與算法研究[A];1992年中國控制與決策學(xué)術(shù)年會論文集[C];1992年

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

相關(guān)重要報(bào)紙文章 前2條

1 本報(bào)記者 賈科華;火電機(jī)組叫苦調(diào)度不合理[N];中國能源報(bào);2012年

2 本報(bào)記者 高芳;牽住“牛鼻子” 巧解“推進(jìn)難”[N];湖南經(jīng)濟(jì)報(bào);2008年

相關(guān)博士學(xué)位論文 前10條

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

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

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

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

5 周理;高效可重構(gòu)陣列計(jì)算：體系結(jié)構(gòu)，設(shè)計(jì)方法與程序映射技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2014年

6 馮大光;一類批處理機(jī)調(diào)度的理論和方法研究[D];東北大學(xué);2011年

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

8 楊磊;內(nèi)容網(wǎng)絡(luò)中內(nèi)容調(diào)度技術(shù)研究[D];重慶大學(xué);2015年

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

10 丁寧;若干調(diào)度問題的算法研究[D];大連理工大學(xué);2016年

相關(guān)碩士學(xué)位論文 前10條

1 張亮;云計(jì)算環(huán)境下的資源調(diào)度技術(shù)的研究[D];江南大學(xué);2015年

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

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

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

5 張勇;帶拒絕和釋放時(shí)間的單機(jī)批調(diào)度問題[D];山東大學(xué);2015年

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

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

8 吉佳紅;基于細(xì)菌覓食算法的改進(jìn)及應(yīng)用研究[D];江蘇科技大學(xué);2015年

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

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

，

本文編號：2159232