最短用户等待时间和最大用户等待间隔的最优调度系统
Optimal scheduling system in terms of lowest waiting time for users and maximum users in waiting intervals
我正在尝试寻找一种算法，以在给定一组时隙的情况下优化安排活动。每个事件 (a,b) 是 2 个用户之间的会议，每个时隙是固定的时间量。
例如。一组可能的事件可以是：[(1,2),(1,3),(4,2),(4,3),(3,1)]，有 4 个可能的时隙。所有事件都必须安排在特定时间段内，但是，应尽量减少每个用户的等待时间（两个事件之间的时间），同时，应最大限度地增加等待时间段内的用户数量。
你知道这个问题的任何可能的算法或启发式吗？
问候
您可以通过简单的方法获得 maybe-better-than-random 解决方案：
- 按 lower-numbered 用户优先对每对排序
- 根据 first-user（主键）、second-user（辅助排序键）
对列表进行排序
- 按此顺序安排会议，同时安排所有独立会议。 （就像一个 CPU 指令调度程序向前看独立指令。任何给定的用户仍将按照列出的顺序开会。你只是在这里找到允许的重叠。）
不幸的是，我不是尝试将问题简化为旅行商问题等已知 NP 问题的专家。可能有 polynomial-time 解决方案，但对我来说并不明显。如果没有人提出，请继续阅读：
如果列表不是太大，您可以brute-force检查每个排列。对于每个排列，安排所有会议（同时进行独立会议），然后对每个用户的 last-first 会议时间求和。这就是该排列的分数。取得分最低的排列。
您可以使用随机起点并朝着局部最小值演化，而不是蛮力。系统发育学软件 like phyml 使用此技术搜索 maximum-likelihood 进化树，其具有类似的因子搜索 space.
- 从随机排列开始并评估其分数
- 进行一些随机更改，然后评估分数
- 如果这不是一个改进，请尝试另一种排列，直到找到一个是。 （也许有一种机制可以记住你已经尝试过对起始树的这种修改）。
- 用这棵新树从 2 开始重复，直到收敛到局部最小值。
- 从 1 开始重复一些其他的开始猜测，并取最好的最终结果。
如果你能有效地计算出交换的分数变化，那将大大加快 re-computing 从头开始排列的分数。
这类似于 genetic algorithm。您应该仔细阅读，看看这些想法是否可行。
听起来像是 Job Shop Scheduling (video) and Meeting Scheduling (video) 与公平约束的结合。两者都是 NP 完全的。
使用简单的贪心构造启发式算法（例如First Fit Decreasing) with Local Search (such as Tabu Search). For these use cases, Local Search leads to better results than Genetic Algorithms, as well be more scalable (see research competitions for proof）。
对于公平约束"waiting time per user should be minimised"，惩罚等待时间平方:
我正在尝试寻找一种算法，以在给定一组时隙的情况下优化安排活动。每个事件 (a,b) 是 2 个用户之间的会议，每个时隙是固定的时间量。 例如。一组可能的事件可以是：[(1,2),(1,3),(4,2),(4,3),(3,1)]，有 4 个可能的时隙。所有事件都必须安排在特定时间段内，但是，应尽量减少每个用户的等待时间（两个事件之间的时间），同时，应最大限度地增加等待时间段内的用户数量。
你知道这个问题的任何可能的算法或启发式吗？
问候
您可以通过简单的方法获得 maybe-better-than-random 解决方案：
- 按 lower-numbered 用户优先对每对排序
- 根据 first-user（主键）、second-user（辅助排序键） 对列表进行排序
- 按此顺序安排会议，同时安排所有独立会议。 （就像一个 CPU 指令调度程序向前看独立指令。任何给定的用户仍将按照列出的顺序开会。你只是在这里找到允许的重叠。）
不幸的是，我不是尝试将问题简化为旅行商问题等已知 NP 问题的专家。可能有 polynomial-time 解决方案，但对我来说并不明显。如果没有人提出，请继续阅读：
如果列表不是太大，您可以brute-force检查每个排列。对于每个排列，安排所有会议（同时进行独立会议），然后对每个用户的 last-first 会议时间求和。这就是该排列的分数。取得分最低的排列。
您可以使用随机起点并朝着局部最小值演化，而不是蛮力。系统发育学软件 like phyml 使用此技术搜索 maximum-likelihood 进化树，其具有类似的因子搜索 space.
- 从随机排列开始并评估其分数
- 进行一些随机更改，然后评估分数
- 如果这不是一个改进，请尝试另一种排列，直到找到一个是。 （也许有一种机制可以记住你已经尝试过对起始树的这种修改）。
- 用这棵新树从 2 开始重复，直到收敛到局部最小值。
- 从 1 开始重复一些其他的开始猜测，并取最好的最终结果。
如果你能有效地计算出交换的分数变化，那将大大加快 re-computing 从头开始排列的分数。
这类似于 genetic algorithm。您应该仔细阅读，看看这些想法是否可行。
听起来像是 Job Shop Scheduling (video) and Meeting Scheduling (video) 与公平约束的结合。两者都是 NP 完全的。
使用简单的贪心构造启发式算法（例如First Fit Decreasing) with Local Search (such as Tabu Search). For these use cases, Local Search leads to better results than Genetic Algorithms, as well be more scalable (see research competitions for proof）。
对于公平约束"waiting time per user should be minimised"，惩罚等待时间平方: