單機(jī)在線繼列分批排序與離線混合分批排序.pdf

1、AthesissubmittedtoZhengzhouUniversityforthedegreeofMasterOnlineSerialbatchSchedulingandOfflineMixedBatchSchedulingonaSingleMachineByXuhaiLiSupervisor：ProfJinjiangYuanMasterofScienceOperationsResearchandCyberneticsDepartm

2、entofMathematicsMay2011摘要本文研究單機(jī)上的在線繼列分批和離線混合分批排序在線繼列分批排序中，一個(gè)工件的信息只有當(dāng)它到達(dá)后才被釋放出來(lái)一臺(tái)批處理機(jī)可以同時(shí)將多個(gè)工件作為一個(gè)繼列批進(jìn)行加工，每個(gè)工件都有它自己的安裝時(shí)間，批的加工時(shí)間為這一批里的所有工件的加工時(shí)間之和，批安裝時(shí)間為這一批里工件的最大的安裝時(shí)間，目標(biāo)是最小化時(shí)間表長(zhǎng)利用排序問(wèn)題的三參數(shù)表示法，該問(wèn)題可表示為l[sbatch，On1ine，b=。。，n≤r

3、j號(hào)s≥sJI‰：混合分批排序中，我們有兩組工件3a和7B，分別稱為A工件和B工件這兩組工件要在同一臺(tái)可以對(duì)工件進(jìn)行分批的機(jī)器上進(jìn)行排序但是，4工件和B工件不能放在同一批內(nèi)進(jìn)行加工此外，A工件批為平行批，容量為b(A)；B工件批為繼列批，容量為6(B)，安裝時(shí)間為s(B)利用排序問(wèn)題的三參數(shù)表示法，該問(wèn)題可表示為1ls—pbatch，s(B)，(6(A)，6(B))h其中，，y∈(G眥，Lm缸，∑0，∑嶼0，厶嫩)本文的主要內(nèi)容如下：第

4、一章介紹了排序問(wèn)題的背景和本文所研究問(wèn)題的相關(guān)發(fā)展，并給出了相關(guān)排序問(wèn)題的術(shù)語(yǔ)和記號(hào)第二章研究在線繼列分批排序，給出排序問(wèn)題l[sbatch，Oil1ine，b=。。，n≤乃號(hào)鼠≥句IG僦的一個(gè)最好可能的在線算法，其競(jìng)爭(zhēng)比為(怕1)／2第三章研究單機(jī)兩組工件繼列分批與平行分批混合排序主要結(jié)果如下：排序問(wèn)題1[spbatch，s(B)，(。o，o。)l工m艤在O(nAnBn)時(shí)間可解排序問(wèn)題1Ispbatch，s(B)，(。。，6(B))