预先安排重复任务
在工作中，我们得到一组形式为（任务名称，频率）的约束，其中频率是一个整数，这意味着任务“任务名称”的每次调用之间的滴答数。两个任务不能同时运行，每个任务调用需要一个周期才能完成。我们的目标是找到匹配一组约束的最佳时间表。
例如，如果给定约束 {(a, 2), (b,2)}，则最佳时间表是“ab ab ab...” 另一方面，如果给定约束条件 ({a,2}, {b, 5}, {c, 5})，则最佳时间表可能是“abaca abaca abaca...”
目前，我们通过以下方式找到最佳时间表：运行遗传算法，尝试最小化实际频率与给定约束之间的距离。它实际上工作得很好，但我想知道是否有一些算法更适合此类问题。我尝试在谷歌上搜索，但似乎找不到合适的词（日程安排通常是关于完成任务:()。你能帮忙吗？
At work, we are given a set of constraints of the form (taskname, frequency) where frequency is an integer number which means the number of ticks between each invocation of the task "taskname". Two tasks cannot run concurrently, and each task invocation takes one tick to complete. Our goal is to find the best schedule in terms of matching the set of constraints.
For example, if we are given the constraints {(a, 2), (b,2)} the best schedule is "ab ab ab..."
On the other hand, if we are given the constraints ({a,2}, {b, 5}, {c, 5}) the best schedule is probably "abaca abaca abaca..."
Currently we find the best schedule by running a genetic algorithm which tries to minimize the distance between actual frequencies and the given constrains. It actually works pretty well, but I wonder if there's some algorithm which better suits this kind of problem. I've tried to search Google but I seem to lack the right words (scheduling is usually about completing tasks :(). Can you help?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
首先，考虑 jldupont 评论的优点！ :)
其次，我认为“周期”是元组第二个元素的准确描述，例如{Name，Period [icity]}。
也就是说，看看网络算法。 加权排队的某些变体可能适用于此。
例如，给定N个任务，创建与任务
T0...Tn对应的N个队列，并在基于任务的周期的每个周期（“tick”）中，将一个项目排队到对应的队列中。然后，调度程序算法的目标是最小化（平均）队列中的服务员总数。简单的起点是简单地从具有最多项目数的队列 Qx 中出队。 （排队项目上指示“年龄”的参数将有助于确定优先级。）
First off, consider the merits of jldupont's comment! :)
Second, I think 'period' is the accurate description of the second element of the tuple, e.g. {Name, Period[icity]}.
That said, look to networking algorithms. Some variant of weighted queuing is probably applicable here.
For example, given N tasks, create N queues corresponding to tasks
T0...Tn, and in each cycle ("tick") based on the period of the task, queue an item to the corresponding queue.The scheduler algorithm would then aim for minimizing (on average) the total number of waiters in the queues. Simple starting off point would be to simply dequeue from the quene Qx which has the highest number of items. (A parameter on queued item to indicate 'age' would assist in prioritization.)