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

1、AthesissubmittedtoZhengzhouUniversityforthedegreeofMasterOnlineSerialbatchSchedulingandOfflineMixedBatchSchedulingonaSingleMachineByXuhaiLiSupervisor：ProfJinjiangYuanMasterofScienceOperationsResearchandCyberneticsDepartm

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

3、j號s≥sJI‰：混合分批排序中，我們有兩組工件3a和7B，分別稱為A工件和B工件這兩組工件要在同一臺可以對工件進行分批的機器上進行排序但是，4工件和B工件不能放在同一批內(nèi)進行加工此外，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、一章介紹了排序問題的背景和本文所研究問題的相關發(fā)展，并給出了相關排序問題的術語和記號第二章研究在線繼列分批排序，給出排序問題l[sbatch，Oil1ine，b=。。，n≤乃號鼠≥句IG僦的一個最好可能的在線算法，其競爭比為(怕1)／2第三章研究單機兩組工件繼列分批與平行分批混合排序主要結(jié)果如下：排序問題1[spbatch，s(B)，(。o，o。)l工m艤在O(nAnBn)時間可解排序問題1Ispbatch，s(B)，(。。，6(B))