On Problems Of Batch Scheduling With Resource Constraints

scheduling has always been an important branch in the research of combinatorial optimization, due to its profound significance in both real world and theory. Batch scheduling is a kind of relatively new scheduling models, which is attracting more and more attention recently. In this dissertation, many new results of the above model with resource constraints on complexities and algorithms are presented. Four chapters are included in the dissertation.In Chapter 1, we briefly introduced some definitions, notations and basic information about scheduling.In Chapter 2, the problems of minimizing the total weighted completed time on single batch processing machine is studied. By using of the FBLW Algorithm, for the case with integeral arrival times and unit processing times, we design an optimal algorithm running in time O(n² log n); For the case with a constant of m arrival times and a identical processing times, we present an optimal algorithm with time complexity O(2^m-1n logn).In Chapter 3, we considered two batch scheduling problems with machine availability constraint. This is the first time that batching machine with availability constraint is considered. For the single machine unpreempetive batch scheduling problem to minimize makespan, we find a polynomial optimal algorithm for the unbounded case, and a 4/3-approximateheuristic, we also prove that the bound is tight.In Chapter 4, we summarized the dissertation and put forward some prob- lems to consider further.