Step-like Degenerate Rejectable Sorting Proble

Scheduling is an important branch of operations research,which is widely used in many fields,such as medicine,transportation,management science and computer science.With the development of manufacturing industry and social economy,with some modern scheduling models appear such as the scheduling with deteriorating jobs in the metallurgical industry and the scheduling with rejection which dues to the constraints of resources.Therefore,the scheduling problem with deteriorating jobs and rejection is widely considered by scholars at home and abroad.In the scheduling with deteriorating jobs,if the actual processing time of job is a stepdeteriorating function of its starting time and deteriorating date,we call it the scheduling with step-deteriorating jobs.In this paper,we consider the single-machine,identical-machine and uniform-machine scheduling problems with step-deteriorating jobs and rejection under the condition of common deteriorating date.The objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs.The article consists of five chapters.In Chapter one,we introduce the background of scheduling,complexity theory and some related symbols of the scheduling problem.In Chapter two,we consider the corresponding single-machine scheduling problem.For the case of common deteriorating penalty,we first show that the problem is NP-hard in the ordinary sense.Then we present two pseudo-polynomial algorithms and a 2-approximation algorithm.Furthermore,we propose a fully polynomial time approximation scheme.For the case of common normal processing time,we present two pseudo-polynomial time algorithms,a 2-approximation algorithm and a fully polynomial time approximation scheme.In Chapter three,we consider the identical-machine scheduling.For the two cases of common deteriorating penalty and common normal processing time,we first show that they are all NP-hard.When the number m of machines is a constant,we provide a pseudopolynomial time algorithm and a fully polynomial time approximation scheme.When m is arbitrary,we present a 3-approximation algorithm.In Chapter four,we consider the uniform-machine scheduling.For the case of common deteriorating penalty,we present a pseudo-polynomial time algorithm,a fully polynomial time approximation scheme and a(2+vmax/vmin)-approximation algorithm,where vmax and vmin are the maximum and minimum speeds of the machines,respectively.In Chapter five,we summarize the results of the paper and present some research topics to be considered in the future.