Coverage for moptipy / examples / jssp / spaces_sizes.py: 13%
287 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2Computations regarding the size of the solution spaces in a JSSP.
4We represent solutions for a Job Shop Scheduling Problems (JSSPs) as Gantt
5diagrams.
6Assume that we look at JSSPs with n jobs and m machines.
7The number of possible Gantt charts (without useless delays) is
8(jobs!)**machines.
10However, not all of them are necessarily feasible.
11If all jobs pass through all machines in the same order, then all of the
12possible Gantt charts are also feasible.
13However, if, say job 0 first goes to machine 0 and then to machine 1 and
14job 1 first goes to machine 1 and then to machine 0, there are possible
15Gantt charts with deadlocks: If we put the second operation of job 0 to
16be the first operation to be done by machine 1 and put the second operation
17of job 1 to be the first operation to be done by machine 0, we end up with
18an infeasible Gantt chart, i.e., one that cannot be executed.
19Thus, the question arises: "For a given number n of jobs and m of machines,
20what is the instance with the fewest feasible Gantt charts?"
22Well, I am sure that there are clever algorithms to compute this. Maybe we
23can even ave an elegant combinatorial formula.
24But I do not want to spend much time on this subject (and maybe would not
25be able to figure it out even if I wanted to...).
26So we try to find this information using a somewhat brute force approach:
27By enumerating instances and, for each instance, the Gantt charts, and
28count how many of them are feasible.
29"""
30import sys
31from math import factorial, log10
32from typing import Iterable
34import numba # type: ignore
35import numpy as np
36from pycommons.io.path import Path, write_lines
37from pycommons.types import check_int_range
39from moptipy.examples.jssp import experiment
40from moptipy.examples.jssp.gantt_space import gantt_space_size
41from moptipy.examples.jssp.instance import Instance
42from moptipy.utils.lang import Lang
45def permutations_with_repetitions_space_size(n: int, m: int) -> int:
46 """
47 Compute the number of n-permutations with m repetitions.
49 :param n: the number of different values
50 :param m: the number of repetitions
51 :returns: the space size
52 :rtype: int
53 """
54 return factorial(n * m) // (factorial(m) ** n)
57#: the pre-computed values
58__PRE_COMPUTED: tuple[tuple[int, int, int,
59 tuple[tuple[int, ...], ...]], ...] = (
60 (3, 2, 22, ((0, 1), (0, 1), (1, 0))),
61 (3, 3, 63, ((0, 1, 2), (1, 0, 2), (2, 0, 1))),
62 (3, 4, 147, ((0, 1, 2, 3), (1, 0, 3, 2), (2, 3, 0, 1))),
63 (3, 5, 317, ((0, 1, 2, 3, 4), (2, 1, 0, 4, 3), (3, 4, 0, 2, 1))),
64 (4, 2, 244, ((0, 1), (0, 1), (1, 0), (1, 0))),
65 (4, 3, 1630, ((0, 1, 2), (1, 0, 2), (2, 0, 1), (2, 1, 0))),
66 (4, 4, 7451, ((0, 1, 2, 3), (1, 0, 3, 2), (2, 3, 1, 0), (3, 2, 0, 1))),
67 (5, 2, 4548, ((0, 1), (0, 1), (0, 1), (1, 0), (1, 0))),
68 (5, 3, 91461, ((0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1))),
69 (6, 2, 108828, ((0, 1), (0, 1), (0, 1), (1, 0), (1, 0), (1, 0))),
70 (7, 2, 3771792, ((0, 1), (0, 1), (0, 1), (0, 1), (1, 0), (1, 0), (1, 0))),
71 (8, 2, 156073536,
72 ((0, 1), (0, 1), (0, 1), (0, 1), (1, 0), (1, 0), (1, 0), (1, 0))),
73)
76def gantt_min_feasible(jobs: int, machines: int) \
77 -> tuple[int, tuple[tuple[int, ...], ...]]:
78 """
79 Find the minimum number of feasible gantt charts.
81 :param jobs: the number of jobs
82 :param machines: the number of machines
83 :return: the minimum number of feasible solutions for any instance
84 of the given configuration and one example of such an instance
85 """
86 check_int_range(jobs, "jobs", 1, 127)
87 check_int_range(machines, "machines", 1, 127)
89 if machines <= 1:
90 return factorial(jobs), (tuple([0] * jobs), )
91 if jobs <= 1:
92 return 1, (tuple(range(machines)), )
93 if jobs <= 2:
94 return machines + 1, (
95 (*list(range(machines - 2, -1, -1)), machines - 1),
96 (machines - 1, *list(range(machines - 1))))
98 for tup in __PRE_COMPUTED:
99 if (tup[0] == jobs) and (tup[1] == machines):
100 return tup[2], tup[3]
102 if machines <= 2: # if there are two machines, we know the shape
103 lst = [[0, 1]] * (jobs - (jobs // 2))
104 lst.extend([[1, 0]] * (jobs // 2))
105 dest = np.array(lst, dtype=np.uint8)
106 res = __enumerate_feasible_for(jobs, machines, dest)
107 else: # more than two machines: need to enumerate
108 dest = np.ndarray(shape=(jobs, machines), dtype=np.uint8)
109 res = int(__find_min_feasible(np.int64(jobs),
110 np.int64(machines), dest))
112 # turn the result into a tuple
113 arr = tuple(sorted(tuple(int(dest[i, j]) for j in range(machines))
114 for i in range(jobs)))
115 return res, arr
118@numba.njit
119def __copy(dest: np.ndarray, source: np.ndarray, n: np.int64) -> None:
120 """
121 Copy an array.
123 :param dest: the destination
124 :param source: the source
125 :param n: the number of elements to copy
126 """
127 for a in range(n):
128 dest[a] = source[a]
131@numba.njit
132def __copy_instance(dest: np.ndarray, source: np.ndarray,
133 jobs: np.int64, machines: np.int64) -> None:
134 """
135 Copy an instance.
137 :param dest: the destination
138 :param source: the source
139 :param jobs: the number of jobs
140 :param machines: the machines
141 """
142 for a in range(jobs):
143 __copy(dest[a], source[a], machines)
146@numba.njit
147def __find_min_feasible(jobs: np.int64, machines: np.int64,
148 dest: np.ndarray) -> np.int64:
149 """
150 Find the minimum number of feasible gantt charts.
152 :param jobs: the number of jobs
153 :param machines: the number of machines
154 :param dest: the destination array
155 :return: the minimum number of feasible solutions for any instance
156 of the given configuration
157 """
158 instance = np.empty(shape=(jobs, machines), dtype=np.uint8)
159 gantt = np.empty(shape=(machines, jobs), dtype=np.uint8)
160 gantt_index = np.zeros(machines, dtype=np.int64)
161 inst_index = np.zeros(jobs, dtype=np.int64)
162 job_state = np.zeros(jobs, dtype=np.int64)
163 gantt_state = np.zeros(machines, dtype=np.int64)
164 upper_bound: np.int64 = np.int64(9223372036854775807)
166 for i in range(jobs):
167 __first_perm(instance[i], inst_index, i, machines)
169 while True:
170 if __check_sorted(instance, jobs, machines):
171 upper_bound = __enumerate_feasible(
172 instance, gantt, job_state, gantt_state, jobs, machines,
173 upper_bound, gantt_index, dest)
175 k = jobs - 1
176 while True:
177 if __next_perm(instance[k], inst_index, k, machines):
178 break
179 k -= 1
180 if k < 0:
181 return upper_bound
182 for j in range(k + 1, jobs):
183 __first_perm(instance[j], inst_index, j, machines)
186@numba.njit(nogil=True)
187def __check_sorted(instance: np.ndarray,
188 jobs: np.int64,
189 machines: np.int64) -> bool:
190 """
191 Check if the instance is such that all jobs are sorted.
193 :param instance: the instance
194 :param jobs: the number of jobs
195 :param machines: the number of machines
196 :return: `True` if the instance is sorted, `False` otherwise
197 """
198 i: np.int64 = jobs - 1
199 arr1: np.ndarray = instance[i]
200 while i > 0:
201 arr2 = arr1
202 i -= 1
203 arr1 = instance[i]
204 for j in range(machines):
205 if arr1[j] > arr2[j]:
206 return True
207 if arr1[j] < arr2[j]:
208 return False
209 return True
212@numba.njit
213def __is_feasible(instance: np.ndarray,
214 gantt: np.ndarray,
215 job_state: np.ndarray,
216 gantt_state: np.ndarray,
217 jobs: np.int64,
218 machines: np.int64,
219 row: np.int64) -> bool:
220 """
221 Check if a Gantt diagram populated until a given row is feasible.
223 :param instance: the JSSP instance, size jobs*machines
224 :param gantt: the gantt chart, size machines*jobs
225 :param job_state: the job state, of length jobs
226 :param gantt_state: the machine state, of length machines
227 :param jobs: the number of jobs
228 :param machines: the number of machines
229 :param row: the number of valid rows of the Gantt chart
230 :return: `True` if the chart is feasible so far, `False` otherwise
231 """
232 if row <= 1:
233 return True
234 job_state.fill(0) # all jobs start at the 0'th operations
235 gantt_state.fill(0) # all machines start at op 0
236 found: bool = True
237 needed_jobs = jobs # the number of required jobs
239 while found:
240 found = False
241 for job in range(jobs): # check all jobs
242 while True: # we process each job as long as we can
243 js = job_state[job] # which operation is required?
244 if js >= machines:
245 break # the job is already finished
246 nm = instance[job, js] # the machine that the operation needs
247 if nm >= row: # ok, this machine is outside of the chart
248 js += 1 # so we assume it's ok
249 job_state[job] = js # and step forward the state
250 found = True # we did something!
251 if js >= machines: # oh, we finished the job?
252 needed_jobs -= 1 # one less jobs to do
253 if needed_jobs <= 0: # no more jobs to do?
254 return True # the chart is feasible!
255 break # quit handling this job, as its finished
256 continue # move to next operation, as job is not finished
257 ms = gantt_state[nm] # get next item in gantt chart
258 mj = gantt[nm, ms] # next job on this machine?
259 if mj == job: # great, this job!
260 gantt_state[nm] = ms + 1 # advance gantt state
261 js += 1 # so we can perform the operation
262 job_state[job] = js # and step forward the state
263 found = True # we did something!
264 if js >= machines: # oh, we finished the job?
265 needed_jobs -= 1 # one less jobs to do
266 if needed_jobs <= 0: # no more jobs to do?
267 return True # the chart is feasible!
268 break # quit handling this job, as its finished
269 continue # move to next operation, as job is not finished
270 break # no, we cannot handle this job now
272 return False # we ended one round without being able to proceed
275@numba.njit
276def __first_perm(arr: np.ndarray,
277 index: np.ndarray,
278 pi: np.int64,
279 n: np.int64) -> None:
280 """
281 Create the first permutation for a given array of values.
283 :param arr: the array to permute over
284 :param index: the array with the index
285 :param pi: the index of the index to use in pi
286 :param n: the length of arr
287 """
288 for i in range(n):
289 arr[i] = i
290 index[pi] = np.int64(0)
293@numba.njit
294def __next_perm(arr: np.ndarray,
295 index: np.ndarray,
296 pi: np.int64,
297 n: np.int64) -> bool:
298 """
299 Get the next permutation for a given array of values.
301 :param arr: the array to permute over
302 :param index: the array with the index
303 :param pi: the index of the index to use in pi
304 :param n: the length of arr
305 :returns: `True` if there is a next permutation, `False` if not
306 """
307 idx = index[pi]
308 if idx >= n - 1:
309 return False
311 nidx = idx + 1
313 if idx == 0: # increase is at the very beginning
314 arr[0], arr[1] = arr[1], arr[0] # swap
315 idx = nidx
316 while True: # update index to the next increase
317 nidx = idx + 1
318 if nidx >= n:
319 break # reached end
320 if arr[idx] <= arr[nidx]:
321 break # found increase
322 idx = nidx
323 else:
324 if arr[nidx] > arr[0]: # value at arr[idx + 1] is greater than arr[0]
325 # no need for binary search, just swap arr[idx + 1] and arr[0]
326 arr[nidx], arr[0] = arr[0], arr[nidx]
327 else:
328 # binary search to find the greatest value which is less
329 # than arr[idx + 1]
330 start = np.int64(0)
331 end = idx
332 mid = (start + end) // 2
333 t_value = arr[nidx]
334 while not (arr[mid] < t_value < arr[mid - 1]):
335 if arr[mid] < t_value:
336 end = mid - 1
337 else:
338 start = mid + 1
339 mid = (start + end) // 2
340 arr[nidx], arr[mid] = arr[mid], arr[nidx] # swap
342 # invert 0 to increase
343 for i in range((idx // 2) + 1):
344 arr[i], arr[idx - i] = arr[idx - i], arr[i]
345 idx = 0 # reset increase
347 index[pi] = idx
348 return True
351@numba.njit
352def __enumerate_feasible(instance: np.ndarray,
353 gantt: np.ndarray,
354 job_state: np.ndarray,
355 gantt_state: np.ndarray,
356 jobs: np.int64,
357 machines: np.int64,
358 upper_bound: np.int64,
359 index: np.ndarray,
360 dest: np.ndarray) -> np.int64:
361 """
362 Enumerate the feasible gantt charts for an instance.
364 :param instance: the JSSP instance, size jobs*machines
365 :param gantt: the gantt chart array, size machines*jobs
366 :param job_state: the job state, of length jobs
367 :param gantt_state: the machine state, of length machines
368 :param jobs: the number of jobs
369 :param machines: the number of machines
370 :param upper_bound: the upper bound - we won't enumerate more
371 charts than this.
372 :param index: the index array
373 :param dest: the destination array
374 :returns: the number of enumerated feasible gantt charts
375 """
376 counter: np.int64 = np.int64(0)
377 for z in range(machines):
378 __first_perm(gantt[z], index, z, jobs)
380 while True:
381 if __is_feasible(instance, gantt, job_state, gantt_state,
382 jobs, machines, machines):
383 counter += 1 # found another feasible gantt chart for instance
384 if counter >= upper_bound:
385 return counter # if we have reached the minimum, we can stop
387 i = machines - 1
388 while True:
389 if __next_perm(gantt[i], index, i, jobs):
390 if i >= machines - 1:
391 break
392 if __is_feasible(instance, gantt, job_state, gantt_state,
393 jobs, machines, i + 1):
394 for j in range(i + 1, machines):
395 __first_perm(gantt[j], index, j, jobs)
396 break
397 else:
398 i -= 1
399 if i < 0:
400 if instance is not dest:
401 __copy_instance(dest, instance, jobs, machines)
402 return counter # we have enumerated all gantt charts
405@numba.njit
406def __enumerate_feasible_for(jobs: np.int64, machines: np.int64,
407 instance: np.ndarray) -> np.int64:
408 """
409 Find the minimum number of feasible gantt charts.
411 :param jobs: the number of jobs
412 :param machines: the number of machines
413 :param instance: the provided instance array
414 :return: the minimum number of feasible solutions for any instance
415 of the given configuration
416 """
417 gantt = np.empty(shape=(machines, jobs), dtype=np.uint8)
418 gantt_index = np.zeros(machines, dtype=np.int64)
419 job_state = np.zeros(jobs, dtype=np.int64)
420 gantt_state = np.zeros(machines, dtype=np.int64)
421 upper_bound: np.int64 = np.int64(9223372036854775807)
422 return __enumerate_feasible(instance, gantt, job_state,
423 gantt_state, jobs, machines,
424 upper_bound, gantt_index,
425 instance)
428def __long_str(value: int) -> str:
429 """
430 Convert a value to a string.
432 :param value: the value
433 :returns: the string representation
434 """
435 if value < 0:
436 return ""
437 if value <= 1_000_000_000_000:
438 return Lang.current().format_int(value)
439 logg = log10(value)
440 exp = int(logg)
441 base = value / (10 ** exp)
442 expf = Lang.current().format_int(exp)
443 return f"$\\approx$ {base:.3f}*10^{expf}^"
446def make_gantt_space_size_table(
447 dest: str = "solution_space_size.md",
448 instances: Iterable[str] = tuple(list( # noqa
449 experiment.INSTANCES) + ["demo"])) -> Path: # noqa
450 """
451 Print a table of solution space sizes.
453 :param dest: the destination file
454 :param instances: the instances to add
455 :returns: the fully-qualified path to the generated file
456 """
457 file = Path(dest)
458 text = [(f'|{Lang.current()["name"]}|'
459 r"$\jsspJobs$|$\jsspMachines$|$\min(\#\text{"
460 f'{Lang.current()["feasible"]}'
461 r"})$|$\left|\solutionSpace\right|$|"),
462 r"|:--|--:|--:|--:|--:|"]
464 inst_scales: list[tuple[int, int, int, int, str]] = []
466 # enumerate the pre-defined instances
467 for inst in set(instances):
468 instance = Instance.from_resource(inst)
469 min_size = -1
470 for tup in __PRE_COMPUTED:
471 if (tup[0] == instance.jobs) and (tup[1] == instance.machines):
472 min_size = tup[2]
473 break
474 if (min_size < 0) and ((instance.jobs <= 2)
475 or (instance.machines <= 2)):
476 min_size = gantt_min_feasible(
477 instance.jobs, instance.machines)[0]
478 inst_scales.append(
479 (instance.jobs, instance.machines,
480 gantt_space_size(instance.jobs, instance.machines),
481 min_size, f"`{instance.name}`"))
482 del instance
484 # enumerate some default values
485 for jobs in range(2, 6):
486 for machines in range(2, 6):
487 found: bool = False # skip over already added scales
488 for tupp in inst_scales:
489 if (tupp[0] == jobs) and (tupp[1] == machines):
490 found = True
491 break
492 if found:
493 continue
495 min_size = -1
496 for tup in __PRE_COMPUTED:
497 if (tup[0] == jobs) and (tup[1] == machines):
498 min_size = tup[2]
499 break
500 if (min_size < 0) and ((jobs <= 2) or (machines <= 2)):
501 min_size = gantt_min_feasible(jobs, machines)[0]
502 name = "[@fig:jssp_feasible_gantt]" \
503 if (jobs == 2) and (machines == 2) else ""
504 inst_scales.append(
505 (jobs, machines, gantt_space_size(jobs, machines),
506 min_size, name))
508 inst_scales.sort()
509 for i, ua in enumerate(inst_scales):
510 a = ua
511 for j in range(i, len(inst_scales)):
512 b = inst_scales[j]
513 if (a[-1] and b[-1]) and (a[-3] > b[-3]):
514 inst_scales[i] = b # noqa: B909
515 inst_scales[j] = a # noqa: B909
516 a = b
518 text.extend(
519 f"|{scale[4]}|{scale[0]}|{scale[1]}|{__long_str(scale[3])}|"
520 f"{__long_str(scale[2])}|" for scale in inst_scales)
522 with file.open_for_write() as wd:
523 write_lines(text, wd)
524 file.enforce_file()
525 return file
528def make_search_space_size_table(
529 dest: str = "solution_space_size.md",
530 instances: Iterable[str] = tuple(list( # noqa
531 experiment.INSTANCES) + ["demo"])) -> Path: # noqa
532 """
533 Print a table of search space sizes.
535 :param dest: the destination file
536 :param instances: the instances to add
537 :returns: the fully-qualified path to the generated file
538 """
539 file = Path(dest)
540 text = [(f'|{Lang.current()["name"]}|'
541 r"$\jsspJobs$|$\jsspMachines$|$\left|\solutionSpace\right|$|"
542 r"$\left|\searchSpace\right|$|"),
543 r"|:--|--:|--:|--:|--:|"]
544 inst_scales: list[tuple[int, int, int, int, str]] = []
546 # enumerate the pre-defined instances
547 for inst in set(instances):
548 instance = Instance.from_resource(inst)
549 inst_scales.append(
550 (instance.jobs, instance.machines,
551 gantt_space_size(instance.jobs, instance.machines),
552 permutations_with_repetitions_space_size(
553 instance.jobs, instance.machines),
554 f"`{instance.name}`"))
555 del instance
557 # enumerate some default values
558 for jobs in range(3, 6):
559 for machines in range(2, 6):
560 found: bool = False # skip over already added scales
561 for tupp in inst_scales:
562 if (tupp[0] == jobs) and (tupp[1] == machines):
563 found = True
564 break
565 if found:
566 continue
567 inst_scales.append(
568 (jobs, machines, gantt_space_size(jobs, machines),
569 permutations_with_repetitions_space_size(
570 jobs, machines), ""))
572 inst_scales.sort()
573 for i, ua in enumerate(inst_scales):
574 a = ua
575 for j in range(i, len(inst_scales)):
576 b = inst_scales[j]
577 if (a[-1] and b[-1]) and (a[-2] > b[-2]):
578 inst_scales[i] = b # noqa: B909
579 inst_scales[j] = a # noqa: B909
580 a = b
581 text.extend(f"|{scale[4]}|{scale[0]}|{scale[1]}|{__long_str(scale[2])}|"
582 f"{__long_str(scale[3])}|" for scale in inst_scales)
584 with file.open_for_write() as wd:
585 write_lines(text, wd)
586 file.enforce_file()
587 return file
590# create the tables if this is the main script
591if __name__ == "__main__":
592 dest_dir = Path(sys.argv[1])
593 dest_dir.ensure_dir_exists()
594 for lang in Lang.all_langs():
595 lang.set_current()
596 make_gantt_space_size_table(
597 dest_dir.resolve_inside(
598 lang.filename("solution_space_size") + ".md"))
599 make_search_space_size_table(
600 dest_dir.resolve_inside(
601 lang.filename("search_space_size") + ".md"))