Minimizing Makespan And Maximum Lateness On Batching Machine

Scheduling is an important research field of combinatorial optimization. Batch machine scheduling problem has its root in various application areas and attracts a lot of attention recently. In this paper we consider the problem of scheduling jobs on a single batch processing machine. Three chapters are included in this thesis.In the first chapter, some notations, definitions and basic background information about the subject are introduced.In the second chapter, we address the problem 1|B, r_j, s_j|C_max. Shuguang Li et al. first considered this problem, and presented an approximation algorithm with worst-case ratio 2 + ε, where ε > 0, can be made arbitrarily small. The problem considered in this paper is similar to that of Shuguang Li et al., the only difference is that we restrict the machine capacity B to be fixed, and we get better results in the sense of worst-case performance. Our main results are as follows:(1) An approximation algorithm with with worst-case ratio 3/2+ε is proposed for the version where the processing times of large jobs (with sizes greater than B/2) are not less than those of small jobs (with sizes not greater than B/2). This result is the best possible unless P = NP.(2) For the general case we present an approximation algorithm with worst-case ratio 7/4 + ε.(3) We also point out that these algorithms can trivially be extended to the...