需要在单台计算机上处理n个作业。作业j需要t j个时间单位来执行，并且利润值为p j。所有作业都应按时间安排W = t [j]个时间单位的总和。将作业j调度为在时间s j开始可以获利（W-s j）* p j。 我已经对p j
和s j以及pj * tj分别进行了贪婪的尝试，但已经能够提出反例。我认为可以通过使用p j / t j递减的贪婪算法来解决，但无法证明这一点。我只是在寻找有关如何正式证明它的提示。
需要在单台计算机上处理n个作业。作业j需要tj个时间单位来执行，其利润值为pj。所有作业都应按时间计划W = tjtime单位的总和。...
我以前见过的一种方法是考虑在建议的时间表中交换两个相邻的作业。假设我们有1,2，其中其他内容将花费时间K，然后我们达到了最后期限。如果