顶点覆盖约束下的同类机排序算法研究

An Algorithm on Uniform Machine Scheduling with Vertex Cover Constraints

给定m台同类机和n个工件,其中第j台机器的速度为sj,第i个工件的加工时间为pi并且在第j台机器上的负载为pi sj.构造一个顶点赋权无向图G=(V,E;w),其中图G的n个顶点代表这n个工件,顶点权重代表相应工件的加工时间.本文研究顶点覆盖约束下的同类机排序问题.该问题是两个组合最优化问题的组合问题,其目标为首先确定图G的一个顶点覆盖,即图的一个顶点子集,使得图中每一条边都至少存在一个顶点属于该子集;然后把这个子集所代表的相应工件集放到m台同类机上加工,使得最大完工时间最小.该问题是NPhard的.本文基于分层算法和LSPT算法设计一个(2+(m−1)·8m/Σ_(j=1^(m)8j))-近似算法,当所有机器的速度都相差不大时,该算法的近似效果较好.

Given m uniform machines and n jobs,let the speed of the jth machine be sj,the processing time of the ith job be pi,which involves that the load on the jth machine is pi sj.Construct a vertex weighted undirected graph G=(V,E;w),where the n vertices of the graph represent the n jobs and the vertex weights represent the processing time of the corresponding jobs.This paper studies the uniform machine scheduling problem with 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 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 NPhard.We design a(2+(m−1)·8m/Σ_(j=1^(m)8j))approximate algorithm based on the layering algorithm and the LSPT algorithm for it.It is realized that the approximation ratio is relatively good when the speeds of all machines are not much different.