Coverage for moptipy/examples/jssp/spaces_sizes.py: 13%
287 statements
« prev ^ index » next coverage.py v7.15.2, created at 2026-07-18 11:24 +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 = int(__enumerate_feasible_for( # type: ignore
107 jobs, machines, dest)) # type: ignore
108 else: # more than two machines: need to enumerate
109 dest = np.ndarray(shape=(jobs, machines), dtype=np.uint8)
110 res = int(__find_min_feasible(np.int64(jobs), # type: ignore
111 np.int64(machines), dest))
113 # turn the result into a tuple
114 arr = tuple(sorted(tuple(int(dest[i, j]) for j in range(machines))
115 for i in range(jobs)))
116 return res, arr
119@numba.njit
120def __copy(dest: np.ndarray, source: np.ndarray, n: np.int64) -> None:
121 """
122 Copy an array.
124 :param dest: the destination
125 :param source: the source
126 :param n: the number of elements to copy
127 """
128 for a in range(n):
129 dest[a] = source[a]
132@numba.njit
133def __copy_instance(dest: np.ndarray, source: np.ndarray,
134 jobs: np.int64, machines: np.int64) -> None:
135 """
136 Copy an instance.
138 :param dest: the destination
139 :param source: the source
140 :param jobs: the number of jobs
141 :param machines: the machines
142 """
143 for a in range(jobs):
144 __copy(dest[a], source[a], machines)
147@numba.njit
148def __find_min_feasible(jobs: np.int64, machines: np.int64,
149 dest: np.ndarray) -> np.int64:
150 """
151 Find the minimum number of feasible gantt charts.
153 :param jobs: the number of jobs
154 :param machines: the number of machines
155 :param dest: the destination array
156 :return: the minimum number of feasible solutions for any instance
157 of the given configuration
158 """
159 instance = np.empty(shape=(jobs, machines), dtype=np.uint8)
160 gantt = np.empty(shape=(machines, jobs), dtype=np.uint8)
161 gantt_index = np.zeros(machines, dtype=np.int64)
162 inst_index = np.zeros(jobs, dtype=np.int64)
163 job_state = np.zeros(jobs, dtype=np.int64)
164 gantt_state = np.zeros(machines, dtype=np.int64)
165 upper_bound: np.int64 = np.int64(9223372036854775807)
167 for i in range(jobs):
168 __first_perm(instance[i], inst_index, i, machines) # type: ignore
170 while True:
171 if __check_sorted(instance, jobs, machines):
172 upper_bound = __enumerate_feasible(
173 instance, gantt, job_state, gantt_state, jobs, machines,
174 upper_bound, gantt_index, dest)
176 k = jobs - 1
177 while True:
178 if __next_perm(instance[k], inst_index, k, machines):
179 break
180 k -= 1
181 if k < 0:
182 return upper_bound
183 for j in range(k + 1, jobs):
184 __first_perm(instance[j], inst_index, j, machines) # type: ignore
187@numba.njit(nogil=True)
188def __check_sorted(instance: np.ndarray,
189 jobs: np.int64,
190 machines: np.int64) -> bool:
191 """
192 Check if the instance is such that all jobs are sorted.
194 :param instance: the instance
195 :param jobs: the number of jobs
196 :param machines: the number of machines
197 :return: `True` if the instance is sorted, `False` otherwise
198 """
199 i: np.int64 = jobs - 1
200 arr1: np.ndarray = instance[i]
201 while i > 0:
202 arr2 = arr1
203 i -= 1
204 arr1 = instance[i]
205 for j in range(machines):
206 if arr1[j] > arr2[j]:
207 return True
208 if arr1[j] < arr2[j]:
209 return False
210 return True
213@numba.njit
214def __is_feasible(instance: np.ndarray,
215 gantt: np.ndarray,
216 job_state: np.ndarray,
217 gantt_state: np.ndarray,
218 jobs: np.int64,
219 machines: np.int64,
220 row: np.int64) -> bool:
221 """
222 Check if a Gantt diagram populated until a given row is feasible.
224 :param instance: the JSSP instance, size jobs*machines
225 :param gantt: the gantt chart, size machines*jobs
226 :param job_state: the job state, of length jobs
227 :param gantt_state: the machine state, of length machines
228 :param jobs: the number of jobs
229 :param machines: the number of machines
230 :param row: the number of valid rows of the Gantt chart
231 :return: `True` if the chart is feasible so far, `False` otherwise
232 """
233 if row <= 1:
234 return True
235 job_state.fill(0) # all jobs start at the 0'th operations
236 gantt_state.fill(0) # all machines start at op 0
237 found: bool = True
238 needed_jobs = jobs # the number of required jobs
240 while found:
241 found = False
242 for job in range(jobs): # check all jobs
243 while True: # we process each job as long as we can
244 js = job_state[job] # which operation is required?
245 if js >= machines:
246 break # the job is already finished
247 nm = instance[job, js] # the machine that the operation needs
248 if nm >= row: # ok, this machine is outside of the chart
249 js += 1 # so we assume it's ok
250 job_state[job] = js # and step forward the state
251 found = True # we did something!
252 if js >= machines: # oh, we finished the job?
253 needed_jobs -= 1 # one less jobs to do
254 if needed_jobs <= 0: # no more jobs to do?
255 return True # the chart is feasible!
256 break # quit handling this job, as its finished
257 continue # move to next operation, as job is not finished
258 ms = gantt_state[nm] # get next item in gantt chart
259 mj = gantt[nm, ms] # next job on this machine?
260 if mj == job: # great, this job!
261 gantt_state[nm] = ms + 1 # advance gantt state
262 js += 1 # so we can perform the operation
263 job_state[job] = js # and step forward the state
264 found = True # we did something!
265 if js >= machines: # oh, we finished the job?
266 needed_jobs -= 1 # one less jobs to do
267 if needed_jobs <= 0: # no more jobs to do?
268 return True # the chart is feasible!
269 break # quit handling this job, as its finished
270 continue # move to next operation, as job is not finished
271 break # no, we cannot handle this job now
273 return False # we ended one round without being able to proceed
276@numba.njit
277def __first_perm(arr: np.ndarray,
278 index: np.ndarray,
279 pi: np.int64,
280 n: np.int64) -> None:
281 """
282 Create the first permutation for a given array of values.
284 :param arr: the array to permute over
285 :param index: the array with the index
286 :param pi: the index of the index to use in pi
287 :param n: the length of arr
288 """
289 for i in range(n):
290 arr[i] = i
291 index[pi] = np.int64(0)
294@numba.njit
295def __next_perm(arr: np.ndarray,
296 index: np.ndarray,
297 pi: np.int64,
298 n: np.int64) -> bool:
299 """
300 Get the next permutation for a given array of values.
302 :param arr: the array to permute over
303 :param index: the array with the index
304 :param pi: the index of the index to use in pi
305 :param n: the length of arr
306 :returns: `True` if there is a next permutation, `False` if not
307 """
308 idx = index[pi]
309 if idx >= n - 1:
310 return False
312 nidx = idx + 1
314 if idx == 0: # increase is at the very beginning
315 arr[0], arr[1] = arr[1], arr[0] # swap
316 idx = nidx
317 while True: # update index to the next increase
318 nidx = idx + 1
319 if nidx >= n:
320 break # reached end
321 if arr[idx] <= arr[nidx]:
322 break # found increase
323 idx = nidx
324 else:
325 if arr[nidx] > arr[0]: # value at arr[idx + 1] is greater than arr[0]
326 # no need for binary search, just swap arr[idx + 1] and arr[0]
327 arr[nidx], arr[0] = arr[0], arr[nidx]
328 else:
329 # binary search to find the greatest value which is less
330 # than arr[idx + 1]
331 start = np.int64(0)
332 end = idx
333 mid = (start + end) // 2
334 t_value = arr[nidx]
335 while not (arr[mid] < t_value < arr[mid - 1]):
336 if arr[mid] < t_value:
337 end = mid - 1
338 else:
339 start = mid + 1
340 mid = (start + end) // 2
341 arr[nidx], arr[mid] = arr[mid], arr[nidx] # swap
343 # invert 0 to increase
344 for i in range((idx // 2) + 1):
345 arr[i], arr[idx - i] = arr[idx - i], arr[i]
346 idx = 0 # reset increase
348 index[pi] = idx
349 return True
352@numba.njit
353def __enumerate_feasible(instance: np.ndarray,
354 gantt: np.ndarray,
355 job_state: np.ndarray,
356 gantt_state: np.ndarray,
357 jobs: np.int64,
358 machines: np.int64,
359 upper_bound: np.int64,
360 index: np.ndarray,
361 dest: np.ndarray) -> np.int64:
362 """
363 Enumerate the feasible gantt charts for an instance.
365 :param instance: the JSSP instance, size jobs*machines
366 :param gantt: the gantt chart array, size machines*jobs
367 :param job_state: the job state, of length jobs
368 :param gantt_state: the machine state, of length machines
369 :param jobs: the number of jobs
370 :param machines: the number of machines
371 :param upper_bound: the upper bound - we won't enumerate more
372 charts than this.
373 :param index: the index array
374 :param dest: the destination array
375 :returns: the number of enumerated feasible gantt charts
376 """
377 counter: np.int64 = np.int64(0)
378 for z in range(machines):
379 __first_perm(gantt[z], index, z, jobs) # type: ignore
381 while True:
382 if __is_feasible(instance, gantt, job_state, gantt_state,
383 jobs, machines, machines):
384 counter += 1 # found another feasible gantt chart for instance
385 if counter >= upper_bound:
386 return counter # if we have reached the minimum, we can stop
388 i = machines - 1
389 while True:
390 if __next_perm(gantt[i], index, i, jobs):
391 if i >= machines - 1:
392 break
393 if __is_feasible(instance, gantt, job_state, gantt_state,
394 jobs, machines, i + 1):
395 for j in range(i + 1, machines):
396 __first_perm(gantt[j], index, j, jobs) # type: ignore
397 break
398 else:
399 i -= 1
400 if i < 0:
401 if instance is not dest:
402 __copy_instance(dest, instance, jobs, machines)
403 return counter # we have enumerated all gantt charts
406@numba.njit
407def __enumerate_feasible_for(jobs: np.int64, machines: np.int64,
408 instance: np.ndarray) -> np.int64:
409 """
410 Find the minimum number of feasible gantt charts.
412 :param jobs: the number of jobs
413 :param machines: the number of machines
414 :param instance: the provided instance array
415 :return: the minimum number of feasible solutions for any instance
416 of the given configuration
417 """
418 gantt = np.empty(shape=(machines, jobs), dtype=np.uint8)
419 gantt_index = np.zeros(machines, dtype=np.int64)
420 job_state = np.zeros(jobs, dtype=np.int64)
421 gantt_state = np.zeros(machines, dtype=np.int64)
422 upper_bound: np.int64 = np.int64(9223372036854775807)
423 return __enumerate_feasible(instance, gantt, job_state,
424 gantt_state, jobs, machines,
425 upper_bound, gantt_index,
426 instance)
429def __long_str(value: int) -> str:
430 """
431 Convert a value to a string.
433 :param value: the value
434 :returns: the string representation
435 """
436 if value < 0:
437 return ""
438 if value <= 1_000_000_000_000:
439 return Lang.current().format_int(value)
440 logg = log10(value)
441 exp = int(logg)
442 base = value / (10 ** exp)
443 expf = Lang.current().format_int(exp)
444 return f"$\\approx$ {base:.3f}*10^{expf}^"
447def make_gantt_space_size_table(
448 dest: str = "solution_space_size.md",
449 instances: Iterable[str] = tuple(list( # noqa
450 experiment.INSTANCES) + ["demo"])) -> Path: # noqa
451 """
452 Print a table of solution space sizes.
454 :param dest: the destination file
455 :param instances: the instances to add
456 :returns: the fully-qualified path to the generated file
457 """
458 file = Path(dest)
459 text = [(f'|{Lang.current()["name"]}|'
460 r"$\jsspJobs$|$\jsspMachines$|$\min(\#\text{"
461 f'{Lang.current()["feasible"]}'
462 r"})$|$\left|\solutionSpace\right|$|"),
463 r"|:--|--:|--:|--:|--:|"]
465 inst_scales: list[tuple[int, int, int, int, str]] = []
467 # enumerate the pre-defined instances
468 for inst in set(instances):
469 instance = Instance.from_resource(inst)
470 min_size = -1
471 for tup in __PRE_COMPUTED:
472 if (tup[0] == instance.jobs) and (tup[1] == instance.machines):
473 min_size = tup[2]
474 break
475 if (min_size < 0) and ((instance.jobs <= 2)
476 or (instance.machines <= 2)):
477 min_size = gantt_min_feasible(
478 instance.jobs, instance.machines)[0]
479 inst_scales.append(
480 (instance.jobs, instance.machines,
481 gantt_space_size(instance.jobs, instance.machines),
482 min_size, f"`{instance.name}`"))
483 del instance
485 # enumerate some default values
486 for jobs in range(2, 6):
487 for machines in range(2, 6):
488 found: bool = False # skip over already added scales
489 for tupp in inst_scales:
490 if (tupp[0] == jobs) and (tupp[1] == machines):
491 found = True
492 break
493 if found:
494 continue
496 min_size = -1
497 for tup in __PRE_COMPUTED:
498 if (tup[0] == jobs) and (tup[1] == machines):
499 min_size = tup[2]
500 break
501 if (min_size < 0) and ((jobs <= 2) or (machines <= 2)):
502 min_size = gantt_min_feasible(jobs, machines)[0]
503 name = "[@fig:jssp_feasible_gantt]" \
504 if (jobs == 2) and (machines == 2) else ""
505 inst_scales.append(
506 (jobs, machines, gantt_space_size(jobs, machines),
507 min_size, name))
509 inst_scales.sort()
510 for i, ua in enumerate(inst_scales):
511 a = ua
512 for j in range(i, len(inst_scales)):
513 b = inst_scales[j]
514 if (a[-1] and b[-1]) and (a[-3] > b[-3]):
515 inst_scales[i] = b # noqa: B909
516 inst_scales[j] = a # noqa: B909
517 a = b
519 text.extend(
520 f"|{scale[4]}|{scale[0]}|{scale[1]}|{__long_str(scale[3])}|"
521 f"{__long_str(scale[2])}|" for scale in inst_scales)
523 with file.open_for_write() as wd:
524 write_lines(text, wd)
525 file.enforce_file()
526 return file
529def make_search_space_size_table(
530 dest: str = "solution_space_size.md",
531 instances: Iterable[str] = tuple(list( # noqa
532 experiment.INSTANCES) + ["demo"])) -> Path: # noqa
533 """
534 Print a table of search space sizes.
536 :param dest: the destination file
537 :param instances: the instances to add
538 :returns: the fully-qualified path to the generated file
539 """
540 file = Path(dest)
541 text = [(f'|{Lang.current()["name"]}|'
542 r"$\jsspJobs$|$\jsspMachines$|$\left|\solutionSpace\right|$|"
543 r"$\left|\searchSpace\right|$|"),
544 r"|:--|--:|--:|--:|--:|"]
545 inst_scales: list[tuple[int, int, int, int, str]] = []
547 # enumerate the pre-defined instances
548 for inst in set(instances):
549 instance = Instance.from_resource(inst)
550 inst_scales.append(
551 (instance.jobs, instance.machines,
552 gantt_space_size(instance.jobs, instance.machines),
553 permutations_with_repetitions_space_size(
554 instance.jobs, instance.machines),
555 f"`{instance.name}`"))
556 del instance
558 # enumerate some default values
559 for jobs in range(3, 6):
560 for machines in range(2, 6):
561 found: bool = False # skip over already added scales
562 for tupp in inst_scales:
563 if (tupp[0] == jobs) and (tupp[1] == machines):
564 found = True
565 break
566 if found:
567 continue
568 inst_scales.append(
569 (jobs, machines, gantt_space_size(jobs, machines),
570 permutations_with_repetitions_space_size(
571 jobs, machines), ""))
573 inst_scales.sort()
574 for i, ua in enumerate(inst_scales):
575 a = ua
576 for j in range(i, len(inst_scales)):
577 b = inst_scales[j]
578 if (a[-1] and b[-1]) and (a[-2] > b[-2]):
579 inst_scales[i] = b # noqa: B909
580 inst_scales[j] = a # noqa: B909
581 a = b
582 text.extend(f"|{scale[4]}|{scale[0]}|{scale[1]}|{__long_str(scale[2])}|"
583 f"{__long_str(scale[3])}|" for scale in inst_scales)
585 with file.open_for_write() as wd:
586 write_lines(text, wd)
587 file.enforce_file()
588 return file
591# create the tables if this is the main script
592if __name__ == "__main__":
593 dest_dir = Path(sys.argv[1])
594 dest_dir.ensure_dir_exists()
595 for lang in Lang.all_langs():
596 lang.set_current()
597 make_gantt_space_size_table(
598 dest_dir.resolve_inside(
599 lang.filename("solution_space_size") + ".md"))
600 make_search_space_size_table(
601 dest_dir.resolve_inside(
602 lang.filename("search_space_size") + ".md"))