1from __future__ import print_function
2
3from bisect import bisect_right
4
5import quantum_launcher.hampy as hampy
6
7from .scheduler import JobShopScheduler, KeyList, get_label
8
9
[docs]
10def get_jss_hamiltonian(job_dict, max_time, onehot):
11 scheduler = QiskitScheduler(job_dict, max_time, onehot)
12 return scheduler.get_hamiltonian()
13
14
[docs]
15class QiskitScheduler(JobShopScheduler):
16
17 def __init__(self, job_dict, max_time=None, onehot='exact'):
18 super().__init__(job_dict, max_time)
19 self.H_pos_by_label = dict()
20 self.H_label_by_pos = dict()
21 self.onehot = onehot
22
23 def _add_one_start_constraint(self, lagrange_one_hot=1):
24 for task in self.tasks:
25 task_times = {get_label(task, t) for t in range(self.max_time)}
26 onehot_tasks = set()
27 for label in task_times:
28 if label in self.absurd_times:
29 continue
30 else:
31 onehot_tasks.add(self.H_pos_by_label[label])
32 if self.onehot == 'exact':
33 self.H += (~hampy.one_in_n(onehot_tasks, self.n)).hamiltonian
34 elif self.onehot == 'quadratic':
35 self.H += hampy.one_in_n(onehot_tasks, self.n, quadratic=True).hamiltonian
36
37 def _add_precedence_constraint(self, lagrange_precedence=1):
38 for current_task, next_task in zip(self.tasks, self.tasks[1:]):
39 if current_task.job != next_task.job:
40 continue
41 for t in range(self.max_time):
42 current_label = get_label(current_task, t)
43 if current_label in self.absurd_times:
44 continue
45 var1 = self.H_pos_by_label[current_label]
46 for tt in range(min(t + current_task.duration, self.max_time)):
47 next_label = get_label(next_task, tt)
48 if next_label in self.absurd_times:
49 continue
50 var2 = self.H_pos_by_label[next_label]
51 equation = hampy.Equation(self.n)
52 self.H += (equation[var1] & equation[var2]).hamiltonian
53
54 def _add_share_machine_constraint(self, lagrange_share=1):
55 sorted_tasks = sorted(self.tasks, key=lambda x: x.machine)
56 wrapped_tasks = KeyList(sorted_tasks, lambda x: x.machine)
57
58 head = 0
59 while head < len(sorted_tasks):
60
61 tail = bisect_right(wrapped_tasks, sorted_tasks[head].machine)
62 same_machine_tasks = sorted_tasks[head:tail]
63
64 head = tail
65
66 if len(same_machine_tasks) < 2:
67 continue
68
69 for task in same_machine_tasks:
70 for other_task in same_machine_tasks:
71 if task.job == other_task.job and task.position == other_task.position:
72 continue
73
74 for t in range(self.max_time):
75 current_label = get_label(task, t)
76 if current_label in self.absurd_times:
77 continue
78
79 var1 = self.H_pos_by_label[current_label]
80
81 for tt in range(t, min(t + task.duration, self.max_time)):
82 this_label = get_label(other_task, tt)
83 if this_label in self.absurd_times:
84 continue
85 var2 = self.H_pos_by_label[this_label]
86 equation = hampy.Equation(self.n)
87 self.H += (equation[var1] & equation[var2]).hamiltonian
88
89 def _build_variable_dict(self):
90 for task in self.tasks:
91 task_times = {get_label(task, t) for t in range(self.max_time)}
92 for label in task_times:
93 if label in self.absurd_times:
94 continue
95 else:
96 self.H_pos_by_label[label] = len(self.H_pos_by_label)
97 self.H_label_by_pos[len(self.H_label_by_pos)] = label
98 self.n = len(self.H_pos_by_label)
99
[docs]
100 def get_hamiltonian(self):
101 self._remove_absurd_times({}, {}, [])
102 self._build_variable_dict()
103 self._add_one_start_constraint()
104 self._add_precedence_constraint()
105 self._add_share_machine_constraint()
106 # Get BQM
107 # bqm = dwavebinarycsp.stitch(self.csp, **stitch_kwargs)
108
109 # Edit BQM to encourage the shortest schedule
110 # Overview of this added penalty:
111 # - Want any-optimal-schedule-penalty < any-non-optimal-schedule-penalty
112 # - Suppose there are N tasks that need to be scheduled and N > 0
113 # - Suppose the the optimal end time for this schedule is t_N
114 # - Then the worst optimal schedule would be if ALL the tasks ended at time t_N. (Since
115 # the optimal schedule is only dependent on when the LAST task is run, it is irrelevant
116 # when the first N-1 tasks end.) Note that by "worst" optimal schedule, I am merely
117 # referring to the most heavily penalized optimal schedule.
118 #
119 # Show math satisfies any-optimal-schedule-penalty < any-non-optimal-schedule-penalty:
120 # - Penalty scheme. Each task is given the penalty: base^(task-end-time). The penalty
121 # of the entire schedule is the sum of penalties of these chosen tasks.
122 # - Chose the base of my geometric series to be N+1. This simplifies the math and it will
123 # become apparent why it's handy later on.
124 #
125 # - Comparing the SUM of penalties between any optimal schedule (on left) with that of the
126 # WORST optimal schedule (on right). As shown below, in this penalty scheme, any optimal
127 # schedule penalty <= the worst optimal schedule.
128 # sum_i (N+1)^t_i <= N * (N+1)^t_N, where t_i the time when the task i ends [eq 1]
129 #
130 # - Now let's show that all optimal schedule penalties < any non-optimal schedule penalty.
131 # We can prove this by applying eq 1 and simply proving that the worst optimal schedule
132 # penalty (below, on left) is always less than any non-optimal schedule penalty.
133 # N * (N+1)^t_N < (N+1)^(t_N + 1)
134 # Note: t_N + 1 is the smallest end time for a non-optimal
135 # schedule. Hence, if t_N' is the end time of the last
136 # task of a non-optimal schedule, t_N + 1 <= t_N'
137 # <= (N+1)^t_N'
138 # < sum^(N-1) (N+1)^t_i' + (N+1)^t_N'
139 # = sum^N (N+1)^t_i'
140 # Note: sum^N (N+1)^t' is the sum of penalties for a
141 # non-optimal schedule
142 #
143 # - Therefore, with this penalty scheme, all optimal solution penalties < any non-optimal
144 # solution penalties
145
146 # Get BQM
147 decision_hamiltonian = self.H.simplify().copy()
148
149 base = len(self.last_task_indices) + 1 # Base for exponent
150 # Get our pruned (remove_absurd_times) variable list so we don't undo pruning
151 # pruned_variables = list(bqm.variables)
152
153 h = 0
154
155 for i in self.last_task_indices:
156 task = self.tasks[i]
157
158 for t in range(self.max_time):
159 end_time = t + task.duration
160
161 # Check task's end time; do not add in absurd times
162 if end_time > self.max_time:
163 continue
164
165 # Add bias to variable
166 bias = 2 * base ** (end_time - self.max_time)
167 # bias = base**(end_time - 5)
168 # bias = base ** (end_time)
169 label = get_label(task, t)
170 if label in self.absurd_times:
171 continue
172
173 var = self.H_pos_by_label[label]
174 self.H += hampy.Variable(var, hampy.Equation(self.n)).to_equation().hamiltonian
175 # self.H += h / (base * len(self.last_task_indices))
176
177 # Get BQM
178 optimization_hamiltonian = self.H.simplify().copy()
179 return decision_hamiltonian, optimization_hamiltonian, self.H_pos_by_label.copy(), self.H_label_by_pos.copy()
