Supply Chain Scheduling Linear Deteriorating Jobs With Rejection On A Single Machine

The theory of scheduling is an important branch of combinatorial optimization, it hasreceived close attention from both manufactures and academic researchers since1950s. On thebasis of applying the scheduling theory to the supply chain management, and in the condition ofjobs with deterioration and rejection, the research of supply chain scheduling is to achieve theoptimal objective function as much as possible in this paper. The thesis is divided into threechapters.The first chapter is an introduction, it mainly introduces the combinatorial optimizationproblems, the background of supply chain scheduling and some preliminary knowledge.In the second chapter, we consider the problem of scheduling and distribution on a singlemachine that the processing time of each job is a simple linear function. If each job has arrivaltime, the optimization objective function is to minimize the sum of transportation cost and totalcompletion time or the maximum lateness. If each job has basic processing time, theoptimization objective function is to minimize the sum of transportation cost and the totalweighted completion time or the total completion time. For these problems, we provide somepolynomial time algorithms.In the third chapter, we consider the problem of scheduling and distribution on a singlemachine that jobs with deterioration and rejection. If the job is rejected, we must pay a certainrejection penalty, otherwise the job must be processed and distributed. If these jobs can beprocessed at zero and they also have basic processing time, the optimization objective function isthe to minimize sum of transportation cost, total completion time or the maximum lateness of theaccepted jobs and the total rejection penalty of the rejected jobs. For these problems, we putforward a polynomial time algorithm or a pseudo polynomial time algorithm.