Three Major Problems In Modern Sorting Theory: Game Sorting, Batch Rejecting Sorting And Online Sorting

Technique is important in modern scheduling, which is an important branch of applied mathematics, and there is no standard technique in the process of analyzing and solving scheduling problems. In fact, to solve almost every scheduling problem calls for a different way from the rest,which implies that we have to find new effective method in the face of the unsolved scheduling problems, which is a piece of work that is now highly valued by scholars both at home and abroad.So how to find new method? Do we really have no clue in the process of solving difficult scheduling problems? There is no fixed technique, however, does there exist common guiding thoughts of analyzing scheduling problems and seeking new technique for solving them? Yes, we think this kind of guiding thoughts do exist, and the classification is one of them. This paper studies three important problems of modern scheduling, and shows that the classification is important.The so called classification is a kind of thought of dividing the object of study by its property into some subproblems in order to show their different regularities for further research. In fact, it is a train of thought that comes very naturally, however, as a simple and immediate way for people to learn complex things, the classification can simplify the difficult scheduling problems well and show the innate essential laws of them. So, when we are suffering no new technique and can find no way out in the face of a scheduling problem, the conscious proper use of the classification will often bring unexpected rewards. In fact, the classification has been successfully used in the process of solving scheduling problems many times. This dissertation will show the big role that the classification has played in scheduling research by three specific examples.The first model（Chapter II） is about the problem of strong stability of Nash equilibria in load balancing games of identical servers, in which, every player has an independent job that has to be scheduled on one of the identical servers to minimize the cost of the player himself, given by the workload of the server on which his job is scheduled. Given a Nash equilibrium of our problem,if several player form a coalition for a coordinated deviation, then the cost of each player of the coalition might be reduced so that the Nash equilibrium has no longer been stable. First, if there is no such coordinated deviation in a Nash equilibrium, then it is called strong Nash equilibrium. And given a Nash equilibrium（not a strong Nash equilibrium）, the improvement ratio of a deviation of a player is defined as the ratio between the pre- and post-deviation costs. Then a Nash equilibrium is said to be a ρ-approximate strong Nash equilibrium if there is no coalition of players such that each player of the coalition will have an improvement ratio more than ρ from a coordinated deviation of the coalition. Clearly, the stability of Nash equilibrium improves with a decreasing value of ρ. So, in Chapter II, we have done a series of researches on the approximation of general Nash equilibria to strong Nash equilibria in load balancing games, and with the classification, we prove that any Nash equilibrium is a（5/4）-approximate strong Nash equilibrium, and the bound is tight.The second model（Chapter III） is about the serial batch scheduling problem on m uniform parallel machines to minimize total completion time, where m is fixed. We consider two subproblems of the scheduling problem. In the first subproblem, all jobs have to be scheduled and the objective is to minimize total completion time. In the second subproblem, each job may be either rejected or accepted to be scheduled and the objective is to minimize the sum of total completion time and total rejection penalty. In Chapter III, a polynomial time procedure is presented with the classification to solve both subproblems with the time complexity O(m²n^m+2) and O(m²n^m+5),respectively.The third model（Chapter IV） is about the on-line scheduling problem on parallel machines to minimize the makespan, where all the jobs arrive over time. We consider two subproblems of the on-line scheduling problem. In the first subproblem, there are two uniform machines with speeds 1 and s（s ≥ 1）. In the second subproblem, there are m identical machines. We study the two subproblems with the classification in Chapter IV. For the first subproblem, we show the on-line LPT algorithm has a competitive ratio of（1 +（?））/2 ≈ 1.6180 and the bound is tight, and the on-line LPT algorithm has the best possible competitive ratio if s ≥ 1.8020. For the second subproblem, we present a lower bound of（15-（?））/8 ≈ 1.3596 on the competitive ratio of any deterministic on-line algorithm, which improves a previous result of 1.3473.