在周期上分发定期消息

Question

我目前面临一个问题：我有必须定期发送的消息。有多个（不同的）间隔，每个间隔都有多个消息。一个周期中可以放入多少条消息是有限制的。这意味着我必须将间隔开始偏移几个周期来分发消息以避免超过周期限制。

简单示例：

约束：每个周期最多 3 条消息

区间A = 2
- 条消息 [0, 1]
区间 B = 3
- 条消息 [2、3、4、5]

无偏移量

cycle	0	1	2	3	4	5	6	7	8	9
messages	0, 1, 2, 3, 4, 5	-	0, 1	2, 3, 4, 5	0, 1	-	0, 1, 2, 3, 4, 5	-	0, 1	0, 1, 2, 3, 4, 5

cycle	10	11	12	13	14	15	16	17	18	19
messages	0, 1	-	0, 1, 2, 3, 4, 5	-	0, 1	2, 3, 4, 5	0, 1	-	0, 1, 2, 3, 4, 5	-

有偏移量

偏移量 A [0, 1]
偏移量 B [1, 2, 0, 0]

cycle	0	1	2	3	4	5	6	7	8	9
messages	0, 4, 5	1, 2	0, 3	1, 4, 5	0, 2	1, 3	0, 4, 5	1, 2	0, 3	1, 4, 5

cycle	10	11	12	13	14	15	16	17	18	19
messages	0, 2	1, 3	0, 4, 5	1, 2	0, 3	1, 4, 5	0, 2	1, 3	0, 4, 5	1, 2

实际情况比这复杂一点：

这可以通过暴力破解所有可能的组合来解决，但这显然需要很长时间。我已经尝试搜索解决类似问题的算法，但无论我使用什么搜索词，我都没有找到可以用作指南的问题。我已经尝试在上面应用 constrained satisfaction 之类的东西，但我认为它不太适合这种情况。

Answer 1

可以将此问题的实例表述为打包问题并通过整数规划解决它们。我使用了 OR-Tools。这对于您提供的实例，每即时消息的最小数量是 4。

import math
import pprint

from ortools.linear_solver import pywraplp


def distribute(period_to_messages):
    solver = pywraplp.Solver.CreateSolver("SCIP")
    # Maps each message ID to a list of Boolean variables indicating which phase
    # it will have.
    message_to_indicators = {
        message: [solver.BoolVar("") for phase in range(period)]
        for (period, messages) in period_to_messages.items()
        for message in messages
    }
    # Enforces the one-hot constraint for each message's indicator variables.
    for indicators in message_to_indicators.values():
        solver.Add(sum(indicators) == 1)
    # Minimizes the maximum coincidence.
    objective = solver.IntVar(0, solver.infinity(), "")
    solver.Minimize(objective)
    # Standard trick for expressing a maximum to be minimized.
    for t in range(math.lcm(*period_to_messages.keys())):
        # The right-hand side is the coincidence at time t.
        solver.Add(
            objective
            >= sum(
                indicators[t % len(indicators)]
                for indicators in message_to_indicators.values()
            )
        )
    solver.Solve()
    print(objective.solution_value())
    # Decodes the solution.
    return {
        message: phase
        for (message, indicators) in message_to_indicators.items()
        for (phase, indicator) in enumerate(indicators)
        if indicator.solution_value()
    }


pprint.pprint(
    distribute(
        {
            5: [133, 254, 340, 341, 344, 346],
            10: [300],
            20: [
                114,
                115,
                130,
                131,
                132,
                137,
                145,
                162,
                166,
                171,
                203,
                205,
                244,
                245,
                252,
                257,
                262,
                263,
                264,
                265,
                270,
                271,
                272,
                276,
                315,
                316,
                321,
                325,
                330,
                332,
                334,
                335,
                336,
                345,
            ],
            60: [175, 176, 253, 255, 256, 337, 342, 343],
            100: [
                146,
                155,
                156,
                157,
                206,
                213,
                273,
                274,
                275,
                33,
                34,
                350,
                351,
                352,
                353,
                354,
                355,
                46,
                47,
                66,
            ],
        }
    )
)

结果：

4.0
{33: 96,
 34: 89,
 46: 89,
 47: 69,
 66: 86,
 114: 3,
 115: 11,
 130: 19,
 131: 19,
 132: 5,
 133: 1,
 137: 17,
 145: 2,
 146: 74,
 155: 29,
 156: 74,
 157: 49,
 162: 5,
 166: 10,
 171: 2,
 175: 35,
 176: 32,
 203: 18,
 205: 19,
 206: 86,
 213: 8,
 244: 4,
 245: 16,
 252: 4,
 253: 32,
 254: 3,
 255: 35,
 256: 29,
 257: 13,
 262: 3,
 263: 17,
 264: 11,
 265: 19,
 270: 4,
 271: 0,
 272: 2,
 273: 28,
 274: 14,
 275: 56,
 276: 18,
 300: 7,
 315: 7,
 316: 13,
 321: 0,
 325: 10,
 330: 7,
 332: 4,
 334: 10,
 335: 0,
 336: 8,
 337: 29,
 340: 0,
 341: 3,
 342: 32,
 343: 35,
 344: 2,
 345: 5,
 346: 1,
 350: 16,
 351: 66,
 352: 34,
 353: 21,
 354: 88,
 355: 29}

