Minimizing Maximum Lateness On Batching Machine

This thesis contains three parts, the objective is to minimize the maximumlateness on batching machine. Two variants are analyzed.In part one, some notion, definitions and basic background information -tsintroduced.In part two, the scheduling problems on uniformly related batch machines are firstly delivered. Two kinds of problems are considered: minimize the makespan and minimize the maximum lateness. The relation between batch scheduling and classical scheduling is declared, then an interesting transform lemma is obtained. Some heuristics for the problems are present, and their performance guarantee is analyzed by the transform lemma. Some present results are improved.In part three, the problem of scheduling n jobs on a single'batching machine is addressed, and the jobs have release times and due dates. Efficient algorithms are also provided for the problem. Algorithm BLS has a worst-case guarantee no more than 1+B, the bound indicates that it becomes very poor in extreme caseswhere B is algorithm BLPT provides worst case error bound 3.