单处理器作业调度问题
现在有 $N$ 个作业 $j_1,j_2,\ldots,j_N$, 已知对应的运行时间分别为 $t_1,t_2,\ldots,t_N$. 而处理器只有一个.
目标是使作业平均完成的时间最小化.
要求: 这里我们非抢占调度(nonpreemptive scheduling), 即 一旦开始一个作业, 就必须把该作业运行完.
References:
Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, (Third Edition).
张怀勇 等译, 《数据结构与算法分析 C++ 描述》(第三版) [Chapter 10. Page. 297]
https://study.com/academy/lesson/preemptive-vs-non-preemptive-process-scheduling.html