Research On Some Concrete Problems In Jobs Scheduling

In general, Jobs Scheduling investigates the problem of, with limited computa-tional resource, how to efficiently process a large amount of computational jobs. In this paper we focus on two kinds of problems in the area of Jobs Scheduling.In this paper, we first consider the problem of Scheduling Machines with Capacity Constraints. Its uniform variation, general variation and k dimensional variation are investigated. Capacity constraints mean individual machine may not be able to process too many jobs. Each machine may have its own capacity upper bound. The aim is to find a feasible schedule that has the minimum Makespan and satisfies the capacity con-straints. In the uniform variation in which the running times of a given job on different machines are identical, we develop 3-approximation algorithm using Iterative Rounding Method against Linear Programming. To the best of the authors' knowledge, this is the first time Iterative Rounding Method is applied to scheduling problem. For the general variation in which a given job may need different running time on different machines, we design a 2-relaxed decision procedure and then derive a 2-approximation algorithm. In the multi-dimensional version, which is generalized by extending the running time of machines to be a kind of capacity, we first develop a (4,4)-relaxed decision procedure for 2-dimensional, say, bicriteria version, then extend it to the k-dimensional version and obtain a (O(k),O(k),..., O(k))-relaxed decision procedure.In the second half of this paper, we consider the Minimum of Maximum Job La-tency in the problem of Precedence Constrained Scheduling on Single Machine. We use Iterative Rounding Method to design a 2-approximation algorithm. Our approach shows the generality of Iterative Rounding Method against NP-Hard problem.