Hierarchical Scheduling On Two Uniform Machines With Bounded Job Sizes

In this paper we study the lower bound and algorithm of two uniform machines scheduling problem under a grade of service provision with the objective of minimizing the makespan. Both machines and jobs have different grades of service and only when a job has a grade of service no less than the machine’s can the job be arranged on the machine. In the semi-online version, the jobs arrive one by one in a given list, and some partial information about the jobs is known in advance. In this paper, we investigate the version of known lower and upper bounds of job sizes.In Chapter 2, we consider the semi-online scheduling problem on two uniform ma-chines with bounded job sizes, where the second machine runs s(0< s< 1)times as fast as the first one. Besides, the second machine can only process partial jobs under some grade of service. Denote the ratio of upper and lower bound of job sizes by t(t≥ 1), i.e.1≤ p≤ t. Presently the area of the (s, t) region failed to be optimal is about 0.2. We discuss the problem for different values of (s, t) of which are not solved yet. We investigate the lower bounds on some (s, t) regions and present an algorithm A for those intervals about s and t, which turns out to be optimal. We has narrowed down the area of the (s, t) region failed to be optimal to 0.007.