Rejectable Batch Sorting Problem Based On Degradation Effect

Schedule problem is a typical combinatorial optimization problem and an important branch of operations research.And parallel-batch scheduling problems with deteriorating jobs or rejection are new modern scheduling model generated from actual production.In this paper,for some objectives such as minimizing the makespan of scheduled jobs plus the total rejection penalties of rejected jobs,we consider the design and the analysis of some algorithms.And we address the two-machine flow-shop scheduling with deterioration jobs and rejection.The main results in the paper are listed as follows:In Chapter 1,we introduce some basic concepts of scheduling problems such as computational complexity,approximate algorithm and so on.And at the same time,some related scheduling models and their theoretical background and application prospect are expounded.In Chapter 2,we consider the bounded parallel-batch scheduling with with deteriorating jobs and rejection.When jobs have identical release dates,we design a pseudo-polynomial time algorithm based on the dynamic programming and a fully polynomial time approximation schemes.When jobs have 8)different release dates,we propose a pseudo-polynomial time dynamic programming algorithm and a 2-approximate algorithm and analyse these algorithms.In Chapter 3,we consider the unbounded parallel-batch scheduling with with deteriorating jobs and rejection in which jobs have identical release dates.For minimizing of the makespan of scheduled jobs plus the total rejection penalties of rejected jobs problem,we design one polynomial time optimal algorithms.And for minimizing of the total weighted completion time of scheduled jobs plus the total rejection penalties of rejected jobs problem,we analyze the computational complexity and propose a,and we design a fully polynomial time approximation schemes for the special case that jobs have identical weights.pseudopolynomial time dynamic programming algorithmIn Chapter 4,we discuss the two-machine flow-shop scheduling problems with deteriorating jobs and rejection.The objection is to minimize the makespan of scheduled jobs plus the total rejection penalties.We prove that the given problem is NP-hard,and propose one pseudo-polynomial time algorithm.Furthermore,we design a polynomial time optimal algorithm for one special case.