裝箱和調(diào)度作為組合優(yōu)化問(wèn)題中比較經(jīng)典的兩大類(lèi),已在工業(yè)生產(chǎn)、物流管理、交通規(guī)劃等行業(yè)發(fā)揮了重要作用。它們的研究見(jiàn)證了近似算法理論的發(fā)展歷程,為其它離散組合優(yōu)化問(wèn)題的研究提供了重要的理論科學(xué)依據(jù)。近年來(lái),帶緩沖區(qū)的在線裝箱已成為研究熱點(diǎn),當(dāng)物品尺寸上限不超過(guò)1/2、緩沖區(qū)大小為2時(shí),目前最好的結(jié)果是鄭等人給出的1.4444的漸近競(jìng)爭(zhēng)比。對(duì)第一階段單機(jī)第二階段多臺(tái)并行機(jī)的兩階段混合流水調(diào)度問(wèn)題,孫等人給出了特定條件下近似比為3的近似算法。本文主要針對(duì)這些結(jié)果分別進(jìn)行改進(jìn)和擴(kuò)展研究。對(duì)于裝箱問(wèn)題,主要研究了帶常數(shù)大小緩沖區(qū)和有界空間兩類(lèi)在線模型。帶緩沖區(qū)在線裝箱指物品在線到來(lái)后可先放入緩沖區(qū),待緩沖區(qū)滿后再進(jìn)行裝箱決策。本文基于物品尺寸劃分思想先將物品按尺寸區(qū)間進(jìn)行分類(lèi),箱子亦按最后所裝物品的組合特征進(jìn)行相應(yīng)分類(lèi)。裝箱時(shí)按類(lèi)別從緩沖區(qū)中選擇合適物品裝入特定類(lèi)別箱子中。本文給出了使用大小為2緩沖區(qū)、物品被分成4類(lèi)的在線算法Al。競(jìng)爭(zhēng)比分析時(shí),采用權(quán)重函數(shù)思想,根據(jù)物品在箱子中的相對(duì)占比設(shè)計(jì)物品的權(quán)重值。研究結(jié)果表明算法A1的最壞漸近競(jìng)爭(zhēng)比為1.4375。該結(jié)果改進(jìn)了前人使用相同大小輔助空間時(shí)的1.4444競(jìng)爭(zhēng)比結(jié)果;若將緩沖區(qū)擴(kuò)大至3,物品被劃分成5類(lèi),競(jìng)爭(zhēng)比可改進(jìn)至1.4243。通過(guò)構(gòu)建使任何算法都不會(huì)表現(xiàn)很好的問(wèn)題實(shí)例,將帶緩沖的在線裝箱算法下界由1.3333改進(jìn)至1.4230,縮緊了上下界之間的縫隙。同時(shí)研究了有界空間在線裝箱模型,在打開(kāi)5個(gè)和7個(gè)箱子情況下,給出物品上限為1/2時(shí)的最壞漸近競(jìng)爭(zhēng)比分別為1.4243和1.4236的兩個(gè)在線算法,改進(jìn)了經(jīng)典調(diào)和算法中使用同樣大小有界空間的競(jìng)爭(zhēng)比結(jié)果。對(duì)于混合流水調(diào)度問(wèn)題,主要研究了集流水與平行機(jī)兩種調(diào)度形式的兩階段混合流水調(diào)度模型。模型中第一階段僅有一臺(tái)機(jī)器,第二階段有m臺(tái)并行機(jī),任務(wù)在第二階段可由多臺(tái)機(jī)器并行處理。按第一階段所有任務(wù)全部結(jié)束再啟動(dòng)第二階段操作的思路,利用已有條形裝箱與平行機(jī)調(diào)度算法,從理論上設(shè)計(jì)了若干近似比小于等于3的近似算法,改進(jìn)了前人給出的特定約束條件下的3近似比結(jié)果。對(duì)第二階段機(jī)器數(shù)目分別為2和3的特定模型,根據(jù)任務(wù)在第二階段所需機(jī)器數(shù)將任務(wù)分組,按先整組調(diào)度、組內(nèi)再列表調(diào)度的設(shè)計(jì)思路,給出了線性時(shí)間復(fù)雜度下近似比分別為2.5和2.67的近似算法。最后通過(guò)對(duì)原模型任務(wù)不可切割條件的松弛,將任務(wù)切割至第二階段的所有機(jī)器上,利用經(jīng)典兩階段流水調(diào)度的Johnson算法,給出所研究模型新的下界,改進(jìn)了前人給出的下界結(jié)果。
【學(xué)位單位】：大連理工大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2019
【中圖分類(lèi)】：TP301.6;TH247
【部分圖文】：

