A Study Of Some Scheduling Problems

Scheduling is one of the most important branches in combinatorial optimization. With the fast development of practical application and theoretical research, various scheduling models can be derived from the original classic. This article launch the research of several different kinds of scheduling problems and focus on approximation algorithm design and estimation of the worst-case ratio. This paper is divided into five chapters.In Chapter1, we first introduce the corresponding concepts, theories and computa-tional complexity briefly. And then we summarize our main research results.In Chapter2, we discuss the scheduling problem of minimizing the sum of quadratic completion times on m parallel machines Pm||ΣCj2. We estimate the scheduling ob-jective value given by the GSPT rule, based on non-convex quadratic programming tech-nique. Then the worst-case ratio according to the GSPT rule is obtained as: if m is even, and,if m is odd.In Chapter3, we concentrate on the scheduling problem of minimizing the weighted total completion time on parallel machines where the processing time of each job can be divided divided into several parts whose processing time are integers. Different parts of the same job can be processed at the same time on different machines. We give approximation algorithm with the worst-case ratio4/3.In Chapter4, we consider two classical scheduling problems Pm||Cmax and Rm||Cmax in the case of privacy-preserving. Consider the situation that the parameters in problems Pm||Cmax and Rm||Cmax are partitioned into groups. Each group is owned by a distinct private entity that is unwilling to share or make public its own data. We construct secure programs based on the privately held data without revealing it. Each unit is capable of their processing strategies after the secure programs is solved and hence the units can cooperate securely.In Chapter5, we discuss two stochastic scheduling problems1|ΣUj and F2|dj=...