On-line Scheduling On A Single Batch Processing Machine And Semi On-line Scheduling On Parallel And Uniform Machines With Available Times

Scheduling, as a branch of the operations research and an applied sciences, has its profound practical and broad applied prospect, among which on-line batch-scheduling and semi on-line scheduling with available times have attracted the attention of so many scholars at home and abroad because of their obviously factual meanings. In this paper we mainly deal with these two kinds of problems.Three chapters are included in this thesis.In the first chapter, some notation, definitions and basic background information about the subject are introduced.In the second chapter, we mainly study the problem of on-line batch scheduling on a single machine with jobs having non-identical sizes to minimize makespan and the problem of on-line batch scheduling on uniform machines. Few are involved in these two kinds of problems at present. For the problem 1|r_j,B, s_j|C_max, each job has both processing time and size. We denote the machine capacity by B, a job is called a large one if its size is greater than B/2 , otherwise it is a small job. A batch processing problem is said to satisfy the proportional assumption if the processing time of each large job is not less than that of any small one.In the first part of this chapter, we extend the on-line batch scheduling on a single machine which considers only the number of jobs while forming a batch to one for which each job has a size and all jobs are due to two release time. Furthermore, we provide an on-line algorithm under proportional assumption...