圖２．２算法Ａ１可能裝載情況示意圖逡逑Ｆｉｇ．邋２．２邋Ｐｏｓｓｉｂｌｅ邋ｂｉｎ邋ｃｏｎｆｉｇｕｒａｔｉｏｎｓ邋ｏｆ邋Ａ１逡逑２．３．２競(jìng)爭(zhēng)比分析逡逑本節(jié)將利用權(quán)重函數(shù)思想，通過(guò)權(quán)重函數(shù)建立算法Ａ１與離線最優(yōu)算法間關(guān)系，據(jù)物品在箱子中的占有率來(lái)設(shè)計(jì)權(quán)重函數(shù)，由此分析最壞情況下算法Ａ１的漸近競(jìng)爭(zhēng)比首先根據(jù)算法裝箱策略考查一下各類(lèi)箱子的最小裝載率。逡逑引理２．２：算法Ａ１完成時(shí)，除了步驟５中用到的箱子外，其它任意一個(gè)／ｆｃ－６ｍ（Ａ；邋＝１，２，邋３）所裝物品尺寸之和至少為每一個(gè)／４邋－邐所裝物品尺寸之和至少為｜。逡逑證明：根據(jù)算法Ａ１處理過(guò)程知，每個(gè)Ａ邋－邋中有２個(gè)－邋ｐｉｅｃｅｓ，根據(jù)物品分規(guī)則，每個(gè)Ａ邋－邋ｐｉｅｃｅｓ都大于￥，故每個(gè)／丨－６咖至少裝｜。同理每個(gè)／２邋－邋至少｜，每個(gè)Ａ邋—６ｍ至少裝ｆ。逡逑算法執(zhí)行過(guò)程中，如果需要打開(kāi)１個(gè)Ｊ４邋－邋６ｉｎ，那么意味著此時(shí)此刻Ｓ１＇中至多１個(gè)Ａ邋－邋ｐｉｅｃｅｓ、２個(gè)／２邋－邋ｐｉｅｃｅｓ，由于緩沖區(qū)總的大小為２，貝＿沖區(qū)中所有剩余／３邋－邋ｐｉｅｃｅｓ和Ｊ４邋－邋ｐｉｅｃｅｓ類(lèi)物品總的尺寸大小一定超過(guò)２邋－邋｜邋－著＝｜；同時(shí)由于此１＇－－—

ＢＥＧＩＮ逡逑（１）將第１個(gè)物品ａｉ放入緩沖區(qū)中；逡逑（２）如果沒(méi)有新到來(lái)的物品，則轉(zhuǎn)到步驟５；否則重復(fù)地將每一個(gè)新到來(lái)物品放入緩沖區(qū)逡逑中，直到放不進(jìn)去為止；逡逑（３）令Ｖ邋＝邋ｅ邋＊５｝邋Ｕ邋｛叫｝，分以下幾種情況裝箱；逡逑３．１）若Ｓ＇中至少有Ａ：邋＋邋１個(gè)厶—ｐｉｅｃｅｓ＃邋＝邋１，２，邋３），則打開(kāi)１個(gè)－邋６ｍ，任選ｆｃ邋＋邋１逡逑個(gè)－邋ｐｉｅｃｅｓ物品放入這個(gè)４邋－邋Ｍｎ中，關(guān)閉該箱子，轉(zhuǎn)到步驟２；逡逑３．２）若Ｙ中厶－Ｐｉｅｃｅｓ類(lèi)物品總大小超過(guò)｜，則打開(kāi)１個(gè)厶－■，按ＮＦ策略將盡逡逑可能多的Ａ－ｐｉｅｃｅｓ類(lèi)物品放人該箱子中，結(jié)束后關(guān)閉該箱子，轉(zhuǎn)到步驟２；逡逑３．３）若以上情況均未出現(xiàn)，則打開(kāi)］個(gè)忍－ｂｉｎ箱子，首先將Ｓ１＇中所有／４－ｐｉｅｃｅｓ逡逑類(lèi)物品放入該筘子中，然后苒按ＮＦ策略將盡可能多的－邋ｐｅｃｅｓ類(lèi)物品放入該逡逑箱子中，直到放不進(jìn)去為止，關(guān)閉該箱子，轉(zhuǎn)到步驟２；逡逑（５）將緩沖區(qū)中剩余物品按ＮＦ策略裝箱。逡逑ＥＮＤ逡逑圖２．３展示了算法Ａ２執(zhí)行后各類(lèi)箱子可能的裝載情況。逡逑

