Coverage for moptipy / examples / jssp / instance.py: 83%
227 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2A representation and collection of Job Shop Scheduling Problem instances.
4The Job Shop Scheduling Problem (JSSP) is one of the classical NP-hard
5problems from operations research. Here we provide a class (:class:`Instance`)
6to represent and load their data as well as a collection of common JSSP
7instances from literature.
9Our problem instances are actually extensions of :class:`numpy.ndarray`. They
10present the basic instance data as a matrix, where each row corresponds to a
11job. Each row has twice the number of machines elements. In an alternating
12fashion, we store the machines that the job needs to go to as well as the time
13that it needs on the machines, one by one. Additionally, the instance name,
14the number of machines, and the number of jobs are provided as attributes
15(although the latter two can easily be inferred from the shape of the matrix).
16Nevertheless, this memory layout and encapsulation as :class:`~numpy.ndarray`
17are the most efficient way to store the data I could come up with.
19You can directly load the most common JSSP instances using
20:meth:`~Instance.from_resource` by providing their mnemonic name. With
21:meth:`~Instance.list_resources`, you can obtain a list of string mnemonic
22names of all JSSP instances available as resource.
24This collection of common instances stems from the repositories [1-5], each of
25which containing some or all of them. The instances themselves were originally
26published by different researchers in literature [6-14].
281. John Edward Beasley. OR-Library: Distributing Test Problems by Electronic
29 Mail. *The Journal of the Operational Research Society (JORS).*
30 41:1069-1072. November 1990. doi: https://doi.org/10.1057/jors.1990.166
312. Jelke Jeroen van Hoorn. *Job Shop Instances and Solutions.* 2015.
32 http://jobshop.jjvh.nl
333. Jelke Jeroen van Hoorn. The Current State of Bounds on Benchmark Instances
34 of the Job-Shop Scheduling Problem. *Journal of Scheduling.* 21(1):127-128.
35 February 2018. doi: https://doi.org/10.1007/s10951-017-0547-8
364. Oleg V. Shylo. *Job Shop Scheduling (Personal Homepage).* August 2019.
37 Knoxville, TN, USA. http://optimizizer.com/jobshop.php
385. Thomas Weise. *jsspInstancesAndResults: Results, Data, and Instances of the
39 Job Shop Scheduling Problem.* Hefei, Anhui, China: Institute of Applied
40 Optimization, School of Computer Science and Artificial Intelligence, Hefei
41 University. 2019. http://github.com/thomasWeise/jsspInstancesAndResults.
42 A GitHub repository with the common benchmark instances for the Job Shop
43 Scheduling Problem as well as results from the literature, both in form of
44 CSV files and R program code to access them.
456. Henry Fisher and Gerald L. Thompson. Probabilistic Learning Combinations of
46 Local Job-Shop Scheduling Rules. Chapter 3.2 of John F. Muth and
47 Gerald L. Thompson, editors, *Industrial Scheduling,* pages 225-251. 1963.
48 Englewood Cliffs, NJ, USA: Prentice-Hall.
497. Joseph Adams, Egon Balas, and Daniel Zawack. The Shifting Bottleneck
50 Procedure for Job Shop Scheduling. *Management Science.* 34(3):391-401.
51 1988. doi: https://doi.org/10.1287/mnsc.34.3.391
528. David Lee Applegate and William John Cook. A Computational Study of the
53 Job-Shop Scheduling Problem. *ORSA Journal on Computing* 3(2):149-156.
54 May 1991. doi: https://doi.org/10.1287/ijoc.3.2.149. The JSSP instances
55 used were generated in Bonn, Germany in 1986.
569. Robert H. Storer, S. David Wu, and Renzo Vaccari. New Search Spaces for
57 Sequencing Problems with Application to Job Shop Scheduling. *Management
58 Science.* 38(10):1495-1509. 1992.
59 doi: https://doi.org/10.1287/mnsc.38.10.1495
6010. Takeshi Yamada and Ryohei Nakano. A Genetic Algorithm Applicable to
61 Large-Scale Job-Shop Instances. In Reinhard Männer and Bernard
62 Manderick, editors, *Proceedings of Parallel Problem Solving from Nature 2
63 (PPSN II),* September 28-30, 1992, Brussels, Belgium, pages 281-290.
64 Amsterdam, The Netherlands: Elsevier.
65 https://www.researchgate.net/publication/220701684
6611. Stephen R. Lawrence. *Resource Constrained Project Scheduling: An
67 Experimental Investigation of Heuristic Scheduling Techniques
68 (Supplement).* 1984. Pittsburgh, PA, USA: Graduate School of Industrial
69 Administration (GSIA), Carnegie-Mellon University.
7012. Ebru Demirkol, Sanjay V. Mehta, and Reha Uzsoy. Benchmarks for Shop
71 Scheduling Problems. *European Journal of Operational Research (EJOR).*
72 109(1):137-141. August 1998.
73 doi: https://doi.org/10.1016/S0377-2217(97)00019-2
7413. Éric D. Taillard. Benchmarks for Basic Scheduling Problems. *European
75 Journal of Operational Research (EJOR).* 64(2):278-285. January 1993.
76 doi: https://doi.org/10.1016/0377-2217(93)90182-M.
77 http://mistic.heig-vd.ch/taillard/articles.dir/Taillard1993EJOR.pdf
7814. André Henning. *Praktische Job-Shop Scheduling-Probleme.* Jena, Thüringen,
79 Germany: Friedrich-Schiller-Universität Jena, Fakultät für Mathematik und
80 Informatik. August 2022. https://www.db-thueringen.de/servlets/MCRFileNo\
81deServlet/dbt_derivate_00001373/Dissertation.pdf
82"""
83from importlib import resources # nosem
84from typing import Final, Iterable, cast
86import numpy as np
87from pycommons.io.path import UTF8
88from pycommons.types import check_int_range, type_error
90import moptipy.utils.nputils as npu
91from moptipy.api.component import Component
92from moptipy.utils.logger import KeyValueLogSection
93from moptipy.utils.nputils import int_range_to_dtype
94from moptipy.utils.strings import sanitize_name
96#: the recommended scope under which instance data should be stored
97SCOPE_INSTANCE: Final[str] = "inst"
98#: The number of machines in the instance.
99MACHINES: Final[str] = "machines"
100#: The number of jobs in the instance.
101JOBS: Final[str] = "jobs"
102#: The lower bound of the makespan of the instance.
103MAKESPAN_LOWER_BOUND: Final[str] = "makespanLowerBound"
104#: The upper bound of the makespan of the instance.
105MAKESPAN_UPPER_BOUND: Final[str] = "makespanUpperBound"
107#: the internal final set of instances
108_INSTANCES: Final[tuple[str, ...]] = \
109 ("abz5", "abz6", "abz7", "abz8", "abz9",
110 "demo",
111 "dmu01", "dmu02", "dmu03", "dmu04", "dmu05", "dmu06", "dmu07",
112 "dmu08", "dmu09", "dmu10", "dmu11", "dmu12", "dmu13", "dmu14",
113 "dmu15", "dmu16", "dmu17", "dmu18", "dmu19", "dmu20", "dmu21",
114 "dmu22", "dmu23", "dmu24", "dmu25", "dmu26", "dmu27", "dmu28",
115 "dmu29", "dmu30", "dmu31", "dmu32", "dmu33", "dmu34", "dmu35",
116 "dmu36", "dmu37", "dmu38", "dmu39", "dmu40", "dmu41", "dmu42",
117 "dmu43", "dmu44", "dmu45", "dmu46", "dmu47", "dmu48", "dmu49",
118 "dmu50", "dmu51", "dmu52", "dmu53", "dmu54", "dmu55", "dmu56",
119 "dmu57", "dmu58", "dmu59", "dmu60", "dmu61", "dmu62", "dmu63",
120 "dmu64", "dmu65", "dmu66", "dmu67", "dmu68", "dmu69", "dmu70",
121 "dmu71", "dmu72", "dmu73", "dmu74", "dmu75", "dmu76", "dmu77",
122 "dmu78", "dmu79", "dmu80",
123 "ft06", "ft10", "ft20",
124 "la01", "la02", "la03", "la04", "la05", "la06", "la07",
125 "la08", "la09", "la10", "la11", "la12", "la13", "la14",
126 "la15", "la16", "la17", "la18", "la19", "la20", "la21",
127 "la22", "la23", "la24", "la25", "la26", "la27", "la28",
128 "la29", "la30", "la31", "la32", "la33", "la34", "la35",
129 "la36", "la37", "la38", "la39", "la40",
130 "orb01", "orb02", "orb03", "orb04", "orb05", "orb06", "orb07",
131 "orb08", "orb09", "orb10",
132 "swv01", "swv02", "swv03", "swv04", "swv05", "swv06", "swv07",
133 "swv08", "swv09", "swv10", "swv11", "swv12", "swv13", "swv14",
134 "swv15", "swv16", "swv17", "swv18", "swv19", "swv20",
135 "ta01", "ta02", "ta03", "ta04", "ta05", "ta06", "ta07",
136 "ta08", "ta09", "ta10", "ta11", "ta12", "ta13", "ta14",
137 "ta15", "ta16", "ta17", "ta18", "ta19", "ta20", "ta21",
138 "ta22", "ta23", "ta24", "ta25", "ta26", "ta27", "ta28",
139 "ta29", "ta30", "ta31", "ta32", "ta33", "ta34", "ta35",
140 "ta36", "ta37", "ta38", "ta39", "ta40", "ta41", "ta42",
141 "ta43", "ta44", "ta45", "ta46", "ta47", "ta48", "ta49",
142 "ta50", "ta51", "ta52", "ta53", "ta54", "ta55", "ta56",
143 "ta57", "ta58", "ta59", "ta60", "ta61", "ta62", "ta63",
144 "ta64", "ta65", "ta66", "ta67", "ta68", "ta69", "ta70",
145 "ta71", "ta72", "ta73", "ta74", "ta75", "ta76", "ta77",
146 "ta78", "ta79", "ta80",
147 "yn1", "yn2", "yn3", "yn4")
150# start lb
151def compute_makespan_lower_bound(machines: int,
152 jobs: int,
153 matrix: np.ndarray) -> int:
154 """
155 Compute the lower bound for the makespan of a JSSP instance data.
157 :param machines: the number of machines
158 :param jobs: the number of jobs
159 :param matrix: the matrix with the instance data
160 :returns: the lower bound for the makespan
161 """
162 # get the lower bound of the makespan with the algorithm by Taillard
163 usedmachines = np.zeros(machines, np.bool_) # -lb
164 jobtimes = np.zeros(jobs, npu.DEFAULT_INT) # get array for job times
165 machinetimes = np.zeros(machines, npu.DEFAULT_INT) # machine times array
166 machine_start_idle = npu.np_ints_max(machines, npu.DEFAULT_INT)
167 machine_end_idle = npu.np_ints_max(machines, npu.DEFAULT_INT)
169 for jobidx in range(jobs): # iterate over all jobs
170 usedmachines.fill(False) # no machine has been used # -lb
171 jobtime: int = 0 # the job time sum
172 for i in range(machines): # iterate over all operations
173 machine, time = matrix[jobidx, i] # get operation data
174 time = int(time)
175 if usedmachines[i]: # machine already used??? -> error # -lb
176 raise ValueError( # -lb
177 f"Machine {machine} occurs more than once.") # -lb
178 usedmachines[i] = True # mark machine as used # -lb
179 if time < 0: # time can _never_ be negative -> error # -lb
180 raise ValueError(f"Invalid time {str(time)!r}'.") # -lb
181 machinetimes[machine] += time # add up operation times
182 machine_start_idle[machine] = min( # update with...
183 machine_start_idle[machine], jobtime) # ...job time
184 jobtime += time # update job time by adding operation time
186 jobtimes[jobidx] = jobtime # store job time
187 jobremaining = jobtime # iterate backwards to get end idle times
188 for i in range(machines - 1, -1, -1): # second iteration round
189 machine, time = matrix[jobidx, i] # get machine for operation
190 time = int(time)
191 machine_end_idle[machine] = min( # update by computing...
192 machine_end_idle[machine], # the time that the job...
193 int(jobtime) - int(jobremaining)) # needs _after_ operation
194 jobremaining -= time # and update the remaining job time
196 if not all(usedmachines): # all machines have been used? # -lb
197 raise ValueError("Some machines not used in a job.") # -lb
199 # get the maximum of the per-machine sums of the idle and work times
200 machines_bound = int(max(map(int, machine_start_idle + machine_end_idle
201 + machinetimes)))
202 if machines_bound <= 0: # -lb
203 raise ValueError("Computed machine bound cannot be <= , " # -lb
204 f"but is {machines_bound}.") # -lb
205 # get the longest time any job needs in total
206 jobs_bound = int(max(map(int, jobtimes)))
207 if jobs_bound <= 0: # -lb
208 raise ValueError( # -lb
209 f"Computed jobs bound cannot be <= , but is {jobs_bound}.") # -lb
211 return int(max(machines_bound, jobs_bound)) # return bigger one
212# end lb
215# start book
216class Instance(Component, np.ndarray):
217 """
218 An instance of the Job Shop Scheduling Problem.
220 Besides the metadata, this object is a three-dimensional np.ndarray
221 where the columns stand for jobs and the rows represent the
222 operations of the jobs. Each row*column contains two values (third
223 dimension), namely the machine where the operation goes and the time
224 it will consume at that machine: `I[job, operation, 0] = machine`,
225 `I[job, operation, 1] = time` that the job spents on machine.
226 """
228 #: the name of the instance
229 name: str
230 #: the number of jobs == self.shape[0]
231 jobs: int
232 #: the number of machines == self.shape[1]
233 machines: int
234 # ... some more properties and methods ...
235 # end book
236 #: the lower bound of the makespan of this JSSP instance
237 makespan_lower_bound: int
238 #: the upper bound of the makespan of this JSSP instance
239 makespan_upper_bound: int
241 def __new__(cls, name: str, machines: int, jobs: int,
242 matrix: np.ndarray,
243 makespan_lower_bound: int | None = None) -> "Instance":
244 """
245 Create an instance of the Job Shop Scheduling Problem.
247 :param cls: the class
248 :param name: the name of the instance
249 :param machines: the number of machines
250 :param jobs: the number of jobs
251 :param matrix: the matrix with the data (will be copied)
252 :param makespan_lower_bound: the lower bound of the makespan, which
253 may be the known global optimum if the instance has been solved
254 to optimality or any other approximation. If `None` is provided,
255 a lower bound will be computed.
256 """
257 use_name: Final[str] = sanitize_name(name)
258 if name != use_name:
259 raise ValueError(f"Name {name!r} is not a valid name.")
261 check_int_range(machines, "machines", 1, 1_000_000)
262 check_int_range(jobs, "jobs", 1, 1_000_000)
263 if not isinstance(matrix, np.ndarray):
264 raise type_error(matrix, "matrix", np.ndarray)
266 use_shape: tuple[int, int, int] = (jobs, machines, 2)
267 if matrix.shape[0] != jobs:
268 raise ValueError(
269 f"Invalid shape {str(matrix.shape)!r} of matrix: must have "
270 f"jobs={jobs} rows, but has {matrix.shape[0]} in "
271 f"instance {name!r}.")
272 if len(matrix.shape) == 3:
273 if matrix.shape[1] != machines:
274 raise ValueError(
275 f"Invalid shape {str(matrix.shape)!r} of matrix: "
276 f"must have 2*machines={machines} columns, but has "
277 f"{matrix.shape[1]} in instance {name!r}.")
278 if matrix.shape[2] != 2:
279 raise ValueError(
280 f"Invalid shape {str(matrix.shape)!r} of matrix: must "
281 f"have 2 cells per row/column tuple, but has "
282 f"{matrix.shape[2]} in instance {name!r}.")
283 elif len(matrix.shape) == 2:
284 if matrix.shape[1] != 2 * machines:
285 raise ValueError(
286 f"Invalid shape {str(matrix.shape)!r} of matrix: must "
287 f"have 2*machines={2 * machines} columns, but has "
288 f"{matrix.shape[1]} in instance {name!r}.")
289 matrix = matrix.reshape(use_shape)
290 else:
291 raise ValueError(
292 "JSSP instance data matrix must have two or three"
293 f"dimensions, but has {len(matrix.shape)} in instance "
294 f"{name!r}.")
295 if matrix.shape != use_shape:
296 raise ValueError(
297 f"matrix.shape is {matrix.shape}, not {use_shape}?")
298 if not npu.is_np_int(matrix.dtype):
299 raise ValueError(
300 "Matrix must have an integer type, but is of type "
301 f"{str(matrix.dtype)!r} in instance {name!r}.")
302 # ... some computations ...
303 ms_lower_bound = compute_makespan_lower_bound(machines, jobs, matrix)
304 ms_upper_bound = int(sum(map(int, matrix[:, :, 1].flatten())))
305 if ms_upper_bound < ms_lower_bound:
306 raise ValueError(
307 f"Computed makespan upper bound {ms_upper_bound} must not "
308 f"be less than computed lower bound {ms_lower_bound}.")
309 if makespan_lower_bound is None:
310 makespan_lower_bound = ms_lower_bound
311 else:
312 check_int_range(
313 makespan_lower_bound, "makespan lower bound",
314 max(0, ms_lower_bound), ms_upper_bound)
315 maxmat: Final[int] = int(matrix.max())
316 obj: Final[Instance] = super().__new__(
317 Instance, use_shape, int_range_to_dtype(
318 min_value=0, max_value=max(ms_upper_bound, maxmat)))
319 np.copyto(obj, matrix, casting="safe")
320 #: the name of the instance
321 obj.name = use_name
322 #: the number of jobs == self.shape[0]
323 obj.jobs = jobs
324 #: the number of machines == self.shape[1]
325 obj.machines = machines
326 #: the lower bound of the makespan of this JSSP instance
327 obj.makespan_lower_bound = makespan_lower_bound
328 #: the upper bound of the makespan of this JSSP instance
329 obj.makespan_upper_bound = ms_upper_bound
330 return obj
332 def __str__(self) -> str:
333 """
334 Get the name of this JSSP instance.
336 :return: the name
337 """
338 return self.name
340 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
341 """
342 Log the parameters describing this JSSP instance to the logger.
344 :param logger: the logger for the parameters
346 >>> from moptipy.utils.logger import InMemoryLogger
347 >>> with InMemoryLogger() as l:
348 ... with l.key_values("I") as kv:
349 ... Instance.from_resource("abz8").log_parameters_to(kv)
350 ... print(repr('@'.join(l.get_log())))
351 'BEGIN_I@name: abz8@class: moptipy.examples.jssp.instance.\
352Instance@machines: 15@jobs: 20@makespanLowerBound: 648\
353@makespanUpperBound: 7586@dtype: h@END_I'
354 """
355 super().log_parameters_to(logger)
356 logger.key_value(MACHINES, self.machines)
357 logger.key_value(JOBS, self.jobs)
358 logger.key_value(MAKESPAN_LOWER_BOUND, self.makespan_lower_bound)
359 logger.key_value(MAKESPAN_UPPER_BOUND, self.makespan_upper_bound)
360 logger.key_value(npu.KEY_NUMPY_TYPE, self.dtype.char)
362 @staticmethod
363 def from_text(name: str, rows: list[str]) -> "Instance":
364 """
365 Convert a name and a set of rows of text to an JSSP instance.
367 :param name: the name of the instance
368 :param rows: the rows
369 :return: the JSSP Instance
370 """
371 if not isinstance(rows, list):
372 raise type_error(rows, "rows", list)
373 if len(rows) < 3:
374 raise ValueError(
375 f"Must have at least 3 rows, but found {rows}.")
376 description = rows[0]
377 if not isinstance(description, str):
378 raise type_error(description, "first element of rows", str)
379 jobs_machines_txt = rows[1]
381 matrix = np.asanyarray([np.fromstring(row, dtype=npu.DEFAULT_INT,
382 sep=" ")
383 for row in rows[2:]])
384 if not np.issubdtype(matrix.dtype, np.integer):
385 raise ValueError("Error when converting array to matrix, "
386 f"got type {str(matrix.dtype)!r}.")
388 min_value = int(matrix.min())
389 if min_value < 0:
390 raise ValueError("JSSP matrix can only contain values >= 0, "
391 f"but found {min_value}.")
393 max_value = int(matrix.max())
394 if max_value <= min_value:
395 raise ValueError(
396 "JSSP matrix must contain value larger than minimum "
397 f"{min_value}, but maximum is {max_value}.")
399 dtype = int_range_to_dtype(min_value=min_value, max_value=max_value,
400 force_unsigned=True)
401 if dtype != matrix.dtype:
402 matrix = matrix.astype(dtype)
404 jobs_machines = jobs_machines_txt.strip().split(" ")
405 jobs = int(jobs_machines[0])
406 machines = int(jobs_machines[len(jobs_machines) - 1])
408 makespan_lower_bound = None
409 i = description.find("lower bound:")
410 if i >= 0:
411 i += 12
412 j = description.find(";", i)
413 if j < i:
414 j = len(description)
415 makespan_lower_bound = int(description[i:j].strip())
417 return Instance(name=name,
418 jobs=jobs,
419 machines=machines,
420 matrix=matrix,
421 makespan_lower_bound=makespan_lower_bound)
423 @staticmethod
424 def from_stream(name: str, stream: Iterable[str]) -> "Instance":
425 """
426 Load an instance from a text stream.
428 :param name: the name of the instance to be loaded
429 :param stream: the text stream
430 :return: the instance
431 """
432 state = 0
433 rows: list[str] | None = None
434 for linestr in stream:
435 line = str.strip(linestr)
436 if len(line) <= 0:
437 continue
438 if state == 0:
439 if line.startswith("+++"):
440 state = 1
441 continue
442 if state == 1:
443 if line.startswith("instance "):
444 inst = line[9:].strip()
445 state = 2 if inst == name else 4
446 continue
447 if state == 2:
448 if line.startswith("+++"):
449 state = 3
450 rows = []
451 continue
452 raise ValueError(f"Unexpected string {line!r}.")
453 if state == 3:
454 if line.startswith("+++"):
455 return Instance.from_text(name=name, rows=rows)
456 rows.append(line)
457 continue
458 if state == 4:
459 if line.startswith("+++"):
460 state = 5
461 continue
462 raise ValueError(f"Unexpected string {line!r}.")
463 if (state == 5) and (line.startswith("+++")):
464 state = 1
466 raise ValueError(f"Could not find instance {name!r}.")
468 @staticmethod
469 def from_resource(name: str) -> "Instance":
470 """
471 Load the JSSP instances `name` provided as part of moptipy.
473 :param name: the instance name
474 :return: the instance
476 >>> jssp = Instance.from_resource("demo")
477 >>> print(jssp.jobs)
478 4
479 >>> print(jssp.machines)
480 5
481 >>> print(jssp)
482 demo
483 """
484 container: Final = Instance.from_resource
485 inst_attr: Final[str] = f"__inst_{name}"
486 if hasattr(container, inst_attr):
487 return cast("Instance", getattr(container, inst_attr))
488 with resources.files(str(__package__)).joinpath(
489 "demo.txt" if (name == "demo")
490 else "instances.txt").open("r", encoding=UTF8) as stream:
491 inst: Final[Instance] = Instance.from_stream(
492 name=name, stream=stream)
493 setattr(container, inst_attr, inst)
494 return inst
496 @staticmethod
497 def list_resources() -> tuple[str, ...]:
498 """
499 Get a tuple with all JSSP instances provided in the moptipy resources.
501 :return: a tuple with all instance names that are valid parameters
502 to :meth:`Instance.from_resource`
504 >>> print(Instance.list_resources()[0:3])
505 ('abz5', 'abz6', 'abz7')
506 """
507 return _INSTANCES
510def check_instance(inst: Instance) -> Instance:
511 """
512 Check whether the contents of a JSSP instance are OK.
514 This method thoroughly checks the contents of an instance and the
515 types of all of its members. If your instances passes this method
516 without any error, it is a valid JSSP instance that can be used for
517 experiments. All instances in our benchmark set listed above will
518 pass this test.
520 :param inst: the instance
521 :returns: the instance, if its contents are OK
522 """
523 if not isinstance(inst, Instance):
524 raise type_error(inst, "instance", Instance)
525 if not isinstance(inst, np.ndarray):
526 raise type_error(inst, "instance", np.ndarray)
527 check_int_range(inst.machines, "inst.machines", 1, 1_000_000)
528 check_int_range(inst.jobs, "inst.jobs", 1, 1_000_000)
529 if not isinstance(inst.name, str):
530 raise type_error(inst.name, "inst.name", str)
531 if (len(inst.name) <= 0) \
532 or (inst.name != sanitize_name(inst.name)):
533 raise ValueError(f"invalid instance name {inst.name!r}")
534 check_int_range(
535 inst.makespan_lower_bound, "inst.makespan_lower_bound",
536 1, 1_000_000_000_000)
537 check_int_range(
538 inst.makespan_upper_bound, "inst.makespan_upper_bound",
539 inst.makespan_lower_bound, 1_000_000_000_000)
540 if len(inst.shape) != 3:
541 raise ValueError(f"inst must be 3d-array, but has shape {inst.shape}"
542 f" for instance {inst.name}.")
543 if inst.shape[0] != inst.jobs:
544 raise ValueError(
545 f"inst.shape[0] must be inst.jobs={inst.jobs}, "
546 f"but inst has shape {inst.shape} for instance {inst.name}.")
547 if inst.shape[1] != inst.machines:
548 raise ValueError(
549 f"inst.machines[1] must be inst.machines={inst.machines}, "
550 f"but inst has shape {inst.shape} for instance {inst.name}.")
551 if inst.shape[2] != 2:
552 raise ValueError(
553 f"inst.machines[2] must be 2, but inst has shape {inst.shape}"
554 f" for instance {inst.name}.")
556 for i in range(inst.jobs):
557 for j in range(inst.machines):
558 machine = inst[i, j, 0]
559 if not (0 <= machine < inst.machines):
560 raise ValueError(
561 f"encountered machine {machine} for job {i} in "
562 f"operation {j}, but there are only "
563 f"{inst.machines} machines for instance {inst.name}.")
564 mslb = compute_makespan_lower_bound(
565 machines=inst.machines, jobs=inst.jobs, matrix=inst)
566 if mslb > inst.makespan_lower_bound:
567 raise ValueError(f"makespan lower bound computed as {mslb},"
568 f"but set to {inst.makespan_upper_bound},"
569 "which is not lower for instance {inst.name}.")
570 msub = sum(inst[:, :, 1].flatten())
571 if msub != inst.makespan_upper_bound:
572 raise ValueError(f"makespan upper bound computed as {msub}, "
573 f"but set to {inst.makespan_upper_bound}"
574 f" for instance {inst.name}.")
575 tub = max(sum(inst[i, :, 1]) for i in range(inst.jobs))
576 if inst.makespan_lower_bound < tub:
577 raise ValueError(f"makespan lower bound {inst.makespan_lower_bound} "
578 f"less then longest job duration {tub}"
579 f" for instance {inst.name}.")
580 return inst