Batch Scheduling With Nonidentical Job Size And With Rejection

Due to its profound significance in both real world and theory, scheduling has always been a hot topic in the research of combinatorial optimization since the 1990s. Batch scheduling with nonidentical job size and scheduling with rejection are all relatively new scheduling models, which are attracting more and more attention recently. In this dissertation, many new results of the above two models on complexities and algorithms are presented:1. We mainly deal with the batch scheduling problem with nonidentical job size to minimize the total completion times. For problem 1|B,s_j,p_j =1|∑]C_j, we use the technique of splitting and put forward for the first time three approximation algorithms with constant ratios, the ratios being 4, 2 and 3/2 respectively. Furthermore, we provide instances to show that the two bounds 2 and 3/2 are tight. Later we make analysis of several existing algorithms for problem 1|B, s_j|∑C_j and show that the worst case ratios of these algorithms can be arbitrarily large2. We make the first study of the two batch scheduling problems with rejection 1|B≥n, rej|∑ω_jT_j + TP and 1|B≥n,rej|∑ω_jU_j + TP. Having known that they are NP-hard, we give pseudo-polynomial time algorithms and FPTAS for them. They are the best exact and approximation algorithms by far. As for the NP-hard problems, the best exact algorithm we can obtain is pseudo-polynomial time algorithm, and the best approximation algorithm can only be FPTAS.