帶容量限制的平行機(jī)排序問(wèn)題.pdf

1、本文考慮了帶容量限制的平行機(jī)排序問(wèn)題：給定m個(gè)同型平行機(jī)(identicalmachines)，限定每臺(tái)機(jī)器上最大的加工個(gè)數(shù)為ki。給定M≤∑ki個(gè)工件，每個(gè)工件的加工時(shí)間記為ti≥0，找出一個(gè)排序使其時(shí)間跨度(makespan)最小而且滿足問(wèn)題所要求的容量限制。
　　 當(dāng)機(jī)器臺(tái)數(shù)為2且容量限制不同時(shí)，則離線情況下提出了算法MLPT，且證明了該算法具有緊界5/3。更進(jìn)一步，在算法MLPT的基礎(chǔ)上，將其稍加修改，記為RLPT，證明

2、該改進(jìn)算法的界為3/2。在線情況下，證明若兩臺(tái)機(jī)器的容量限制之差大于等于2時(shí)，則任何合理的在線算法都不具有比2更好的界。然而若它們的容量限制之差為0或1時(shí)，提出了一個(gè)在線算法(記為BS)，并證明這種情況下該算法具有界1+α，其中α=√5—1/2，且該算法是最好算法。
　　 當(dāng)機(jī)器臺(tái)數(shù)為m時(shí)，首先證明了當(dāng)容量限制不同時(shí)，任何在線算法的界至少是m+1/2。另外，當(dāng)機(jī)器的容量限制相同時(shí)，分析了LS算法，并證明LS算法的界為2m—δ—1