On Several Problems Of Batch Scheduling, Scheduling With Rejection And Scheduling With Discretely Processing Times

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, scheduling with rejection and scheduling with discretely compressible processing times are all relatively new scheduling models, which are attracting more and more attention recently. In this dissertation, many new results of the above three models on complexities and algorithms are presented:1. We present an overall survey on batch scheduling;We point out that in the sense of a new way of encoding, batch scheduling with infinite machine capacity and arbitrary release times to minimize total completion time is NP-hard;For the unrelated-parallel-machine-batch-scheduling problem with arbitrary release times to minimize makespan, we present a PTAS in an environment a little wider than uniform machines;For the single machine batch scheduling problem with non-identical job sizes to minimize makespan, when the processing times and job sizes are proportional, we present a lower bound of 3/2 and design an asymptotic PTAS, in the sense that the proportion is a constant.2. We consider for the first time the constraint version of scheduling with rejection as well as the case with non-identical release times. For the problem to minimize the total weighted completion time with the constraint of total penalties, we first verify that it is NP-hard and then design an FPTAS;For the rejection problem with non-identical release times to minimize the total penalties of the rejected jobs plus makespan of the processed ones, we prove its NP-hardness andpresent a PTAS, we also design a best possible algorithm with competitive ratio (5^1/2 + l)/2 for the on-line special case with two distinct release times.3. For the processing-time-discretely-compressible model, we discuss the following two criteria, to minimize makespan with the constraint of total compression cost and to minimize the sum of total weighted completion time plus total cost. For the first problem, we show that it is NP-hard and design an FP-TAS;For the second problem, we point out that it has in fact been proven to be NP-hard by Engels etc.(1998), Wan etc.(2001) and Hoogeveen etc.(2002) independently, which answers the open question proposed by Z.L Chen etc.(1997). We also present a greedy heuristic, which has a bounded worst case performance ratio for a special case and works very well for the general problem over various simulations.