流水調(diào)度問題是組合優(yōu)化領(lǐng)域的經(jīng)典問題之一,因為與實際生產(chǎn)密切相關(guān),是目前研究較為廣泛的一種調(diào)度問題。在整個生產(chǎn)過程中,產(chǎn)品的加工與產(chǎn)品的運(yùn)輸是最重要的兩個環(huán)節(jié),如果將兩者結(jié)合并提出合理的解決方案,既可以節(jié)約生產(chǎn)成本,又可以提高生產(chǎn)效率。本文主要研究考慮運(yùn)輸時間的兩臺機(jī)器和一臺運(yùn)輸機(jī)的流水調(diào)度,根據(jù)運(yùn)輸機(jī)所處的位置,分為兩種模型。模型1:工件先在兩臺流水機(jī)器上加工,然后由運(yùn)輸機(jī)運(yùn)輸?shù)侥康牡?模型2:工件先在一臺流水機(jī)器上加工,然后由運(yùn)輸機(jī)運(yùn)輸?shù)搅硪慌_流水機(jī)器上繼續(xù)加工。本文研究了以上兩種模型的計算復(fù)雜性,設(shè)計了模型1在某些特殊情況下的最優(yōu)調(diào)度算法,同時改進(jìn)了這兩種模型近似算法的近似比,具體結(jié)果如下:首先,對于模型1,當(dāng)運(yùn)輸機(jī)每次最多運(yùn)輸2個工件時,Yuan等人在2007年只證明該問題是一般NP-難。本文證明了該問題是強(qiáng)NP-難,解決了2007年以來一直未解的問題。對于模型2,目前其復(fù)雜性的研究結(jié)果如下:2001年Hurink和Lee等人分別證明了當(dāng)運(yùn)輸機(jī)每次運(yùn)輸1個或3個及以上工件時,這兩種情況都是強(qiáng)NP-難,而每次最多運(yùn)輸2個工件時,該問題是否是強(qiáng)NP-難十幾年來尚未被證明。本文證明了... 

【文章來源】：大連理工大學(xué)遼寧省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：95 頁

【學(xué)位級別】：博士

【部分圖文】：

圖２．３大工件在機(jī)器５上加工完成時間??Ｆｉｇ．２．３?Ｃｏｍｐｌｅｔｉｎｇ?ｔｉｍｅ?ｏｆ?ｂｉｇ?ｊｏｂ?ｂ〇?ｏｎ?ｍａｃｈｉｎｅ?Ｂ??

圖２．４大工件＆〇和極小工件調(diào)度示意圖??Ｆｉｇ．２．４?Ｔｈｅ?ｓｃｈｅｄｕｌｅ?ｆｏｒ?ｂｉｇ?ｊｏｂ?６〇?ａｎｄ?ｔｉｎｙ?ｊｏｂ?ｔ〇??

圖２．５第一個有序組調(diào)度示意圖?？??Ｆｉｇ．２．５?Ｔｈｅ?ｓｃｈｅｄｕｌｅ?ｄｉａｇｒａｍ?ｏｆ?ｔｈｅ?ｆｉｒｓｔ?ｏｒｄｅｒｅｄ?ｇｒｏｕｐ??

【參考文獻(xiàn)】：
期刊論文
[1]P/NP問題的答案是P≠NP[J]. 溫邦彥.  重慶理工大學(xué)學(xué)報(自然科學(xué)版). 2010(09)
[2]生產(chǎn)調(diào)度研究綜述[J]. 余建軍,張定超,周銘新.  中國制造業(yè)信息化. 2009(17)
[3]帶運(yùn)輸時間和自動機(jī)的流水作業(yè)排序問題的復(fù)雜性[J]. 時凌,文軍.  數(shù)學(xué)物理學(xué)報. 2008(05)
[4]生產(chǎn)調(diào)度理論和方法研究綜述[J]. 徐俊剛,戴國忠,王宏安.  計算機(jī)研究與發(fā)展. 2004(02)
[5]3機(jī)Flow-shop調(diào)度問題研究[J]. 陳雄,湯光強(qiáng),吳啟迪.  信息與控制. 2002(03)
[6]排序、經(jīng)典排序和新型排序[J]. 唐國春.  數(shù)學(xué)理論與應(yīng)用. 1999(03)

碩士論文
[1]兩階段車間作業(yè)排序問題的研究[D]. 楊佳雯.浙江理工大學(xué) 2016
[2]若干帶運(yùn)輸排序問題研究[D]. 王學(xué)士.浙江理工大學(xué) 2015



本文編號：3084275