Scheduling Jobs With Non-Identical Sizes On Parallel Batch Prosessors

Batch processing scheduling is an important scheduling problem. Many manufacturing systems contain batch processors. The thesis considers the problems of scheduling jobs with non-identical capacity requiements or sizes on identical, uniform and unrelated batch processing machines to minimize the makespan respectively. It comprises the following three chapters:Chapter 1 is devoted to schedule jobs with non-identical capacity requiements on identical batch processing machines. we provide an approximation algorithm PM, and prove that its performance ratio isn't more than 11/4-1/m. All the machines have the same speed.In chapter 2, we consider the problem of sheduling jobs witn non-identical sizes on uniform batch processing machines to minimize the makespan. We give two approximation algorithms: QBFF and QM, and prove that their performanceratios aren't more than B/a + 1, 7/4 + ρ, respectively, where ρ = (m - l)s₁/ ∑s_i, a = min{a_j}, s_i is the speed of machine M_i, m is the number of the machines.