我正在尝试寻找一种算法,以在给定一组时隙的情况下优化安排事件。每个事件 (a,b) 是 2 个用户之间的 session ,每个时隙是固定的时间量。 例如。一组可能的事件可以是:[(1,2),(1,3),(4,2),(4,3),(3,1)],有 4 个可能的时隙。所有事件都必须安排在特定时间段内,但是,每个用户的等待时间(两个事件之间的时间)应最小化,同时,等待时间段内的用户数量应最大化。
你知道这个问题的任何可能的算法或启发式吗?
问候
最佳答案
听起来像 Job Shop Scheduling 的组合( video ) 和 session 安排 ( video ) 具有公平约束。两者都是 NP 完全的。
使用简单的贪心构造启发式算法(例如 First Fit Decreasing )和本地搜索(例如 Tabu Search )。对于这些用例,本地搜索比遗传算法产生更好的结果,并且更具可扩展性(参见 proof 的研究竞赛)。
对于公平约束“每个用户的等待时间应该最小化”,惩罚等待时间平方:
关于algorithm - 最短用户等待时间和最大用户等待间隔的最优调度系统,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32287056/