Answer 2

基于数论的替代、无整数规划的方法。适用于周期的 Hasse 图是树的实例（这在代码中被断言，并且满足给定实例）。对于单个周期，想法是在循环中分配阶段方式。处理完全由以下命令排序的多个期间可分性，我们使用一种伙伴分配系统，处理一个阶段对于较小的周期 p，然后将其分解为 q/p 个不同的较大周期 q.

的阶段

import collections
import math
import pprint


def closure_under_gcd(periods):
    closure = set()
    periods = list(periods)
    while periods:
        p = periods.pop()
        if p in closure:
            continue
        periods.extend(math.gcd(p, q) for q in closure)
        closure.add(p)
    return closure


def divides(p, q):
    return q % p == 0


def is_totally_ordered_by_divisibility(periods):
    periods = sorted(periods)
    return all(divides(periods[j - 1], periods[j]) for j in range(1, len(periods)))


class RootDeck:
    def deal(self):
        return 0

    def period(self):
        return 1


class ChildDeck:
    def __init__(self, parent, period):
        self._parent = parent
        self._period = period
        self._phase = self._period // self._parent.period() - 1

    def deal(self):
        self._phase += 1
        if self._phase == self._period // self._parent.period():
            self._parent_phase = self._parent.deal()
            self._phase = 0
        return self._parent_phase + self._phase * self._parent.period()

    def period(self):
        return self._period


def compute_objective(period_to_messages, message_to_phase):
    time_to_messages = [[] for j in range(math.lcm(*period_to_messages.keys()))]
    for period, messages in period_to_messages.items():
        for message in messages:
            for t in range(message_to_phase[message], len(time_to_messages), period):
                time_to_messages[t].append(message)
    return max(map(len, time_to_messages))


def distribute(period_to_messages):
    periods = closure_under_gcd(period_to_messages.keys())
    assert all(
        is_totally_ordered_by_divisibility(math.gcd(p, q) for p in periods if p < q)
        for q in periods
    )
    phase_decks = {1: RootDeck()}
    message_to_phase = {}
    for q in sorted(periods):
        p = max(p for p in phase_decks.keys() if divides(p, q))
        phase_deck = ChildDeck(phase_decks[p], q)
        if q in period_to_messages:
            for message in sorted(period_to_messages[q]):
                message_to_phase[message] = phase_deck.deal()
        phase_decks[q] = phase_deck
    print(compute_objective(period_to_messages, message_to_phase))
    return message_to_phase


pprint.pprint(
    distribute(
        {
            5: [133, 254, 340, 341, 344, 346],
            10: [300],
            20: [
                114,
                115,
                130,
                131,
                132,
                137,
                145,
                162,
                166,
                171,
                203,
                205,
                244,
                245,
                252,
                257,
                262,
                263,
                264,
                265,
                270,
                271,
                272,
                276,
                315,
                316,
                321,
                325,
                330,
                332,
                334,
                335,
                336,
                345,
            ],
            60: [175, 176, 253, 255, 256, 337, 342, 343],
            100: [
                146,
                155,
                156,
                157,
                206,
                213,
                273,
                274,
                275,
                33,
                34,
                350,
                351,
                352,
                353,
                354,
                355,
                46,
                47,
                66,
            ],
        }
    )
)

结果：

4
{33: 15,
 34: 35,
 46: 55,
 47: 75,
 66: 95,
 114: 6,
 115: 16,
 130: 2,
 131: 12,
 132: 7,
 133: 0,
 137: 17,
 145: 3,
 146: 1,
 155: 21,
 156: 41,
 157: 61,
 162: 13,
 166: 8,
 171: 18,
 175: 0,
 176: 20,
 203: 4,
 205: 14,
 206: 81,
 213: 11,
 244: 9,
 245: 19,
 252: 0,
 253: 40,
 254: 1,
 255: 10,
 256: 30,
 257: 10,
 262: 5,
 263: 15,
 264: 1,
 265: 11,
 270: 6,
 271: 16,
 272: 2,
 273: 31,
 274: 51,
 275: 71,
 276: 12,
 300: 1,
 315: 7,
 316: 17,
 321: 3,
 325: 13,
 330: 8,
 332: 18,
 334: 4,
 335: 14,
 336: 9,
 337: 50,
 340: 2,
 341: 3,
 342: 5,
 343: 25,
 344: 4,
 345: 19,
 346: 0,
 350: 91,
 351: 6,
 352: 26,
 353: 46,
 354: 66,
 355: 86}

在周期上分发定期消息

Distribute periodic messages on cycles

python

c++

algorithm

load-balancing