兩種新型排序問題的近似算法——分批排序和柔性流水車間排序問題的研究.pdf

1、曲阜師范大學(xué)碩士學(xué)位論文兩種新型排序問題的近似算法——分批排序和柔性流水車間排序問題的研究姓名：任建鋒申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：張玉忠2003.3.12曲阜師范大學(xué)碩士學(xué)位畢業(yè)論文1當(dāng)工件被分批加工時(shí)，每一批的工時(shí)為該批中所有工件的加工時(shí)間的最大值，到達(dá)時(shí)間是其中的工件最晚的到達(dá)時(shí)間2一批工件只能在一臺(tái)機(jī)器上加工，而且開工以后不能被打斷或轉(zhuǎn)移到別的機(jī)器上，一直到該批被加工完明顯地，同一批工件的完工時(shí)間是相同的二PT

2、AS算法下面將Foto等(13]在蓽機(jī)排序問題1frjf∑G中給出的兩個(gè)引理推廣到同型機(jī)的分批排序問題P圳rJ，B∑eJ中這兩個(gè)引理將原實(shí)例的加工時(shí)間和到達(dá)時(shí)問轉(zhuǎn)化成具有較好性質(zhì)的新實(shí)例，且費(fèi)用不超過1oie)引理1在修正費(fèi)用不超過1￡的情況下，可以將原實(shí)例的加工時(shí)間和到達(dá)時(shí)間修改為1￡的整數(shù)次冪引理2在修正費(fèi)用不超過1￡的情況下，可以對(duì)所有工件J的到達(dá)時(shí)間進(jìn)行修正，使其滿足ri≥￡只引理2表明我們可以假定沒有工件在零時(shí)刻到達(dá)，且沒有工