代码之家 › 专栏 › 技术社区 › Chander Shivdasani

处理具有相同优先级的作业的算法

algorithm

Chander Shivdasani · 技术社区 · 15 年前

我正在从帕帕迪米特洛和瓦齐拉尼的一本叫做算法的书中解决运动问题。

问题如下:

一个服务器有n个客户等待服务。每个客户所需的服务时间是预先知道的:对于客户i来说是ti分钟,因此,例如,如果客户是按照增加i的顺序服务的,那么第i个客户必须等待总和(j=1到n)tj分钟。

我们希望把总的等待时间降到最低。给出一个有效的算法。

我的尝试:

我想了两种方法,但无法决定哪一种方法是最好的,或者其他任何比我更好的方法。

方法1:

以循环方式发球,时间段为5。然而,当我需要在决定时间段时更加小心。它不应该太高或太低。所以,我想选择时间片作为服务时间的平均值。

方法2: 假设作业是根据它们所花费的时间排序的,并存储在数组A中[1…n]

先发球A[1],然后发球N[2],然后发球N-1]等等。

对于这个问题,我真的无法决定哪一个更为理想的解决方案。我错过什么了吗?

谢谢, 钱德尔

2 回复 | 直到 13 年前

theReverseFlick 15 年前

您可以通过添加排序部分和改进循环方法来解决这个问题,

首先根据服务时间对客户进行分类

现在,您也可以检查客户剩余时间是否少于t/2,而不是以循环方式给每个客户一个时间段t,如果这样,就完成了他的任务。

所以对于从第一个排序的列表中的每个客户时间t的服务器客户如果他的剩余时间是<T/2,那么现在就完成他的服务否则转到下一个客户

Achal Dave 13 年前

我假设“总等待时间”是每个客户在服务器完成服务之前等待的时间之和,并且假设客户是按照增加i的顺序被服务的,所以客户 C1 等待T1分钟,客户 C2 等待 t1+t2 会议记录和客户 C3 等待 t1+t2+t3 分钟,然后…顾客 Cn 等待 t1+t2+...+t{n-1}+tn 分钟。

或:

C1 waits: t1
C2 waits: t1+t2
C3 waits: t1+t2+t3
...
Cn waits: t1+t2+t3+...tn

总的等待时间加起来是 n*t1+(n-1)*t2+...1*tn

同样,这是基于这样一个假设:客户是按照增加i的顺序得到服务的。

现在,您希望首先为哪个客户提供服务?

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

2 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

2 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

2 年前