A Proof Of NP-hardness And A FPTAS For The Batching Problem With Rejection

Due to its profound significance in both theory and real world, scheduling has always been a hot topic in the research of combinatorial optimization. It is widely used in computer science, management, scientific, agricultural and in-dustrial production, transports and other sectors. Scheduling with rejection and batching scheduling are all relatively new scheduling models, which are attracting more and more attention recently. In this dissertation, many new results of the two models on complexities and algorithms arc presented.There are three chapters in this article.In the first chapter, some notations, definitions and basic background infor-mation about the subject are introduced. And then the main research results about this dissertation have been summarized.In the second chapter, we study the batch scheduling problems with rejec-tion. Scheduling problems have been widely studied in the last two decades. For traditional research, it is always assumed that we have to process all the jobs. In the real world, however, we can make a higher-level decision, i.e., we can break the assumption by rejecting certain jobs, of course, we should pay a correspond-ing penalty. We consider the unbounded parallel batch machine scheduling with objective is to minimize the sum of the maximum tardiness (maximum lateness) of the accepted jobs and the total rejection penalty of the rejected jobs for the first time. We show that this problem is NP-hardIn the third chapter.we provide a pseudo-polynomial-time algorithm.Finally a2-approximation algorithm and a fully polynomial-time approximation scheme are given for the problem.