algorithm - 具有等待时间和优先级的调度算法

Question

我浏览了一系列调度算法及其实现，但是找不到任何引用来实现解决以下问题的算法。

给定一个有 n 个进程的进程数组，第 i 个进程表示为:

Arrival[i]代表它的到达时间，

Depart[i] 表示进程将终止的时间(处理或未处理无关紧要)和

Time[i] 表示为流程提供服务所需的时间，以及

Preferred[i] 表示一个 bool 值(如果该过程是首选，则为 true，否则为 false)

我们需要安排进程以最大限度地处理首选进程。

一次只能处理一个进程，如果一个进程在完成之前就离开了，就说它是未处理的。否则，流程一旦启动，就无法暂停或中断。

“最佳”解决方案的标准依次是:

1. 最喜欢的流程服务。
2. 服务于大多数非首选流程
3. 最少的总处理时间。

如有任何想法，我们将不胜感激。

Answer 1

我怀疑您最好的解决方案将是一个简单的回溯算法——尝试所有可能性，用“遗漏点”的分数评估每一个:最小化您没有的首选流程的数量完成。

首先，一些预处理:

• 将列表分成列表，首选列表和非列表。
• 按到达时间对每个列表进行排序。
• 对于每个流程，从出发时间减去处理时间；这会产生“最晚开始时间”，这是一个对我们更有用的数字。

现在，只需执行经典的尝试一切递归:

Base Case:
    If process list is empty, move to handling non-preferred processes in a similar function.

Case 1: Serve the first process `P` on the list.
    skipped [remains unchanged]
    new_served_list = served_list + P (append)
    new_start = current start time + `Time(P)`
    new_total = total processing time + `Time(P)`
    // remove processes whose latest start time will be passed:
    new_proc_list = proc_list - {any process with `latest_start(P) < start_time`}.
    Recur on (new_start, new_total, new_served_list, new_proc_list)
    save `result_1`

Case 2: *Don't* serve the first process.
    new_skipped = skipped + 1
    new_proc_list = proc_list - `P`.
    recur on (start, total, served_list, new_proc_list)
    save `result_2

Compare result_1 and result_2; return the better one.

对于非首选进程，您仍然需要一个类似的功能——但该功能必须使进程适应首选进程的间隙。我将把这个扩展留给学生作为练习。 :-)

请注意，它分解为许多小问题，每个开区间一个问题。