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

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

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