最小化時間表長的分組工件單機繼列批在線排序.pdf

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

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

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