Two Scheduling Problems With Rejection On A Single Machine

In recent years, a series of single machine scheduling problems with learning effects are extensively noticed by people, and the related scheduling models are extensively applied to various scheduling problems. In addition, in the production process, businesses will refuse to product some jobs, because it can improve the efficiency of production, so that more and more domestic and foreign researchers will also take rejection into the scheduling problems. This paper discusses two kinds of scheduling problems related to rejection:First of all, the first chapter introduces to scheduling problems related knowledge,the research status and main research contents in this paper. secondly, the second chapter introduces to scheduling problems related learning and deterioration effects and rejection, in which the jobs have considerable due windows. To discuss two problems, the objective function of the first problem is to minimize earliness,tardiness, the due windows of starting time, the size of due windows and cost of rejection. The objective function of the second problem is to minimize earliness, the number of tardy jobs, the due windows of starting time, the size of due windows and cost of rejection, and according to two problems give two polynomial algorithms,respectively. Again, In the third chapter, the problem is studied with the combination of a fixed unavailability interval,the De Jong’s learning effect and unavailable interval single machine scheduling problems are studied. In this model, the actual processing time of a job is the decreasing function of it’s position. The machine has a fixed unavailable interval, and the jobs are nonresumable. The objective is to minimize makespan. The problem is NP-hard. We give a fully polynominal time approximation scheme. In addition, the results obtained are extended to the case of the job can be rejected.