本文關(guān)鍵詞： 冷鏈 投送期 流水作業(yè) 訂單排序 近似算法　出處：《魯東大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：隨著社會的迅速發(fā)展,人們對物質(zhì)生活的追求也隨之提高,他們對食物也有了更高的要求,特別是對冷鮮的肉食.由于人們對食品安全和營養(yǎng)價值的較高追求,他們會更傾向于購買大型企業(yè)生產(chǎn)的品牌產(chǎn)品.為此,企業(yè)決策者們?yōu)榱苏袛埜嗟目蛻?希望通過采取一些措施達(dá)到既降低成本又能提高服務(wù)質(zhì)量.但是,在實際的冷鏈加工業(yè)中,二者很難同時實現(xiàn),由此會產(chǎn)生一些不好的效果,如:缺貨率高,配送延誤,產(chǎn)品品質(zhì)降低等,從而會使市場額下降.在此背景下,冷鏈加工業(yè)中的排序問題引起了學(xué)者們的廣泛關(guān)注.如何既能滿足不同客戶的特殊需要又能使企業(yè)的損失達(dá)到最小,找到一個行之有效的方法,能夠快速的協(xié)同安排生產(chǎn)和配送是即將要解決的問題.本文考慮的是幾類基于冷鏈加工的訂單排序模型.對于不同的機(jī)器環(huán)境和目標(biāo)函數(shù)設(shè)計了近似算法.本文的主要內(nèi)容如下:1.針對有固定投送期與存儲費用的單機(jī)環(huán)境下的訂單排序模型,考慮的問題是極小化工件最大完工時間和存儲費用的加權(quán)和這一問題.利用3-劃分證明了問題的一般情形是強(qiáng)NP-困難的,并證明沒有固定近似比的多項式時間的算法.對于投送期呈周期性這一特殊情形,提出了一個3/2-近似的算法,同時證明了該近似比是最好的,除非P=NP.2.針對有就緒時間的流水作業(yè)(flowshop)訂單排序模型,研究了極小化時間表長(makespan)問題.文章將訂單進(jìn)行了分批考慮,對于訂單有固定就緒時間的情形,利用2-劃分證明了問題是一般NP-困難的.提出了一個偽多項式時間的動態(tài)規(guī)劃算法,并根據(jù)改善的Johnson規(guī)則設(shè)計了2-近似的算法.針對問題的特殊情形,基于Johnson規(guī)則,提出了2-近似算法并進(jìn)一步改進(jìn)算法,設(shè)計了3/2-近似的算法.最后考慮了一個批有固定數(shù)目的情形,并設(shè)計了一個簡單的算法.
[Abstract]:With the rapid development of society, the pursuit of material life is increased, they also have higher demand for food, especially for cold fresh. Because the people of carnivorous higher food safety and nutritional value of the pursuit, they will be more inclined to buy large enterprises producing brand products. Therefore, the enterprise decision researchers in order to attract more customers, hopes to take some measures to reduce the cost and improve the quality of service. However, in the cold chain industry practice, the two is difficult to realized at the same time, it will produce some bad effects, such as: high rate of out of stock, delivery delays, reduce product quality, thus the market volume decreased. Under this background, the sort of cold chain in processing industry has aroused wide attention from scholars. How to meet the special needs of different customers and can make the enterprise loss minimum, find a The effective method to quickly arrange the production and distribution of cooperation is going to solve the problem. This paper is concerned with several models of order scheduling based on cold chain processing. For different machine environment and design target function approximation algorithm. The main contents of this paper are as follows: 1. according to a fixed order scheduling model of delivery and storage period the cost of a single machine environment, consider the problem is minimizing the maximum completion time and storage cost and weighted the problem. By using the 3- division shows that the general problem is strongly NP- hard, and prove that there is no fixed polynomial time approximate ratio algorithm. For a special case of the delivery period periodically, propose a 3/2- approximation algorithm, and proves that the approximation ratio is the best, unless P=NP.2. for ready time line (flowshop) ordering model, research To minimize makespan (makespan). The order of partial consideration, a fixed ready time in the case of orders, using 2- division shows that the problem is generally difficult. NP- proposed a dynamic programming algorithm for pseudo polynomial time, and the design of the 2- approximation algorithm based on improved Johnson special case rules. In order to solve the problem, based on the rules of Johnson, put forward 2- algorithm and improved algorithm, 3/2- approximation algorithm design. Finally we consider a number of fixed number of cases, and a simple algorithm design.

【學(xué)位授予單位】：魯東大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O223

【相似文獻(xiàn)】

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

1 黃春毅;董笑菊;龍環(huán);;用P系統(tǒng)解決排序問題[J];上海交通大學(xué)學(xué)報;2008年02期

2 姜振多;孫世杰;吳志剛;;排序問題的穩(wěn)定性分析(英文)[J];Journal of Shanghai University(English Edition);2008年01期

3 譚素平;;排序問題的分類與特點[J];科技信息;2012年36期

4 越民義,韓繼業(yè);排序問題中的一些數(shù)學(xué)問題[J];數(shù)學(xué)的實踐與認(rèn)識;1976年03期

5 越民義,韓繼業(yè);同順序m×n排序問題的一個新方法[J];科學(xué)通報;1979年18期

