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

1、AthesissubmittedtoZhengzhouUniversityforthedegreeofMasterOnlineSerialbatchSchedulingandOfflineMixedBatchSchedulingonaSingleMachineByXuhaiLiSupervisor：ProfJinjiangYuanMasterofScienceOperationsResearchandCyberneticsDepartm

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

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

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