使用python安排预订(不是餐厅)

Question

我正在编写一个使用OpenStack的python应用程序,以便学生访问有限数量的虚拟机.

学生可以现在或将来进行预约.

我需要将在任何时间安排的虚拟机数量限制为X,同时仍然允许学生在插槽/预留可用时保留vms.

预订对象如下所示(sqlalchemy).我知道所要求的预约的开始时间和长度,此时我需要通过现有的预订,看看在所要求的时间段内是否有太多的预订.*_job字段是APScheduler作业的名称.

class Reservation(Entity):
    student = ManyToOne('Student', required=True)
    class_id = ManyToOne('Class', required=True)
    image = ManyToOne('Image', required=True)
    # openstack image id filled in once the instance is started
    instance_id = Field(UnicodeText)

    # apscheduler jobs
    stop_instance_job = Field(UnicodeText)
    start_instance_job = Field(UnicodeText)
    warn_reservation_ending_job = Field(UnicodeText)
    check_instance_job = Field(UnicodeText)

有关在何处查找计划算法示例或类似内容的任何指针？我甚至都不清楚要搜索什么...

谢谢.

Answer 1

您应该查找基于网格的调度程序。通常，调度程序不知道真实的执行时间（或资源使用时间），并且使用复杂的启发式方法来猜测问题将花费多长时间（请参阅网格调度程序上的此类启发式方法：PDF 下载描述基于网格的调度）。使用基本网格来表示随时间变化的工作负载的更简单方法很可能会满足您的需求。据我所知，Python 没有任何很棒的网格对象库（不过我之前已经用 C++ 和 Python 实现了一些，而且它们并不太难）。您应该查看 numpy 包，以便更轻松地解释多维对象——它可以很容易地模拟或实现网格。

Msw 提到了 Dijkstra 的银行家算法，它是作业调度的一种形式 - 然而，您的问题更关心未来状态而不是当前状态，并且您可以准确预测（知道其真实值）任务时间。因此，您在注册作业时填写的 T（时间步长）× N（资源数量 - 可能只是 1）× M（最大资源预留）网格就足够了。确定是否可以在特定时间段中安排特定作业的时间复杂度为 O(task_length * M)，检查网格的一个子部分 (start, stop)x(required_resources)x(1,M) 是否有空槽。

为特定作业找到合适的位置（选择开始时间）是一项更困难的任务，可以通过修改后的 Dijkstra 算法或任何标准调度程序来实现（msw 的评论对此任务比时隙能力检查更有帮助） 。请注意，在线的许多调度程序内容都是特定于操作系统进程调度的，它更关心操作的类型（I/O 或非 I/O）以及花费时间超过预期的惩罚，而不是抽象资源的使用。因此，谷歌搜索调度程序通常会为您提供 Linux 调度程序实现，而不是任意数据的技术。尝试查找最短作业调度程序，在解释后，它们通常更简单并且对操作系统任务的依赖程度较低。