Single Machine Scheduling Problems With Due-window And Rejection

Scheduling is one of significant problems in combinatorial optimization. In thispaper we consider a single machine scheduling with due-window and rejection. Themain content is as following：Firstly, we introduce some background knowledge of scheduling problem andwhat I do in this paper.In second chapter, we consider a single machine scheduling with due-windowand rejection. In this model, the jobs have to be split into a set of accepted jobs and aset of rejected jobs. We assume that every accepted job has an undetermineddue-window and the size of due-window is identical. There is no cost where the job iscompleted during the due-window, but there is cost where the job is completed prioror after the due-window. The cost of the rejected jobs depends on the rejected jobs.The goal is to determine the optimal sequence of accepted jobs and minimize the totalcost of two sets jobs. In this part, we first given some important properties andconclusions, and some discussion of the optimal solutions; then we proof that theproblem is solvable in polynomial time. We provided a dynamic programmingalgorithm and numerical example for the problem. At the end of the chapter weextend the problem to the scheduling model with position-dependent processing times.By convert the problem into a series of assignment problems we proved that theproblem is polynomial solvable.In third chapter, we extended model of second chapter to the scheduling withmaintenance activity. We consider a single machine scheduling with due-window,maintenance activity and rejection. There are two cases: maintenance activity starttime is t0and maintenance activity start time is equal to the completion time of ajob. The time of the maintenance activity is a fixed value. The processing time of thejob that process after the maintenance activity will be reduced. The goal is todetermine the location of the maintenance activity and the optimal sequence ofaccepted jobs to minimize a total costs including accepted jobs and rejection jobs. Weconvert two versions of the problem into the assignment problems and proved that theproblem is polynomial solvable. A numerical example is given. Last, summarize thewhole dissertation and research work in the future is pointed out.