In this paper, we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p, (1+φ)p], where p>0 and f = (Ö5-1)/2phi=(sqrt{5}-1)/2. Jobs arrive over time. First, we deal with the on-line problem on a bounded batch machine with the objective to minimize makespan. A class of algorithms with competitive ratio (Ö5+1)/2(sqrt{5}+1)/2 are given. Then we consider the scheduling on an unbounded batch machine to minimize the time by which all jobs have been delivered, and provide a class of on-line algorithms with competitive ratio (Ö5+1)/2(sqrt{5}+1)/2. The two class of algorithms are optimal for the problems studied here.
展开▼