ｍ邋：＝邋ｍ－＼－邋ｍ／ｃ；逡逑ＥＮＤ逡逑若物品尺寸分布相對(duì)比較均勻，算法結(jié)束后每類(lèi)箱子的可能裝載情況如圖３．１所示。逡逑５＋￡邐；邐：逡逑１＋＾邐５＋￡：邐：邐；逡逑４邋邐邋■逡逑卜＇——邋Ｗ邐■逡逑邐邐＼＋￡邐邐邋——邐＾ｍｚ逡逑邐邋ｊ＋ｆ邐邐逡逑３邐－＋￡邐邐邋ｎ邋ｓ逡逑邐邋邐邋Ｊ邋＋邋ｇ邋ｈ＋￡逡逑Ｉｘ邋－邋ｂｉｎ邐Ｌ邋—ｂｌｎ邐ｈ邋－邋ｂｉｎ邐／４邋—邋ｂｉｎ邐ｈ邋－ｂｉｎ逡逑圖３．１算法Ａ３可能裝載情況示意圖逡逑Ｆｉｇ邋３．１邋Ｐｏｓｓｉｂｌｅ邋ｂｉｎ邋ｃｏｎｆｉｇｕｒａｔｉｏｎｓ邋ｏｆ邋Ａ３逡逑－３８－逡逑

【參考文獻(xiàn)】

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

1 孫景昊;鄧慶緒;孟亞坤;;GPU上兩階段負(fù)載調(diào)度問(wèn)題的建模與近似算法[J];軟件學(xué)報(bào);2014年02期

2 陳田;陳慶新;毛寧;劉建軍;;具有兩道工序的柔性同序加工車(chē)間任務(wù)投放策略[J];工業(yè)工程;2010年05期

3 王輝;魯習(xí)文;;工件帶到達(dá)時(shí)間的兩階段柔性流水作業(yè)的近似算法[J];運(yùn)籌學(xué)學(xué)報(bào);2007年03期

4 張國(guó)川;k－Bounded　Space　On－line裝箱中AFB_k算法的界[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);1996年03期

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

1 趙曉凡;在線裝箱問(wèn)題相關(guān)近似算法研究[D];北京交通大學(xué);2016年

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

3 姚國(guó)輝;若干組合優(yōu)化問(wèn)題的算法研究[D];山東大學(xué);2009年

4 石永強(qiáng);若干批處理機(jī)排序與裝箱問(wèn)題的算法研究[D];浙江大學(xué);2005年

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

1 孫蕊;多車(chē)場(chǎng)多配送中心滿載車(chē)輛路徑問(wèn)題研究[D];沈陽(yáng)師范大學(xué);2016年

2 邵飛牛;一維裝箱問(wèn)題啟發(fā)式算法的設(shè)計(jì)與分析[D];東北大學(xué);2013年

3 陳幸瑜;兩臺(tái)同類(lèi)機(jī)極大化機(jī)器最小負(fù)載問(wèn)題研究[D];浙江大學(xué);2008年

4 郭文靜;兩階段模糊柔性流水車(chē)間排序模型及算法[D];南京理工大學(xué);2006年

本文編號(hào)：2815993