График смен для людей, работающих в парах

Я бы планировал смены таким образом, чтобы люди работали в паре.
1. Основным ограничением является то, что время от времени каждый человек не должен работать с человеком, с которым он работал в предыдущую смену.
2. Там не ограничивают время смен, мне просто нужно сопоставить пару с днем.

Например, если {A, B .. F} представляют людей, то
День 1: A-B День 2: C-D День 3: E-F День 4: A-B ‹--- Неправильно, потому что так (1.) нарушается

Мое решение:
Определите фитнес-функцию T, тогда T (A) будет равно 0, если A работал сегодня, или T (A) = c, если A работал в последний раз c дней назад.
Шаги было бы:

  1. Произвести инициализацию пар случайным образом (очевидно, с соблюдением ограничений)
  2. Создайте новую пару (i, j): возьмите элемент (человека) i с наивысшей пригодностью и элемент j со вторыми по величине значениями пригодности, доказывающими, что T (j)! = T (i). (Чтобы не обеспечивать каждый раз разные пары)
  3. Обновлять

Есть способ лучше решить проблему? Есть что-то подобное в литературе, чтобы я мог проконсультироваться? Нравится похожие задачи для примеров? Проблемы с медсестрой вроде как на это?

Спасибо.


optimization scheduling algorithm approximation
person Ewybe    schedule 11.09.2014    source источник
comment
Почему бы просто не составить пары AB, CD, EF, FA, BC, DE, AB, ...? (при условии, что количество человек четное, для нечетных чисел это можно сделать аналогично)   -  person Anton Savin    schedule 12.09.2014
comment
Разве вы не можете просто создать список всех парных комбинаций, а затем отсортировать их в любом порядке? Похоже, вы думаете, что это должно быть сложно.   -  person Mooing Duck    schedule 12.09.2014
comment
Это похоже на планирование кругового турнира.   -  person David Eisenstat    schedule 12.09.2014
comment
Это больше похоже на расписание теннисного клуба, чем на Составление списка сотрудников. Как и в расписании теннисного клуба, у вас есть 2 игровых места в день, и вы можете даже захотеть справедливости назначений (каждый должен работать столько же смен, сколько другие) и справедливости конфронтации (каждый должен работать примерно столько же раз с каждым из остальных). Затем просто добавьте конкретное жесткое ограничение, что для каждой смены, которую работает человек, предыдущая смена этого человека не должна быть с одним и тем же коллегой.   -  person Geoffrey De Smet    schedule 12.09.2014
comment
Да очень похоже   -  person Ewybe    schedule 12.09.2014

Ответы (1)


arrow_upward
1
arrow_downward

Ваша проблема недооценена, что приводит к тривиальным решениям. Например, выберите любых трех человек, {A, B, C}, и запланируйте AB, AC, BC (повторение).

Если вы хотите более справедливое решение: продолжайте выбирать случайную пару каждый день, пока не найдете жизнеспособную пару. Существует не более N нежизнеспособных пар и N (N-1) / 2 возможных пар.

Вот один из способов сделать это:

import random

def schedule(folk):
    excluded = dict((p, None) for p in folk)
    while True:
        while True:
            a, b = random.sample(folk, 2)
            if excluded[a] != b and excluded[b] != a:
                break
        excluded[a], excluded[b] = b, a
        yield a, b

for a, b in schedule('ABCDE'):
    print '%s%s' % (a, b),
person Paul Hankin    schedule 12.09.2014