单机排序问题1｜P_k≥P_qP_k／W_k＞P_q／W_q｜sum　from　q＝1　to　n　of　（…）W_q｜c_q－d_q｜近似最优解的伪多项式时间算法

A PSEUDO POLYNOMIAL TIME ALGORITHM THAT IS USED TO FIND APPROXIMATE OPTIMAL SOLUTION OF SCHEDULING PROBLEM P1|P k≥P qP k/W k>P q/W q|nq=1W q| c q-d q|

Ｌａｗｌｅｒ和Ｌｅｎｓｔｒａ已证明［１］：单机排序问题１‖ｎｑ＝１Ｗｑｍａｘ｛（ｃｑ－ｄｑ），０｝是“强”ＮＰ完全的。而该问题是１‖ｎｑ＝１Ｗｑ｜ｃｑ－ｄｑ｜的子问题，因而也是强ＮＰ完全问题，没有好算法。本文在假设Ｐｋ≥ＰｑＰｋ／Ｗｋ＞Ｐｑ／Ｗｑ成立的条件下，设计出求该问题的近似最优解的伪多项式时间算法。

Lawler and Lenstra proved that scheduling problem of single processor P1 ‖nq=1W q {max{(c q-d q,0)} is “strongly”NP complete.But the problem is a subproblem of P1 ‖nq=1W q|c q-d q| .It must also be “strongly” NP complete,there exists no “good” algorithm.In the paper,it proves that under conditions P k≥P qP k/W k>P q/W q ,a pseudo polynomial time algorthm is deduced.