最小化時(shí)間表長(zhǎng)的分組工件單機(jī)繼列批在線排序.pdf

1、PhMDissertation，ZhengzhouUniversity，No200712014070105005On1ineschedulingonaserialbatchmachinewith一●●●familyt0mlnlmlzethemakesPanCandidate：JunmeiDOUSupervisor：ProfWenhuaLiSpeciality：OperationsResearchandCyberneticsDepartm

2、entofMathematics，ZhengzhouUniversity，Zhengzhou，450052，PRChinaSeptember，2010摘要本文研究帶有工件組的單機(jī)繼列批在線排序問(wèn)題，批容量分無(wú)限和有限，目標(biāo)函數(shù)為最小化最大完工時(shí)間。工件的到達(dá)時(shí)刻是任意的，每個(gè)工件都有各自的安裝時(shí)間。機(jī)器在每一時(shí)刻最多加工一個(gè)工件，工件是按照一個(gè)接一個(gè)串聯(lián)的方式形成一批的。批的安裝時(shí)間等于包含在這一批里的工件的最大安裝時(shí)間，批加工時(shí)間等于

3、包含在這一批里的工件的加工時(shí)間之和。具體的模型如下：(1)1]on—line，s—batch，(s，p)，b=oo，n≤勺≥5i≥勺，twofamilies[C～，其中(s，P)表示工件具有各自的安裝時(shí)間和加工時(shí)間。我們給這個(gè)問(wèn)題的下界是皿4墨，并給出了最好可能的在線算法。(2)lion—line，s—batch，(s，p)，6=o。，5t=8，twofamilieslC。，我們同樣證明了這個(gè)問(wèn)題的下界是牮，并給出了最好可能的在線算法。