认为全是1。因此，很容易想到贪心准则应该是尽量选取效益值最大的作业安排。但由于起始时间是一个区间0fi1，可以将后面考虑的作业插到前面安排时剩余的空闲时间片里，这是不同的地方。程序522带限期作业安排的贪心算法伪代码GreedyJobfp
f1
和p1
分别代表各项作业的限期和效益值，而且
项作业的排序满足：p1≥p2≥…≥p
localJJ1初始化解集forifrom2to
doifJ∪i中的作业是相容的the
JJ∪i将i加入解中e
dife
dfore
dGreedyJob
f7
定理521算法GreedyJob对于作业排序问题总是得到最优解。证明：假设贪心算法所选择的作业的集合J不是最优解，则一定有相容的作业子集I，其产生更大的效益值。并假定I是具有最大效益值的相容作业子集中使得I∩J最大者。这两个作业集之间没有包含关系。这是因为算法GreedyJob的特性和假定I产生的效益值比J的效益值更大。假设a是JI中具有最大效益的作业，于是，J中比a具有更大效益的作业都应该在I中。现在将作业a加入到I中，得Ia∪I由I的效益值最大，I一定是不相容的。从而，对于I的任一个调度表S，在fa时刻前的时间片都已经被占用。假定S是I的这样一个调度表：在fa时刻之前最大限度的安排了IJ中的作业。如果S中fa时刻之前的作业仍然都是J中的，则I∩J中结束时刻不晚于fa的作业至少有fa个。但aI∩J，这与J的相容性矛盾。因此，S中必有某个作业b∈IJ，其被安排在时刻fa之前的时间片上。在这样的b中选择结束时刻最晚的。由a的选法以及b∈IJ，必然有pa≥pb不然，按照算法，b将先于a被考虑加入到J中。令JIb则J必然具有最大效益值，而且J∩JI∩J与I的选取相

矛盾。故J具有最大效益值。证毕例子设
7p1p2…p
3530252015105d1d2…d
4243483算法GreedyJob的执行过程。为避免调度表调整，将算法GreedyJob稍做改进：在每次选择作业时，在调度表中尽量地向后安排该项作业，这样好为后面的作业安排留下更多的空间。1，34123412123341223123434122301123463412230178多机调度问题设有
项独立的作业12…
由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业分段处理。多机调度问题要求给出一种调度方案，使所给的
个作业在尽可能短的时间内由m台机器处理完。这是一个NP完全r