Lower Bounds On The On-line Hierarchical Uniform Machine Scheduling

This paper studied the on-line scheduling on hierarchical uniform machines. Jobs arrive on-line over list are processed in three hierarchical uniform machines. Two types of the model are studied. In the first type, the first machine’s speed is1, which could process all jobs, while the other two machines’ speed is s which could only process jobs of level2. The second type is the first and second machines’ speed is1, which could process all jobs, while the third machine’s speed is s, which could only process jobs of level2. We present some lower bounds for some special cases.