【摘要】：生產(chǎn)調(diào)度問題是一類經(jīng)典的組合最優(yōu)化問題,研究如何合理分配和調(diào)度有限資源以獲得最大效益,在實(shí)際的生產(chǎn)中具有廣泛的應(yīng)用。高效的調(diào)度方案可以提高生產(chǎn)設(shè)備利用率、降低成本,增加企業(yè)的利潤。供應(yīng)鏈調(diào)度問題是生產(chǎn)調(diào)度問題的擴(kuò)展,研究的是供應(yīng)鏈的成員們(包括供應(yīng)商、制造商、分銷商和第三方物流等)在信息共享的基礎(chǔ)上,為了達(dá)到縮短產(chǎn)品交貨期,降低整條供應(yīng)鏈運(yùn)作成本的目標(biāo),實(shí)行聯(lián)合(或協(xié)同)的調(diào)度,對生產(chǎn)制造領(lǐng)域有著重要的研究價(jià)值。 首先,本文對供應(yīng)鏈調(diào)度問題的研究背景和意義進(jìn)行了歸納總結(jié)并對其國內(nèi)外研究現(xiàn)狀做了詳細(xì)介紹。 其次,對組合優(yōu)化問題、調(diào)度問題、相關(guān)算法及計(jì)算復(fù)雜性進(jìn)行了回顧,同時(shí)對于調(diào)度問題的求解思路以及本文所采用的主要算法做了簡單介紹。 然后,研究了帶有分批配送的供應(yīng)鏈調(diào)度問題。我們先對原始問題作了復(fù)雜性分析,證明了該問題是強(qiáng)NTP-hard問題；對于配送批次有常數(shù)上界的情形,我們證明了是一般的NP-hard問題,并設(shè)計(jì)了完全多項(xiàng)式時(shí)間算法(FPTAS)。另外,我們還研究了三個(gè)多項(xiàng)式可解的子問題,對每個(gè)子問題設(shè)計(jì)了相應(yīng)的多項(xiàng)式時(shí)間最優(yōu)算法,并通過計(jì)算實(shí)例,驗(yàn)證了算法的有效性。 接著,研究了具有惡化效應(yīng)的供應(yīng)鏈調(diào)度問題。同樣地,我們先對原始問題作了復(fù)雜性分析,證明了該問題是強(qiáng)NP-hard問題,并進(jìn)一步證明了該問題不存在常數(shù)最壞情況界的多項(xiàng)式時(shí)間算法,除非P=NP；對于到達(dá)批次有常數(shù)上界的情形,我們對其做了復(fù)雜性分析,證明了該問題仍然是強(qiáng)NP-hard問題,并設(shè)計(jì)了FPTAS。 最后,我們對兩個(gè)模型中設(shè)計(jì)的FPTAS通過數(shù)據(jù)試驗(yàn),采用MATLAB軟件對算法進(jìn)行編程,對隨機(jī)給定的實(shí)例找到了工件的最優(yōu)批次數(shù),每個(gè)批次工件的最優(yōu)加工順序,并求出了最優(yōu)目標(biāo)值,驗(yàn)證了FPTAS的有效性。
[Abstract]:Production scheduling problem is a classical combinatorial optimization problem. It is widely used in practical production to study how to reasonably allocate and schedule finite resources to obtain maximum benefit. The efficient scheduling scheme can increase the utilization rate of production equipment, reduce the cost and increase the profit of the enterprise. The supply chain scheduling problem is an extension of the production scheduling problem. In order to shorten the product delivery time, the members of the supply chain (including suppliers, manufacturers, distributors and third party logistics, etc.) are studied on the basis of information sharing. To reduce the operation cost of the whole supply chain and to implement joint (or cooperative) scheduling has important research value in the field of production and manufacturing. Firstly, this paper summarizes the research background and significance of supply chain scheduling problem and introduces the current situation of supply chain scheduling problem at home and abroad. Secondly, the combinatorial optimization problem, scheduling problem, related algorithms and computational complexity are reviewed, and the idea of solving the scheduling problem and the main algorithms used in this paper are briefly introduced. Then, the supply chain scheduling problem with batch distribution is studied. We first analyze the complexity of the original problem and prove that the problem is a strong NTP-hard problem, and for the case where the distribution lot has a constant upper bound, we prove that it is a general NP-hard problem, and design a complete polynomial time algorithm (FPTAS). In addition, we also study three polynomial solvable subproblems, design corresponding polynomial time optimal algorithm for each subproblem, and verify the validity of the algorithm by an example. Then, the supply chain scheduling problem with deterioration effect is studied. Similarly, we first analyze the complexity of the original problem, prove that the problem is a strong NP-hard problem, and further prove that the problem does not have a polynomial time algorithm for the worst-case bound of constants, unless the problem is a NP-hard problem. For the case where the batch has a constant upper bound, we analyze its complexity, prove that the problem is still a strong NP-hard problem, and design a FPTAS. Finally, the FPTAS designed in the two models is tested by data, and the algorithm is programmed by MATLAB software. The optimal batch number of the workpiece and the optimal processing order of each batch are found for the random given instance. The optimal target value is obtained, and the validity of FPTAS is verified.
【學(xué)位授予單位】：浙江工商大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：F274;F272

【參考文獻(xiàn)】

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

1 劉靜;閔嘯;;一個(gè)帶退化工件的單機(jī)準(zhǔn)時(shí)生產(chǎn)制問題[J];浙江大學(xué)學(xué)報(bào)(理學(xué)版);2010年01期

2 孫鑫;陳秋雙;龍磊;徐海濤;;三層供應(yīng)鏈聯(lián)合調(diào)度算法研究[J];計(jì)算機(jī)集成制造系統(tǒng);2006年04期

3 李芳;邱俊茹;葉春明;鄭晴;;基于供應(yīng)鏈的協(xié)同生產(chǎn)調(diào)度研究發(fā)展現(xiàn)狀與展望[J];計(jì)算機(jī)應(yīng)用研究;2010年11期

，

本文編號：2173915