The Theoretical Analysis And Algorithm Design On Some Scheduling Problems

Scheduling problem is one of the most active branches in operations research and combinatorial optimization. Since the 50’s of the last century, scheduling has gained great attention from the researchers of manufacturing production, supply chain management, internet and so on. With the need of theoretical research and practical, a lot of new models are proposed in these years. This thesis studies some new models of three kinds of scheduling problems which are hybrid flow shop scheduling problem, two-level supply chain problem and job scheduling game under a hybrid scheduling policy. For the models of the ?rst two problems, this thesis mainly focus on computational complexity and optimal algorithm design.And for the models of the last problem, this thesis mainly focus on analysis of the price of anarchy. The thesis is split into four chapters.We ?rst introduce some concepts and theories of scheduling problems, computational complexity and algorithm and job scheduling game, then we summarize the background and some recent research results of above three kinds of scheduling problems in Chapter 1.In Chapter 2, a two-machine two-stage flow shop problem with flexible tasks is considered. Each job has two tasks, the ?rst task can be processed on either machine, called flexible task, while the second task must be processed on the second machine and can’t be processed unless the ?rst task is completed. The problem is to determine the assignment of the flexible tasks to the machines for each job, with the objective of minimizing the makespan. We present a fully polynomial time approximation scheme(FPTAS) for the problem. Moreover, we consider the problems with identical jobs and buffer capacity, and present some optimal algorithms for them. For the problems with identical jobs, we ?nd an interesting result: If the buffer is not less than 2, more buffer capacity can not bring better result.In Chapter 3, a two-level supply chain problem is studied which is closely related to the batch sizing scheduling problem with earliness and tardiness penalties. In the problem, there are K customer orders, where each customer order consisting of some unit length jobs has a due date. The jobs are processed in a common machine and then delivered to their customers in batches, where the size of each batch has upper and lower bounds and each batch may incur a ?xed setup cost which can also be considered a ?xed delivery cost. The goal is to ?nd a schedule which minimizes the sum of the earliness and tardiness costs and the setup costs incurred by creating a new batch. We ?rst present some structural properties of the optimal schedules for single-order problem with an additional assumption(a): The jobs are consecutively processed from time zero. Based on these properties, we give a polynomial-time algorithm for single-order problem with assumption(a). Then we give dynamic programming algorithms for some special cases of multiple-order problem with assumption(a). At last, we present some structural properties of the optimal schedules for single-order problem without assumption(a) and give a polynomial-time algorithm for it.In Chapter 4, a job scheduling game is considered, where each job is a sel?sh agent and chooses one machine that minimizes its own cost which is its weighted completion time. Every job is available at time zero and the preemption is not allowed. Each machine is also available at time zero and declares its own scheduling policy. It is different from most other similar researches that different machines are allowed to declare different scheduling policies. In this paper, there are two scheduling policies(Weighted Shortest Processing Time policy and Proportional Sharing policy) can be chosen by machines. The social cost is the total weighted completion times of all jobs rather than the maximal load over all machines(makespan) which is a common goal in the previous studies. For this job scheduling game, ?rst we write a linear programming relaxation for this problem. Then,we write down the dual of above linear programming. By discussing the relationship between four values: the optimal objectives of above linear programming and the dual linear programming, the minimal social cost for all feasible mixed strategy-pro?les and the maximal social cost for all mixed Nash equilibriums of this job scheduling game, we give the main result of this paper: the Mixed Price of Anarchy(MPo A) of this job scheduling game is exactly 4.