Single Machine Batch Scheduling With Rejection

Scheduling is an important branch of combinatorial optimization. It is extensively applied in many fields, such as management science, computer science, production of industry and agriculture, transportation et al.. Batch scheduling, scheduling with rejection are all relatively new scheduling models, which are attracting more and more attention recently. In this dissertation, we maily discuss the problem of batch scheduling with rejection.Three chapters are included in the dissertation.In the first chapter , we briefly introduced some notation, definition and basic background information about scheduling.In the second chapter, we address the single machine scheduling problem with both batching and rejection. Our objective is to minmize the makespan of the accepted jobs plus the sum of penalties of the rejected ones. For the case with identical job arrivals, we present a dynamic programming algorithm whose time complexity is O(n²logB). The problem is denoted by 1|rej,B|C_max +∑_j∈Re_j.In the third chapter, we consider for the general case with arbitrary job arrivals. For the problem 1|m,rej,B|C_max +∑_j∈Re_j design a PTAS.