/
appointment_scheduling.pi
138 lines (105 loc) · 3.89 KB
/
appointment_scheduling.pi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/*
Appointment scheduling in Picat.
From Stack Overflow
"Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)"
http://stackoverflow.com/questions/11143439/appointment-scheduling-algorithm-n-people-with-n-free-busy-slots-constraint-sa
""
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:
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.
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.
Repeat 1 & 2 until there are no more combinations like that.
Pick a person, schedule them randomly into one of their available slots. Remember
this operation.
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
I have a feeling that this might be NP-C.
""
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import util.
import cp.
main => go.
go =>
println("Matrix based approach:"),
L1 = findall(X,appointment_scheduling(X)),
foreach(S1 in L1)
foreach(R in S1)
writeln(R)
end,
nl
end,
println("\nSet based approach:"),
L2 = findall(X,appointment_scheduling2(X)),
foreach(S2 in L2)
writeln(S2)
end,
nl.
% Matrix based approach
appointment_scheduling(X) =>
N = 4,
% The allowed slots
M = [[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)
X = new_array(N,N),
X :: 0..1,
% constraints
foreach(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
sum([X[I,J] : J in 1..N]) #= 1,
sum([X[J,I] : J in 1..N]) #= 1
end,
solve(X).
%
% "Set based" approach
%
appointment_scheduling2(X) =>
N = 4,
% The allowed splots
M = [[1, 2, 3, 4],
[2, 3],
[1, 4],
[1, 4]],
% decision variables
% the assignment of persons to a slot (appointment number 1..N)
X = new_list(N),
X :: 1..N,
% constraints
all_different(X),
foreach(I in 1..N)
% ensure a free slot
member(X[I], M[I])
end,
solve(X).