6 吳家強(qiáng);用分段選優(yōu)法求解“排序問題”[J];武漢水利電力學(xué)院學(xué)報;1979年03期

7 戴志勇;;一類排序問題最優(yōu)工序定義的等價性[J];武漢鋼鐵學(xué)院學(xué)報;1979年02期

8 韓繼業(yè);排序問題的一個判別條件和一類特殊的m×n排序問題[J];應(yīng)用數(shù)學(xué)學(xué)報;1980年04期

9 吳在德;梁學(xué)信;;排序問題計算加工時間的一種方法及其一個應(yīng)用[J];華僑大學(xué)學(xué)報;1981年01期

10 葉懋冬;;關(guān)于過竿問題與多臺機(jī)床上零件加工的排序問題(Ⅰ)[J];浙江大學(xué)學(xué)報;1982年04期

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

1 柏孟卓;唐國春;;加工時間可控的同時加工排序問題[A];2006年中國運籌學(xué)會數(shù)學(xué)規(guī)劃分會代表會議暨第六屆學(xué)術(shù)會議論文集[C];2006年

2 張蓮珠;;關(guān)于六角鏈的極值和排序問題的一些結(jié)果[A];中國運籌學(xué)會第六屆學(xué)術(shù)交流會論文集（上卷）[C];2000年

3 周支立;李懷祖;;有重疊區(qū)域的兩抓鉤周期性排序問題的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孫世杰;陳躍;;參數(shù)可控的排序問題[A];2001年全國數(shù)學(xué)規(guī)劃及運籌研討會論文集[C];2001年

5 張玉忠;;分批排序問題研究[A];中國運籌學(xué)會第七屆學(xué)術(shù)交流會論文集（上卷）[C];2004年

6 張玉忠;;分批排序問題研究[A];中國運籌學(xué)會第七屆學(xué)術(shù)交流會論文集（中卷）[C];2004年

7 譚萬達(dá);;二元對比排序中的最少逆序原理[A];中國系統(tǒng)工程學(xué)會模糊數(shù)學(xué)與模糊系統(tǒng)委員會第五屆年會論文選集[C];1990年

8 呂緒華;楊漢興;;求解裝配式排序問題的歸并算法及其性能比研究[A];中國運籌學(xué)會第六屆學(xué)術(shù)交流會論文集（下卷）[C];2000年

9 樊保強(qiáng);;帶倉儲約束的準(zhǔn)時排序問題[A];中國運籌學(xué)會第九屆學(xué)術(shù)交流會論文集[C];2008年

10 陳榮軍;唐國春;;自由作業(yè)環(huán)境下的供應(yīng)鏈排序問題[A];中國運籌學(xué)會第九屆學(xué)術(shù)交流會論文集[C];2008年

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

1 高強(qiáng);一些現(xiàn)代排序問題的算法設(shè)計與分析[D];華東理工大學(xué);2015年

2 谷存昌;工件的加工和配送協(xié)作排序問題[D];曲阜師范大學(xué);2015年

3 殷娜;依賴于資源分配的排序問題研究[D];上海大學(xué);2015年

4 仲維亞;供應(yīng)鏈管理中的若干排序問題研究[D];浙江大學(xué);2008年

5 尹曉;基因組重組排序問題的算法研究[D];山東大學(xué);2010年

6 余煒;若干網(wǎng)絡(luò)排序問題的算法和復(fù)雜性研究[D];華東理工大學(xué);2010年

7 張安;帶服務(wù)等級的在線排序問題及相關(guān)問題研究[D];浙江大學(xué);2009年

8 鄭睿;鋼鐵生產(chǎn)中的批處理機(jī)作業(yè)排序問題算法研究[D];復(fù)旦大學(xué);2009年

9 季敏;當(dāng)代工業(yè)中的若干排序問題研究[D];浙江大學(xué);2006年

10 李好好;若干排序問題研究[D];浙江大學(xué);2014年

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

1 李韋萱;兩類帶有維修的排序問題[D];沈陽師范大學(xué);2015年

2 周雨波;與工件釋放時間和交貨時間有關(guān)的排序問題及近似算法[D];蘭州大學(xué);2015年

3 張龍;優(yōu)化交貨期窗口的單機(jī)供應(yīng)鏈排序問題[D];曲阜師范大學(xué);2015年

4 于萌萌;工件帶有惡化效應(yīng)的博弈排序問題[D];曲阜師范大學(xué);2015年

5 李雨潔;恒速機(jī)下的有限資源博弈排序最優(yōu)性研究[D];曲阜師范大學(xué);2015年

6 尚明明;帶有GDD假設(shè)的幾類重新排序問題研究[D];鄭州大學(xué);2015年

7 黃保斌;分批的供應(yīng)、加工、配送供應(yīng)鏈排序問題[D];曲阜師范大學(xué);2015年

8 程琦;交貨期可指派的新型排序問題研究[D];東華理工大學(xué);2014年

9 沈園園;不確定環(huán)境下的機(jī)器排序問題[D];清華大學(xué);2015年

10 易杰;成組排序與重新排序問題研究[D];河南工業(yè)大學(xué);2016年

，

本文編號：1555245