如何在(到达时间，执行时间)事先已知的情况下*最优*求解N个作业的调度，使得N个作业的平均等待时间最小？
有人能解释一下如何最佳地解决这个问题吗？
很明显，即使这两个链接说 SJF 是最优的，贪婪的方法也不会产生最佳解决方案（我认为他们不考虑平均等待时间，而是有最小化总执行时间的标准）。
> < Li > < p > http://www . cs . jhu . edu/~ yairamir/cs 418/os2/SLD 026 . htm
http://os.etf.bg.ac.rs/OS2/Stud/Rad01/sjf.htm
从我对这个问题的了解来看，似乎需要详尽地列出所有可能的作业时间表（排列）。但我不确定是否有一种基于动态编程的方法可以让人们获得最佳解决方案，而不必详尽地找到所有可能排列的平均等待时间。
问题：在n不同作业的（r_i，t_i）数组中给出了作业请求时间和作业长度时间的列表。r_i表示作业请求何时进入，即作业的到达时间或请求时间，t_i表示作业执行所用的时间单位。只有一个人处理作业，一次只能处理一个作业。
使用输入数组（r_i、t_i）计算一组给定的 N 个作业的最短平均等待时间？
示例:list (r_i，t_i): job-1(0，3)，job-2(2，5)，job-3(3，2)
如果作业按作业-1、作业-2、作业-3的顺序完成，则：
job-1=作业结束时间-作业请求时间=3-0
job-2=8-2=6的等待时间
作业 3 的等待时间 = 10-3 = 7
所以平均等待时间是：（3 6 7）/3。
但是如果这些工作是按照job-1， job-3， job-2的顺序完成的：平均等待时间是：（3 2 8）/3=13/3，这比原来的顺序要好。所以最小平均等待时间是13/3时间单位。
编辑：
>
作业的等待时间定义为（完成时间 - 到达或请求时间）。人们也可以称之为周转时间。问题是最小化总等待时间/N，这与最小化总等待时间相同，如果假设等待时间的定义不同（作业开始时间 - 作业到达时间）。
SJF(最短作业优先)未给出最佳计划的示例:
J1（1，5）J2（2，2）J3（0，3）
最短作业 j2。但是选择 j3， j2， j1 比在 j2， j3， j1 中首先选择 j2 （等待时间 = 4 7 11） 更好
在时间0时，最短作业是J1。J1-J2作为排班给出的总等待时间为100 102。J2-J1计划给出的最佳总等待时间为3 103。
共有2个答案
听起来像是NP完全的作业车间调度（这是一种奇特的说法，今天没有人知道如何在合理的时间和横向扩展中最佳地解决它）。
研究一些算法，如构造启发式算法，然后是局部搜索（如禁忌搜索）。这些算法最有效，如MISTA 2013等学术组件所证明的。有关相关实现，请参阅我的开源项目作业调度和任务分配优化实现/视频。
您的描述中有一些不清楚的地方：是否允许抢占？即是否可以停止一项工作，开始另一项工作，然后再完成这项工作。在这两种情况下，您都可以查看此网站，以了解您的问题是NP难还是多项式可解。
-
< li >如果允许抢占，问题很容易解决，写成1 | pmtnrj|∑Cj < li >如果不允许抢占，1|rj|∑Cj是NP难的，因此您不可能找到贪婪算法来解决您的问题。
此外，查看完成时间的总和或等待时间的总和是严格等价的，您只需添加/删除发布日期和处理时间的总和。
-
我的目标是计算抢占最短作业优先调度算法的平均等待时间。 假设作业的到达时间以2个单位为间隔，如0,2,4,6……即，第一个作业以0个单位进入，第二个作业在2个单位的时间后进入，以此类推。 我为我的程序测试了 3 个测试用例并得到了正确答案： 测试用例1： 作业：8,4,9,5 平均时间：6.5 测试用例2： 作业：7,4,1,4 平均时间：3 但是当我把一个有1000个作业的文件作为输入时，我得到
-
我们知道优先级调度可以是抢占式的或非抢占式的。这两个中的哪一个通常平均等待时间最少？？它们的性能会根据测试用例而变化吗？？
-
给定下表，用于计算基于优先级的抢占式调度的流程和平均等待时间。 甘特图如下： 我有以下问题： 1） 周转时间是否 = 19 个单位？ 2)如何计算平均等待时间？有公式吗？ 3)如果很少有进程具有相同的优先级，该怎么办？ 我是操作系统的新手。我看过其他一些类似的问题，但我不知道该怎么做。
-
好吧，我们有贪婪的作业调度算法（调度最大数量的作业）。我们可以使用不同的技术 最短的作业优先 最早开始时间在先 首先将冲突降至最低的作业 最早的结束时间在前 我有前三种策略的反例，但我找不到第四种策略的反例。 以下是前三种方法的反例 最短的作业优先: 最早开始时间： 首先是冲突最小的工作： 这里我们可以安排4个冲突为3，4，4，3的作业，而不是3个冲突最小的作业，即2，3，3 那么，最后一个最早的
-
我有一个问题，如何同时对到达时间和突发时间进行排序。我的代码首先检查较低的突发时间，然后检查到达时间。 最短作业优先(非抢占式)CPU调度检查进程突发时间，如果< code >进程具有最短的突发时间和到达时间，则执行该进程。 下面是我对数组进行排序的代码片段: 下面是上面代码片段的结果: 如果排序公式正确，这应该是输出： 参考：最短作业优先 （SJF）
-
假设以下进程在指定的时间到达执行。每个进程将运行列出的时间量。 我想绘制甘特图并计算抢占式最短作业优先调度的平均等待时间。 解决办法 http://imgur.com/fP8u61C 等待时间为2毫秒。 请告诉我这是否正确。 我怀疑的步骤是，在进程B到达的3ms时，调度程序是完成进程A还是启动进程B。