在不同日期随机分配一组人员时，最佳方法是什么？

Question

所以，我有一个安装问题。但我不确定这是不是我必须张贴的地方

上下文

基本上我想让不同的学习小组

• 有很多学生
• 有很多导师

但是，每个人每周都有一组可用的天数来参加一次学习。 每个人只能参加一个研究小组

可用性示例

StudentA = [Tuesday, Wednesday]
StudentB = [Wednesday, Saturday]
StudentC = [Saturday]

TutorA= [Tuesday, Friday]
TutorB = [Tuesday]

我必须让学习小组

• 有2到4名学生
• 有2至3名导师

---

我的方法

我正在使用python 3 我正在尝试生成所有可能的组合，并使用可用人员列表筛选实际可能的案例：

1. 我用代码命名每个学生可用性组合：

   • [星期二]=>；“p1”
   • [星期三]=>；“p2”
   • [星期二、星期三、星期四]=>；“第7页”

2. 导师也是这样

   • [星期二]=>；“c1”
   • [星期三]=>；“c2”
   • [星期二、星期三、星期四]=>；“c7”

3. 我使用itertools.compositions_和替换来制作所有

• 学生组合
• 导师组合

1. 我将之前的两种组合组合组合成可能的研究组

2. 我将所有团队组合起来生成场景

3. 我使用限制进行过滤

   • 每个人被分配到一个研究组
   • 每个人只参加一次
   • 学生比老师多

---

问题

正如人们所期望的，组合和排列产生了大量的可能性

我可以接受将天数限制为三天

但我仍然无法为我的普通电脑提供可接受的性能

有没有更好的方法我没有看到？我在想象一些线性代数是否能把这个问题转化成一组方程，但不确定

Obs：学生和导师的数量要大得多（每人20到50人）

Answer 1

上下文

按每周7天的可用性指定学生

例如：

 [
    [1, 1, 0, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 1],
    [1, 1, 0, 1, 0, 1, 1],
    [0, 1, 0, 1, 0, 1, 0]
  ]

每行为一名学生（即本例中为4名学生） 每列表示一周中的一天（即7），可用或不可用分别为1或0

因此[1, 1, 0, 0, 0, 0, 0]表示学生0在一周的前两天，即周一和周二有空

TA可用性也有类似规定

例如：

[
    [1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 1]
]

显示有三个助教，每天都有第一个助教

会议安排如下：

               7 Days with N sessions per day numbered 0 to N-1

Session    Monday   Tuesday  Wednesday  Thursday  Friday   Saturday   Sunday
0          session  session  session   session   session   session    session
1          session  session  session   session   session   session    session
2          session  session  session   session   session   session    session
3          session  session  session   session   session   session    session
            ...
N-1        session  session  session   session   session   session    session

N未知，但我们可以选择一个适当的大值（即，如果N get只导致更多未分配给学生或助教的课程）

制约因素包括：

• 每节课2至4名学生
• 学生每周只上一节课
• 学生只在空闲时间被分配一节课
• 每节课2至3个助教
• 助教仅在其可用日分配课程

的目标是找到满足约束条件的学生和助教的作业

方法

使用谷歌ortools Contstraint Solver

ortools允许将这个组合问题描述为搜索问题

参考：ortools youtube Tutorail

代码

from ortools.sat.python import cp_model    # Google Constraint Modeling Tool (https://developers.google.com/optimization/cp/cp_solver)
from tabulate import tabulate              # For displaying results in table form (https://pypi.org/project/tabulate/)

week_days = ("Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday")
                                      
