Appointment scheduling algorithm (N people with N

问题:

Problem statement

We have one employer that wants to interview N people, and therefore makes N interview slots. Every person has a free-busy schedule for those slots. Give an algorithm that schedules the N people into N slots if possible, and return a flag / error / etc if it is impossible. What is the fastest possible runtime complexity?

My approaches so far

Naive: there are N! ways to schedule N people. Go through all of them, for each permutation, check if it's feasible. O( n! )

Backtracking:

1. Look for any interview time slots that can only have 1 person. Schedule the person, remove them from the list of candidates and remove the slot.
2. Look for any candidates that can only go into 1 slot. Schedule the person, remove them from the list of candidates and remove the slot.
3. Repeat 1 & 2 until there are no more combinations like that.
4. Pick a person, schedule them randomly into one of their available slots. Remember this operation.
5. Repeat 1, 2, 3 until we have a schedule or there is an unresolvable conflict. If we have a schedule, return it. If there's an unresolvable conflict, backtrack.

This is O( n! ) worst case, I think - which isn't any better.

There might be a D.P. solution as well - but I'm not seeing it yet.

Other thoughts

The problem can be represented in an NxN matrix, where the rows are "slots", columns are "people", and the values are "1" for free and "0" for busy. Then, we're looking for a row-column-swapped Identity Matrix within this matrix. Steps 1 & 2 are looking for a row or a column with only one "1". (If the rank of the matrix is = N, I that means that there is a solution. But the opposite does not hold) Another way to look at it is to treat the matrix as an unweighed directed graph edge matrix. Then, the nodes each represent 1 candidate and 1 slot. We're then looking for a set of edges so that every node in the graph has one outgoing edge and one incoming edge. Or, with 2x nodes, it would be a bipartite graph.

Example of a matrix:

1 1 1 1
0 1 1 0
1 0 0 1
1 0 0 1

回答1:

As you pointed out, the problem is equivalent to the problem of finding a maximum matching in a bipartite graph (one set of vertices is the set of people and the other on the set of slots, there is an edge between a person and a slot if the person is available for this slot).

This problem can be solved with the Hopcroft-Karp algorithm.

Complexity O(n^(5/2)) in the worst case, better if the graph is sparse.

回答2:

As for the Constraint Programming approach it can be modeled in different ways, for example with a matrix approach and a set based approach.

The set based approach is shown below in the high level CP language MiniZinc. s is the people who are available each time slot (using set notation); the decision variables are the array x (which person should be allotted to each time).

include "globals.mzn"; 
int: n = 4;

% free persons per time slot
array[1..n] of set of int: s =  
[{1,2,3,4},
 {2,3},
 {1,4},
 {1,4}];


% decision variables
% the assignment of persons to a slot (appointment number 1..n)
array[1..n] of var 1..n: x;

solve satisfy;

constraint
  % ensure that the appointed person for the time slot is free
  forall(i in 1..n) (
    x[i] in s[i]
  )
  /\ % ensure that each person get a distinct time slot
  alldifferent(x)
;

output [ show(x) ];

The model outputs these 4 solutions (in 0.5ms), e.g. time 1 is assigned to person 3 etc.

x: [3, 2, 4, 1]
----------
x: [2, 3, 4, 1]
----------
x: [3, 2, 1, 4]
----------
x: [2, 3, 1, 4]

The MiniZinc model is here: appointment_scheduling_set.mzn

The matrix approach model is here (without the output section) and use a standard Integer programming approach: appointment_scheduling.mzn.

int: n = 4;

% rows are time slots
% columns are people
array[1..n, 1..n] of int: m = array2d(1..n, 1..n,
[
1, 1, 1, 1,
0, 1, 1, 0,
1, 0, 0, 1,
1, 0, 0, 1,
]);

% decision variables
% the assignment of persons to a slot (appointment number 1..n)
array[1..n, 1..n] of var 0..1: x;

solve satisfy;

constraint
  forall(i in 1..n) (
    % ensure a free slot
    sum([m[i,j]*x[i,j] | j in 1..n]) = 1

    /\ % ensure one assignment per slot and per person
    sum([x[i,j] | j in 1..n]) = 1
    /\
    sum([x[j,i] | j in 1..n]) = 1
  )
;

The solution from this model is the same, though presented in another (and more verbose) way and - as it happens - in the same order as the set based approach

slot 1: 3
slot 2: 2
slot 3: 4
slot 4: 1
----------
slot 1: 2
slot 2: 3
slot 3: 4
slot 4: 1
----------
slot 1: 3
slot 2: 2
slot 3: 1
slot 4: 4
----------
slot 1: 2
slot 2: 3
slot 3: 1
slot 4: 4

回答3:

This is the Maximum Bipartite Matching problem.

Depending on the density of the graph, the fastest solution is probably the Hopcroft-Karp algorithm, which runs in at most O(N^(5/2)) time, but likely much faster.

回答4:

I believe that you can use network flows.

• Create a vertex u_i for candidate i, and a vertex v_j for slot j.
• Make a source node s and put an (directed) edge from s to each u_i of capacity 1.
• Make a sink node t and put an edge from each v_j to t of capacity 1.
• Put an edge from u_i to v_j if candidate i can interview in slot j.
• We have O(N) vertices and O(N^2) edges, the maximum possible flow is N.
• Find the max flow using, for example, the Ford-Fulkerson algorithm, which takes O(E*f) where E is the number of edges and f is the value of the max flow, so it takes O(N^3).
• If the max flow is N, then we have a schedule: if the edge (u_i,v_j) has flow 1, then we interview candidate i in slot j, otherwise it's impossible.

By the integral flow theorem, the max flow will have integer flows on the edges, which is 0 or 1, so we do have a valid schedule.