| Batching scheduling is an important class of optimization problems with a lot of practical applications. It is widely applied to the large-scale modern autonomous systems, such as semiconductor manufacturing, aerospace industry, iron and steel casting and so on. Therefore, it has important theoretic and practical significance to study the algorithms and mechanisms for various models of batching scheduling problems.Research on batching scheduling problems mainly focuses on two aspects:one is the algorithm design to pursue the overall optimization, and the other is the scheduling mechanism design for the systems with selfish agents in a game situation. The models and problems concerned in the thesis is as follows:(1) Algorithm design for the on-line parallel-batching scheduling problem:the model of the on-line parallel-batching scheduling model discussed is described as: there is a set of independent jobs J={J1,...,Jn} which can be handled on m parallel-batching machines{M1,...,Mm}; each job Jj(1≤i≤n) has its processing time of pj and becomes available at its release date r., which is unknown in advance; each machine can handle up to B jobs as a batch simultaneously, and all the jobs in a batch start and complete at the same time; the processing time of a batch is the maximum of the processing times of jobs belonging to it. On-line means the information regarding the jobs is not known in advance until they arrive. Once a batch is started, it cannot be stopped until its completion. The study goal is to design a process of batching scheduling that involves assigning all the jobs to the batches and machines and determining the order of process of batches so as to optimize the global objective.(2) Coordination mechanism design for a parallel machine scheduling game situation:the scheduling game discussed can be described as:a coordination mechanism is a set of scheduling policies, one for each machine, that determines how to schedule the jobs that have selected the machine; each job corresponds to an independent and selfish agent who pursues his own objective by selfishly choosing one machine to process his job depending on the coordination mechanism and does not care about the waste of social resources. The System has a social cost. Given a coordination mechanism, selfish agents will achieve a Nash equilibrium, which achieves a social cost accordingly maybe with higher social cost compared with the optimal social cost. Therefore, the goal of the coordination mechanism design is to propose a mechanism such that the corresponding Nash equilibrium can be achieve the social cost as optimal as possible.In this paper we focus on the design of algorithms and mechanism for two parallel-batching scheduling models. The main results are:First, we discuss the problem of minimizing the global makespan in the model, where there are n on-line scheduling jobs with release dates on m parallel bounded batch processing machines, and each job has a unit processing time. Two different online algorithms with the same competitive ratio1+α:Unified Algorithm and Greedy Algorithm Aa; are proposed. It is also shown that the competitive ratio1+α is the best possible.Next, we discuss the problem of semi-online scheduling jobs with release dates on m parallel bounded batch processing machines to minimize the makespan under game situation. In this problem, it is assumed that the upper bound of the total number of jobs is known in advance, each job Jj(1≤i≤n) has a unit processing time, the nonnegative release date rj is a rational number and min given in advance. We propose a coordinate mechanism, called Delayed Coordination Mechanism, construct a Nash equilibrium and prove the uniqueness of the Nash equilibrium under this mechanisms by giving a greedy algorithm. Furthermore, for the Delayed Coordination Mechanism, the price of anarchy (PoA) is given, which is a measure of the comparison of the social costs between the global optimization and the Nash equilibrium, therefore, the efficiency of the designed mechanism is demonstrated. |
PDF Full Text Request