Scheduling Problems With Rejection And Semi On-line Scheduling On Two Uniform Machines

Scheduling, as a branch of operations research and applied mathematics, has its profound practical and broad applied prospect. In this paper we mainly deal with two kinds of scheduling problems with rejection and a semi on-line scheduling problem.In classical scheduling models, it is usually assumed that all jobs must be processed and that the processing time is given unchanged. While in many ap-plications, a job could not be processed if its processing time or processing cost is very large. We could choose to pay some charge to send it outside for "out processing", or buy finished product. The scheduling problems we considered are not only to minimize the regular objective functions, but also make the total cost of rejected jobs be in an acceptable interval. This is the so-called problem of scheduling with rejection.In most classical literature of scheduling theory, problems are classified as off-line and on-line. If full information on jobs to be scheduled is available in advance, we call the scheduling problem off-line. By contrast, if the jobs are not known ahead of time, but arrive one by one, and we are required to schedule jobs irrevocably on the machines as soon as they are given, without any knowledge about jobs that follow later on, this problem is called on-line. But semi-online is neither off-line nor on-line, but somehow in between.Three chapters are included in this thesis.In the first chapter, we describe the research development of the scheduling, some useful information and the main results obtained in this thesis.In the second chapter, we consider the scheduling with rejection. The ob-jective functions are to minimize the total completion time and the maximum completion time of the processed ones when the total compression cost is given. Firstly, we prove that the problem and the problem are all N P-hard. Then, we design two pseudo-polynomial time dynamic algo-rithms and FPTAS.In the third chapter, we consider a semi on-line scheduling problem on two uniform machines where the largest processing time is known in advance. The objective function is to minimize the maximum job completion time. Algorithms with corresponding competitive ratio are presented for the considered problem.