1from __future__ import print_function
2
3from bisect import bisect_right
4
5# from pyqubo import Binary
6from .Binary import Binary
7
8from .scheduler import JobShopScheduler, KeyList, get_label
9
10
[docs]
11def get_jss_bqm(job_dict, max_time, disable_till=None, disable_since=None, disabled_variables=None, lagrange_one_hot=3,
12 lagrange_precedence=1, lagrange_share=2):
13 if disable_till is None:
14 disable_till = {}
15 if disable_since is None:
16 disable_since = {}
17 if disabled_variables is None:
18 disabled_variables = []
19
20 scheduler = DWaveScheduler(job_dict, max_time)
21 return scheduler.get_bqm(disable_till, disable_since, disabled_variables,
22 lagrange_one_hot,
23 lagrange_precedence,
24 lagrange_share)
25
26
[docs]
27class DWaveScheduler(JobShopScheduler):
28
29 def __init__(self, job_dict, max_time=None):
30 super().__init__(job_dict, max_time)
31
32 def _add_one_start_constraint(self, lagrange_one_hot=1):
33 """self.csp gets the constraint: A task can start once and only once
34 """
35 for task in self.tasks:
36 task_times = {get_label(task, t) for t in range(self.max_time)}
37 H_term = 0
38 for label in task_times:
39 if label in self.absurd_times:
40 continue
41 if label not in self.H_vars:
42 var = Binary(label)
43 self.H_vars[label] = var
44 else:
45 var = self.H_vars[label]
46 H_term += var
47 self.H += lagrange_one_hot * ((1 - H_term) ** 2)
48
49 def _add_precedence_constraint(self, lagrange_precedence=1):
50 """self.csp gets the constraint: Task must follow a particular order.
51 Note: assumes self.tasks are sorted by jobs and then by position
52 """
53 for current_task, next_task in zip(self.tasks, self.tasks[1:]):
54 if current_task.job != next_task.job:
55 continue
56
57 # Forming constraints with the relevant times of the next task
58 for t in range(self.max_time):
59 current_label = get_label(current_task, t)
60 if current_label in self.absurd_times:
61 continue
62
63 if current_label not in self.H_vars:
64 var1 = Binary(current_label)
65 self.H_vars[current_label] = var1
66 else:
67 var1 = self.H_vars[current_label]
68
69 for tt in range(min(t + current_task.duration, self.max_time)):
70
71 next_label = get_label(next_task, tt)
72 if next_label in self.absurd_times:
73 continue
74 if next_label not in self.H_vars:
75 var2 = Binary(next_label)
76 self.H_vars[next_label] = var2
77 else:
78 var2 = self.H_vars[next_label]
79
80 self.H += lagrange_precedence * var1 * var2
81
82 def _add_share_machine_constraint(self, lagrange_share=1):
83 """self.csp gets the constraint: At most one task per machine per time unit
84 """
85 sorted_tasks = sorted(self.tasks, key=lambda x: x.machine)
86 # Key wrapper for bisect function
87 wrapped_tasks = KeyList(sorted_tasks, lambda x: x.machine)
88
89 head = 0
90 while head < len(sorted_tasks):
91
92 # Find tasks that share a machine
93 tail = bisect_right(wrapped_tasks, sorted_tasks[head].machine)
94 same_machine_tasks = sorted_tasks[head:tail]
95
96 # Update
97 head = tail
98
99 # No need to build coupling for a single task
100 if len(same_machine_tasks) < 2:
101 continue
102
103 # Apply constraint between all tasks for each unit of time
104 for task in same_machine_tasks:
105 for other_task in same_machine_tasks:
106 if task.job == other_task.job and task.position == other_task.position:
107 continue
108
109 for t in range(self.max_time):
110 current_label = get_label(task, t)
111 if current_label in self.absurd_times:
112 continue
113
114 if current_label not in self.H_vars:
115 var1 = Binary(current_label)
116 self.H_vars[current_label] = var1
117 else:
118 var1 = self.H_vars[current_label]
119
120 for tt in range(t, min(t + task.duration, self.max_time)):
121 this_label = get_label(other_task, tt)
122 if this_label in self.absurd_times:
123 continue
124 if this_label not in self.H_vars:
125 var2 = Binary(this_label)
126 self.H_vars[this_label] = var2
127 else:
128 var2 = self.H_vars[this_label]
129
130 self.H += lagrange_share * var1 * var2
131
[docs]
132 def get_bqm(self, disable_till, disable_since, disabled_variables,
133 lagrange_one_hot, lagrange_precedence, lagrange_share):
134 """Returns a BQM to the Job Shop Scheduling problem. """
135
136 # Apply constraints to self.csp
137 self._remove_absurd_times(
138 disable_till, disable_since, disabled_variables)
139 self._add_one_start_constraint(lagrange_one_hot)
140 self._add_precedence_constraint(lagrange_precedence)
141 self._add_share_machine_constraint(lagrange_share)
142 # Get BQM
143 # bqm = dwaveBinarycsp.stitch(self.csp, **stitch_kwargs)
144
145 # Edit BQM to encourage the shortest schedule
146 # Overview of this added penalty:
147 # - Want any-optimal-schedule-penalty < any-non-optimal-schedule-penalty
148 # - Suppose there are N tasks that need to be scheduled and N > 0
149 # - Suppose the the optimal end time for this schedule is t_N
150 # - Then the worst optimal schedule would be if ALL the tasks ended at time t_N. (Since
151 # the optimal schedule is only dependent on when the LAST task is run, it is irrelevant
152 # when the first N-1 tasks end.) Note that by "worst" optimal schedule, I am merely
153 # referring to the most heavily penalized optimal schedule.
154 #
155 # Show math satisfies any-optimal-schedule-penalty < any-non-optimal-schedule-penalty:
156 # - Penalty scheme. Each task is given the penalty: base^(task-end-time). The penalty
157 # of the entire schedule is the sum of penalties of these chosen tasks.
158 # - Chose the base of my geometric series to be N+1. This simplifies the math and it will
159 # become apparent why it's handy later on.
160 #
161 # - Comparing the SUM of penalties between any optimal schedule (on left) with that of the
162 # WORST optimal schedule (on right). As shown below, in this penalty scheme, any optimal
163 # schedule penalty <= the worst optimal schedule.
164 # sum_i (N+1)^t_i <= N * (N+1)^t_N, where t_i the time when the task i ends [eq 1]
165 #
166 # - Now let's show that all optimal schedule penalties < any non-optimal schedule penalty.
167 # We can prove this by applying eq 1 and simply proving that the worst optimal schedule
168 # penalty (below, on left) is always less than any non-optimal schedule penalty.
169 # N * (N+1)^t_N < (N+1)^(t_N + 1)
170 # Note: t_N + 1 is the smallest end time for a non-optimal
171 # schedule. Hence, if t_N' is the end time of the last
172 # task of a non-optimal schedule, t_N + 1 <= t_N'
173 # <= (N+1)^t_N'
174 # < sum^(N-1) (N+1)^t_i' + (N+1)^t_N'
175 # = sum^N (N+1)^t_i'
176 # Note: sum^N (N+1)^t' is the sum of penalties for a
177 # non-optimal schedule
178 #
179 # - Therefore, with this penalty scheme, all optimal solution penalties < any non-optimal
180 # solution penalties
181 base = len(self.last_task_indices) + 1 # Base for exponent
182 # Get our pruned (remove_absurd_times) variable list so we don't undo pruning
183 # pruned_variables = list(bqm.variables)
184 for i in self.last_task_indices:
185 task = self.tasks[i]
186
187 for t in range(self.max_time):
188 end_time = t + task.duration
189
190 # Check task's end time; do not add in absurd times
191 if end_time > self.max_time:
192 continue
193
194 # Add bias to variable
195 bias = 2 * base ** (end_time - self.max_time)
196 label = get_label(task, t)
197 if label in self.absurd_times:
198 continue
199 if label not in self.H_vars:
200 var = Binary(label)
201 self.H_vars[label] = var
202 else:
203 var = self.H_vars[label]
204 self.H += var * bias
205
206 # Get BQM
207 self.model = self.H.compile()
208 bqm = self.model.to_bqm()
209 return bqm