def main(student_availability, ta_availability):
    ########################################################
    # Information Setup
    ########################################################
    num_days = len(week_days)     # days in a week we are using
                                    
    num_students = len(student_availability)
    num_days = len(student_availability[0])
    all_students = range(num_students)
    all_days = range(num_days)
    
    # Show student availability
    special = u'\u2713'
    tmp_table = [[special if c else 'x' for c in row] for row in student_availability]
    display_table(tmp_table, "Students", "Students Availability")
 
 
    num_tas = len(ta_availability)
    all_tas = range(num_tas)
    
    # Show TA availability
    tmp_table = [[special if c else 'x' for c in row] for row in ta_availability]
    display_table(tmp_table, "     TAs", "\nTA Availability")
    
    # Learning sessions 
    #  Model as max sessions per day, 7 days a weeks
    #  The solver will decide which sessions are assigned students and TAs
    max_sessions_per_day = num_students       # Would actually use a lot fewer sessions per day
    all_sessions = range(max_sessions_per_day)
 
    ########################################################
    # Creates the model
    ########################################################
    model = cp_model.CpModel()
    
    ########################################################
    # Specify Constraints
    ########################################################
    
    session_zero = {}             # sessions with zero students and TAs (i.e. unused)
    session_bound = {}            # sessions which satisfy the student and TA occupancy bounds
    for d in all_days:
        for session in all_sessions:
            session_zero[(d, session)] = model.NewBoolVar('zero%id%ig' % (d, session))
            session_bound[(d, session)] = model.NewBoolVar('bound%id%ig' % (d, session))
            model.Add(session_zero[(d, session)] + session_bound[(d, session)]==1)  # Sessions are used or unused

    # Student Constraints
    student_group = {}
    for s in all_students:
        for d in all_days:
            for session in all_sessions:
                student_group[(s, d, session)] = model.NewBoolVar('student_assigned%is%id%ig' % (s, d, session))
                
    # Each used session has between 2 & 4 students
    for d in all_days:
        for session in all_sessions:
            # Meeting define by (d, session)
            students_assigned = sum(student_group[(s, d, session)] for s in all_students)
            model.Add(students_assigned==0).OnlyEnforceIf(session_zero[(d, session)])
            model.Add(students_assigned >= 2).OnlyEnforceIf(session_bound[(d, session)])
            model.Add(students_assigned <= 4).OnlyEnforceIf(session_bound[(d, session)])
                
    # Every student is assigned one session in the week on their available days
    for s, row in enumerate(student_availability):
        available_days = [d for d, v in enumerate(row) if v > 0]
        model.Add(sum(student_group[(s, d, session)] for d in available_days for session in all_sessions) == 1)
        
    # No Studentss are assigned sessions on their unavailable days
    for t, row in enumerate(student_availability):
        unavailable_days = [d for d, v in enumerate(row) if v == 0]
        model.Add(sum(student_group[(t, d, session)] for d in unavailable_days for session in all_sessions) == 0)
                
        
    # TA Constraint
    ta_group = {}
    for t in all_tas:
        for d in all_days:
            for session in all_sessions:
                ta_group[(t, d, session)] = model.NewBoolVar('ta_assigned%is%id%ig' % (t, d, session))

            
    # Each session has between 2 & 3 TAs
    for d in all_days:
        for session in all_sessions:
            ta_assigned = sum(ta_group[(t, d, session)] for t in all_tas)
            model.Add(ta_assigned==0).OnlyEnforceIf(session_zero[(d, session)])
            model.Add(ta_assigned >= 2).OnlyEnforceIf(session_bound[(d, session)])
            model.Add(ta_assigned <= 3).OnlyEnforceIf(session_bound[(d, session)])

    # TAs are assigned on available days
    for t, row in enumerate(ta_availability):
        available_days = [d for d, v in enumerate(row) if v > 0]
        model.Add(sum(ta_group[(t, d, session)] for d in available_days for session in all_sessions) >= 0)
        
    # No TAs are assigned on their unavailable days
    for t, row in enumerate(ta_availability):
        unavailable_days = [d for d, v in enumerate(row) if v == 0]
        model.Add(sum(ta_group[(t, d, session)] for d in unavailable_days for session in all_sessions) == 0)
                
    # Creates the solver and solve.
    solver = cp_model.CpSolver()
    
    # Sets a time limit of 10 seconds.
    solver.parameters.max_time_in_seconds = 10.0
 
    # Display the first five solutions.
    a_few_solutions = range(2)
    solution_printer = StudentsPartialSolutionPrinter(student_group,
                                                      num_students, 
                                                      ta_group, 
                                                      num_tas,
                                                      num_days, 
                                                      max_sessions_per_day,
                                                      student_availability,
                                                      ta_availability,
                                                      a_few_solutions)
    
    status = solver.Solve(model, solution_printer)
    print()
    print('Status = %s' % solver.StatusName(status))
    print('Number of solutions found: %i' % solution_printer.solution_count())


    # Statistics.
    print()
    print('Statistics')
    print('  - conflicts       : %i' % solver.NumConflicts())
    print('  - branches        : %i' % solver.NumBranches())
    print('  - wall time       : %f s' % solver.WallTime())
    print('  - solutions found : %i' % solution_printer.solution_count())

class StudentsPartialSolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, 
                 student_group,
                 num_students, 
                 ta_group, 
                 num_tas,
                 num_days, 
                 max_sessions_per_day, 
                 student_availability,
                 ta_availability,
                 sols):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self._student_group = student_group
        self._num_students = num_students
        self._ta_group = ta_group
        self._num_tas = num_tas
        self._num_days = num_days
        self._max_sessions_per_day = max_sessions_per_day
        self._student_availability = student_availability
        self._ta_availability = ta_availability
        self._solutions = set(sols)
        self._solution_count = 0

    def on_solution_callback(self):
        if self._solution_count in self._solutions:
            print('\nSolution %i' % self._solution_count)
            # Student Scheduling
            table = [[u'\u2713' if col else 'x' for col in row] for row in self._student_availability]
            
            for session in range(self._max_sessions_per_day):
                    for d in range(self._num_days):
                        for s in range(self._num_students):
                            if self.Value(self._student_group[(s, d, session)]):
                                table[s][d] = table[s][d] + f" {week_days[d][:3]}-{session}"
            print()    
            display_table(table, "Students", "Students Scheduling")
                      
   
            # TA scheduling
            table = [[u'\u2713' if col else 'x' for col in row] for row in self._ta_availability]
            for session in range(self._max_sessions_per_day):
                    for d in range(self._num_days):
                        for s in range(self._num_tas):
                            if self.Value(self._ta_group[(s, d, session)]):
                                table[s][d] = table[s][d] + f" {week_days[d][:3]}-{session}"
                
            
            print()
            display_table(table, "     TAs", "TA Scheduling")

        self._solution_count += 1
 
    def solution_count(self):
        return self._solution_count

def display_table(data, data_category, message):
    ''' Display data in tabular form'''
    table = [[f'{idx:>8}'] + row for idx, row in enumerate(data)]
    print(message)
    print(tabulate(table, headers=(data_category,) + week_days, tablefmt="rst"))
    
if __name__ == '__main__':
    # Student Information
    student_availability = [
        [1, 1, 0, 0, 0, 0, 0],
        [1, 0, 1, 0, 0, 0, 1],
        [1, 1, 0, 1, 0, 1, 1],
        [0, 1, 0, 1, 0, 1, 0]
    ]
    
    # TA Information
    ta_availability = [
        [1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0],
        [1, 0, 0, 1, 0, 0, 1]
    ]
    
    # Find solutions
    main(student_availability, ta_availability)

输出

指定的问题需要三个会话 星期一（星期一至三）和星期四（星期四至零）

Students Availability
==========  ========  =========  ===========  ==========  ========  ==========  ========
  Students  Monday    Tuesday    Wednesday    Thursday    Friday    Saturday    Sunday
==========  ========  =========  ===========  ==========  ========  ==========  ========
         0  ✓         ✓          x            x           x         x           x
         1  ✓         x          ✓            x           x         x           ✓
         2  ✓         ✓          x            ✓           x         ✓           ✓
         3  x         ✓          x            ✓           x         ✓           x
==========  ========  =========  ===========  ==========  ========  ==========  ========

TA Availability
==========  ========  =========  ===========  ==========  ========  ==========  ========
       TAs  Monday    Tuesday    Wednesday    Thursday    Friday    Saturday    Sunday
==========  ========  =========  ===========  ==========  ========  ==========  ========
         0  ✓         ✓          ✓            ✓           ✓         ✓           ✓
         1  ✓         x          x            x           x         x           x
         2  ✓         x          x            ✓           x         x           ✓
==========  ========  =========  ===========  ==========  ========  ==========  ========

Solution 0

Students Scheduling
==========  ========  =========  ===========  ==========  ========  ==========  ========
  Students  Monday    Tuesday    Wednesday    Thursday    Friday    Saturday    Sunday
==========  ========  =========  ===========  ==========  ========  ==========  ========
         0  ✓ Mon-3   ✓          x            x           x         x           x
         1  ✓ Mon-3   x          ✓            x           x         x           ✓
         2  ✓         ✓          x            ✓ Thu-0     x         ✓           ✓
         3  x         ✓          x            ✓ Thu-0     x         ✓           x
==========  ========  =========  ===========  ==========  ========  ==========  ========

TA Scheduling
==========  ========  =========  ===========  ==========  ========  ==========  ========
       TAs  Monday    Tuesday    Wednesday    Thursday    Friday    Saturday    Sunday
==========  ========  =========  ===========  ==========  ========  ==========  ========
         0  ✓ Mon-3   ✓          ✓            ✓ Thu-0     ✓         ✓           ✓
         1  ✓ Mon-3   x          x            x           x         x           x
         2  ✓         x          x            ✓ Thu-0     x         x           ✓
==========  ========  =========  ===========  ==========  ========  ==========  ========

Status = OPTIMAL
Number of solutions found: 1

Statistics
  - conflicts       : 0
  - branches        : 0
  - wall time       : 0.014649 s
  - solutions found : 1