兩類平行機(jī)分批排序問題.pdf

1、排序問題是一類重要的組合最優(yōu)化問題．本文首先介紹了排序問題的定義和分類，然后對分批排序問題進(jìn)行了討論．分批排序是現(xiàn)代排序模型之一，有著很強(qiáng)的應(yīng)用背景．在這一排序模型中，若干個(gè)工件可以放在一批中同時(shí)加工，工件在加工過程中不允許中斷，也不允許移走正在加工的工件，同批工件的完工時(shí)間均等于該批中最后工件的完工時(shí)間．分批排序模型按照分批方式的不同可以分成兩類：并行分批排序模型和串行分批排序模型．在并行分批排序模型中，機(jī)器在每一時(shí)刻可以加工多個(gè)工件

2、，在串行分批排序模型中，機(jī)器在每一時(shí)刻最多只能加工一個(gè)工件，工件按一個(gè)接一個(gè)的串聯(lián)方式形成一批． 本文首先介紹了分批排序問題的分類及其研究成果，然后分別對兩類平行機(jī)的并行分批與串行分批排序問題進(jìn)行了討論．第二章分別討論了容量無限與容量有限的平行機(jī)并行分批排序問題．第一種同型批處理機(jī)，容量為無限，目標(biāo)函數(shù)是極小化完工時(shí)間和，本文給出了動態(tài)規(guī)劃算法，并將結(jié)論進(jìn)一步推廣至同類批處理機(jī)．第二種同類批處理，容量為有限，目標(biāo)函數(shù)是極小化加權(quán)