Minimize The Batch Scheduling Problem Of Two Similar Machines Online With Great Completion Time

Scheduling is an important research field of combinatorial optimization. As a branch of the operations research and an applied science, it is widely used in scientific management,computer science and other sectors and has attracted the attention of so many scholars at home and abroad, among which online scheduling and batch scheduling are two new kinds of modern scheduling models. Besides, scheduling online on uniform machines is an important manifestation of the application in actual operation. This article is about the study for this problem.Four chapters are included in this thesis.In the first chapter, some basic notations, definations and background information about the scheduling theory are introduced. We mainly introduce the computational complexity,batch scheduling, on-line scheduling and the main results and innovations of this paper.In the second chapter, we mainly study the problem of on-line scheduling on two uniform machines, where the arrival times and the processing times of jobs are agreeable, the batch capacity is unbounded and the objective is to minimize the makespan.Few are involved in this kind of problem at present. For this problem, we mainly research such a situation, with the time of arriving time getting later, the biggest prosessing time of all the jobs at arriving time ri will be more bigger than the one of all the jobs in the former arriving time, and we can express it by mathematical symbols as following Q₂|r_i < r_j???p_i?p_j, B =? on - line|C_max.In this chapter, at first, we provide an online algorithm,then, we prove the competitive ratio of this algorithm is not bigger than s + ?, where ? is the positive root of ?² + s? - 1 = 0, the speeds of two uniform machines are 1 and s, where s ? 1. when s = 1 , we will get that the competitive ratio of this algorithm is not bigger than 1.618.In the third chapter, we mainly study the problem of on-line scheduling on two uniform machines, where the arrival times of jobs are different, the batch capacity is unbounded and the objective is to minimize the makespan. And we can express it by mathematical symbols as following Q₂|r_i,B = ? on-line|C_max. In this chapter,for this problem, at first, we still use the on-line algorithm mentioned in chapter two, then, we prove the competitive ratio of this algorithm is not bigger than ?s + ??2.In the fourth chapter, we mainly study the problem of on-line scheduling on two uniform machines, where the arrival times and the processing times of jobs are agreeable, the batch capacity is unbounded and the objective is to minimize the flow-time.We mainly research such a situation, with the time of arriving time getting later, the biggest prosessing time of all the jobs at arriving time ri will be less than the ong of all the jobs in the former arriving time, and we can express it by mathematical symbol as following Q₂|r_i <r_j??? p_i > p_j, B =?, on - line|F_max. In this chapter, for this problem, at first,we still use the on-line algorithm mentioned in chapter two, then, we prove the competitive ratio of this algorithm is not bigger than 1+ 1/?.