Algorithms Study In Batch Scheduling And Bin Packing

In this thesis, we deal with some new models of scheduling on a single batch processing machine and bin packing problems. Firstly, we consider two online models of batch scheduling problems to minimize makespan which arises in the semiconductor manufacturing. The batch processing machine can handle several jobs simultaneously if total size of them does not exceed the capacity B of the machine. These jobs form a batch. The jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time and size become known upon its arrival. In Chapter 3, we consider the model that the jobs have identical processing time. A Greedy Algorithm with competitive ratio 2 is provided. Then, we design an improved online algorithm A₂ with competitive ratio not greater than 3^1/2 In Chapter 4, the general model that the jobs have arbitrary processing times is considered. For the special case with only two distinct arrival times, we give an online algorithm M₂(α) with competitive ratio not greater than 119/44. For the general case, an algorithm M^∞ is showed that its competitive ratio is not greater than 7/2. Moreover, we prove that if the problem satisfies the agreeable assumption 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), both algorithms can be improved.Secondly, we study two varieties of classical bin packing problems. In Chapter 5, we deal with variable-sized bin packing which arises in carrier transportation. There...