Semi-online scheduling with ‘end of sequence’ information

Semi-online scheduling with ‘end of sequence’ information

0.00 Avg rating0 Votes
Article ID: iaor20083045
Country: Netherlands
Volume: 14
Issue: 1
Start Page Number: 45
End Page Number: 61
Publication Date: Jul 2007
Journal: Journal of Combinatorial Optimization
Authors: ,
Abstract:

We study a variant of classical scheduling, which is called scheduling with ‘end of sequence’ information. It is known in advance that the last job has the longest processing time. Moreover, the last job is marked, and thus it is known for every new job whether it is the final job of the sequence. We explore this model on two uniformly related machines, that is, two machines with possibly different speeds. Two objectives are considered, maximizing the minimum completion time and minimizing the maximum completion time (makespan). Let s be the speed ratio between the two machines, we consider the competitive ratios which are possible to achieve for the two problems as functions of s. We present algorithms for different values of s and lower bounds on the competitive ratio. The proposed algorithms are best possible for a wide range of values of s. For the overall competitive ratio, we show tight bounds of ϕ + 1 ≈ 2.618 for the first problem, and upper and lower bounds of 1.5 and 1.46557 for the second problem.

Reviews

Required fields are marked *. Your email address will not be published.