%0 Journal Article
%T 具有先序约束的平行机排序问题<br>Parallel Machine Scheduling Problem with Precedence Constraints
%A 陈雪
%A 廖礼琴
%A 张同全
%J Advances in Applied Mathematics
%P 3693-3698
%@ 2324-8009
%D 2021
%I Hans Publishing
%R 10.12677/AAM.2021.1011392
%X 根据财务系统中的回避原则，构造了具有先序约束的平行机排序问题的模型，目标函数为最小化最大负载，证明了具有先序约束的平行机排序问题是一个NP-完备问题。为之设计了LPTM算法，并分析了其近似比为3-1/m。<br />
According to the avoidance principle in the financial system, a model of the parallel machine scheduling problem with precedence constraints is constructed, and the objective function is to minimize the maximum load, which is proved that the parallel machine scheduling problem with precedence constraints is an NP-complete problem. We design the LPTM algorithm and analyze its approximate ratio to <span>3-1/m</span>.
%K 平行机，排序，先序约束，近似算法<br>Parallel Identical Machines
%K Scheduling
%K Precedence Constraints
%K Approximation Algorithms
%U http://www.hanspub.org/journal/PaperInformation.aspx?PaperID=46357