Several Problems Of One Machine Batch Scheduling With Rejection

Bath scheduling is a class of combinatorial optimization problems which has strong application background and are emerged in the early 1990s. It is mainly come from large-scale modernization production assembly line. Scheduling prob-lems with with rejection are a new type problem appeared in recent years. These problems fit the actual situation and has more important reality significance. In this thesis we combine bath scheduling with rejected scheduling and discuss some bath scheduling problems with rejection. The structure of this article is as follows:In the first chapter, we mainly introduce the background of scheduling prob-lems, related notations and elementary knowledge needed. Then, we surmmarize the chief results and innovation points of this paper.In the second chapter, we first prove the single machine bath scheduling problem which the objective is to minimize the sum of total weighted comple-tion time and rejection cost is NP-hard. Then give a pseudo-polynomial time algorithm based on dynamic programming and a FPTAS.In the third chapter, we first discuss bath scheduling problem with regection under two special circumstances. One is bounded bath scheduling problem with regection whose objective is to minimize total weighted completion time. It is discussed under a number of special circumstances such as each job is of the equal processing time, all jobs have two different arrival time. The other is unbounded bath scheduling problem with regection whose objective is to minimize the maximum delay. It is discussed under the situation of all the jobs are of the same rejection cost. Last, we respectively give polynomial time algorithms for these two problems based on dynamic programming.