关键词: 组合最优化问题, 顶点覆盖, 分层, 同类机, 近似比,  , 排序

Abstract: Given $m$ uniform machines and $n$ jobs, let the speed of the $j$th machine be $s_{j}$, the processing time of the $i$th job be $p_ {i}$, which involves that the load on the $j$th machine is $\frac{p_i}{s_j}$. Construct a weighted undirected graph $\hat{G} = (V, E; W)$, where the $n$ vertices of the graph represent the $n$ jobs and the vertex weight represents the processing time of the corresponding job. This paper studies the uniform machine scheduling problem under some vertex cover constraints, which is a combinatorial problem of two combinatorial optimization problems. The goal is to firstly determine a vertex cover of the graph $\hat{G}$, that is, a vertex subset of the graph, such that the subset contains at least one endpoint of each edge and then to minimize the makespan when all the jobs corresponding to the subset are put to process on the $m$ uniform machines. The problem is NP-hard. We design a $(2+{(m-1)\cdot s_m\over \sum_{j=1}^m s_j})$- approximate algorithm based on the layering algorithm and the LSPT algorithm for it, and it is realized that the approximation ratio is relatively good when the speeds of all machines are not much different.

Key words: Combination optimization problem, Vertex cover, Layering,  , Uniform machine,  , Approximation ratio, Scheduling