调度算法

发布于 2024-11-29 16:27:10 字数 874 浏览 3 评论 0原文

我有一个调度问题，新作业（执行顺序连接的任务集）每隔几秒左右就会到达。
每个作业都需要以已知的时间间隔分配一些资源。
例如：
作业j1是我们为其预留资源{r1, r2, r3}的一组任务在已知的调度模式上：

r1:[t0 .. t1=t0+td1], 
r2:[t2=t1+td2+i2 .. t3=t2+td3]

t0 是执行的开始时间
td1 是 r1 的资源分配的长度
t1 是 r1 的资源分配的结束时间
i1 是 r1、r2 等之间的等待周期的长度。

时间表示例
在该示例中，在 j1 执行开始后立即调度新作业 j2。 j2 的最早开始时间是 t1。作业可能需要几分钟的执行时间，其中大部分时间都是等待。

我有一个调度程序，它查看当前的预订表，并决定哪个是具有固定分配时间和等待期的新作业的最早可能开始时刻，并相应地进行预订。

（但实际上，等待时间并不需要固定——但在一定百分比（可能是 5%）内，并且资源使用可能有替代方案，例如，如果资源 r3.1 被预订，则 3.2 可能会被预订））

但是，如果需要调度程序（是的，有人建议）能够在新作业到达时动态调整所有调度分配，以最大化完成的总工作量（一天内）通过利用事实上，等待时间不需要完全按照给定的方式进行，并且可以与一些资源重复项并行执行（3.1/3.2），那么我将考虑一种完全不同的调度方案（与我当前的“尽快启动”相比）尽可能的方法）。

那么你会称之为什么调度方案呢？
关于解决（新）问题有什么建议吗？

原文

I have a scheduling problem where new jobs (sets of tasks whose execution is sequentially connected) arrive every few seconds or so.
Each job requires some resources to be allocated at known intervals.
For example:
Job j1 is a set of tasks for which we reserve resources {r1, r2, r3}
on a known scheduling pattern:

r1:[t0 .. t1=t0+td1], 
r2:[t2=t1+td2+i2 .. t3=t2+td3]

t0 being the start time of execution
td1 is the length of the resource allocation for r1
t1 being the end time of the resource allocation for r1
i1 is length of the waiting perioid between r1, r2 and so on.

schedule example

In the example, a new job j2 is being scheduled right after j1 execution has started.
The earliest start time for j2 is t1.
A job may take some minutes of execution most of which consists of waiting.

I have a scheduler that looks at the current reservation table and decides which is the earliest possible starting moment for a new job with fixed allocation times and waiting periods and makes the reservations accordingly.

(But in reality, the waiting period doesn't really need to be fixed - but within some percentage (maybe 5%) and there may be alternatives to resource usage, for example, if resource r3.1 is booked, then 3.2 may be used as such to achieve the same thing.)

However, if the scheduler is required (yes, it's been suggested) to be able to dynamically adjust all the schedule allocations when a new job arrives to maximize the total work done (in a day) by taking advantage of the fact that the waiting times need not be exactly as given and the possibility to parallel execution with some resrouce duplicates (3.1/3.2), then I'd be looking at a completely different scheduling scheme (than my current start-as-soon-as-possible approach).