具有特殊族工件的分批在線排序問題.pdf

1、授予單位代碼學(xué)號或申請?zhí)?0459:200612014070105008鄭碩士州大學(xué)位(科學(xué)學(xué)位)學(xué)論文具有特殊族工件的分批在線排序問題院系名稱:數(shù)學(xué)系學(xué)科門類:理學(xué)專業(yè)名稱:運(yùn)籌學(xué)與控制論作者姓名:郭書恩導(dǎo)師姓名、職稱:李文華教授二零零九年五月摘要所謂排序，就是在一定的約束條件下對工件和機(jī)器按時(shí)間進(jìn)行分配和安排次序，使某一個(gè)或某一些指標(biāo)達(dá)到最優(yōu).在平行分批排序模型中，機(jī)器可以同時(shí)加工屬于同一批的多個(gè)工件.每一個(gè)批的加工時(shí)間是這批工件中

2、所有工件加工時(shí)間的最大者.對于分族工件來說，不同族的工件不能放在一批進(jìn)行加工.在在線排序間題中，工件按時(shí)到達(dá)，每個(gè)工件的特性(包括它的加工時(shí)間馬和到達(dá)時(shí)間勺)只有在工件到達(dá)時(shí)才知道，并且工件一旦被安排之后就不允許再改變.一個(gè)在線算法的好壞通常是用它的競爭比來衡量的.本文研究了一類特殊的三族工件平行分批的最小化時(shí)間表長排序問題.在這個(gè)模型中，有兩個(gè)族可分批的批容量是無界的，即為正常的可分批族另外一個(gè)族的批容量為1，即一批只能加工一個(gè)工件.