Coverage for moptipy / examples / jssp / instance.py: 83%
227 statements
« prev ^ index » next coverage.py v7.13.2, created at 2026-01-28 04:20 +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, # noqa: PYI034
242 matrix: np.ndarray, # noqa: PYI034
243 makespan_lower_bound: int | None = None) -> \
244 "Instance": # noqa: PYI034
245 """
246 Create an instance of the Job Shop Scheduling Problem.
248 :param cls: the class
249 :param name: the name of the instance
250 :param machines: the number of machines
251 :param jobs: the number of jobs
252 :param matrix: the matrix with the data (will be copied)
253 :param makespan_lower_bound: the lower bound of the makespan, which
254 may be the known global optimum if the instance has been solved
255 to optimality or any other approximation. If `None` is provided,
256 a lower bound will be computed.
257 """
258 use_name: Final[str] = sanitize_name(name)
259 if name != use_name:
260 raise ValueError(f"Name {name!r} is not a valid name.")
262 check_int_range(machines, "machines", 1, 1_000_000)
263 check_int_range(jobs, "jobs", 1, 1_000_000)
264 if not isinstance(matrix, np.ndarray):
265 raise type_error(matrix, "matrix", np.ndarray)
267 use_shape: tuple[int, int, int] = (jobs, machines, 2)
268 if matrix.shape[0] != jobs:
269 raise ValueError(
270 f"Invalid shape {str(matrix.shape)!r} of matrix: must have "
271 f"jobs={jobs} rows, but has {matrix.shape[0]} in "
272 f"instance {name!r}.")
273 if len(matrix.shape) == 3:
274 if matrix.shape[1] != machines:
275 raise ValueError(
276 f"Invalid shape {str(matrix.shape)!r} of matrix: "
277 f"must have 2*machines={machines} columns, but has "
278 f"{matrix.shape[1]} in instance {name!r}.")
279 if matrix.shape[2] != 2:
280 raise ValueError(
281 f"Invalid shape {str(matrix.shape)!r} of matrix: must "
282 f"have 2 cells per row/column tuple, but has "
283 f"{matrix.shape[2]} in instance {name!r}.")
284 elif len(matrix.shape) == 2:
285 if matrix.shape[1] != 2 * machines:
286 raise ValueError(
287 f"Invalid shape {str(matrix.shape)!r} of matrix: must "
288 f"have 2*machines={2 * machines} columns, but has "
289 f"{matrix.shape[1]} in instance {name!r}.")
290 matrix = matrix.reshape(use_shape)
291 else:
292 raise ValueError(
293 "JSSP instance data matrix must have two or three"
294 f"dimensions, but has {len(matrix.shape)} in instance "
295 f"{name!r}.")
296 if matrix.shape != use_shape:
297 raise ValueError(
298 f"matrix.shape is {matrix.shape}, not {use_shape}?")
299 if not npu.is_np_int(matrix.dtype):
300 raise ValueError(
301 "Matrix must have an integer type, but is of type "
302 f"{str(matrix.dtype)!r} in instance {name!r}.")
303 # ... some computations ...
304 ms_lower_bound = compute_makespan_lower_bound(machines, jobs, matrix)
305 ms_upper_bound = int(sum(map(int, matrix[:, :, 1].flatten())))
306 if ms_upper_bound < ms_lower_bound:
307 raise ValueError(
308 f"Computed makespan upper bound {ms_upper_bound} must not "
309 f"be less than computed lower bound {ms_lower_bound}.")
310 if makespan_lower_bound is None:
311 makespan_lower_bound = ms_lower_bound
312 else:
313 check_int_range(
314 makespan_lower_bound, "makespan lower bound",
315 max(0, ms_lower_bound), ms_upper_bound)
316 maxmat: Final[int] = int(matrix.max())
317 obj: Final[Instance] = super().__new__(
318 Instance, use_shape, int_range_to_dtype(
319 min_value=0, max_value=max(ms_upper_bound, maxmat)))
320 np.copyto(obj, matrix, casting="safe")
321 #: the name of the instance
322 obj.name = use_name
323 #: the number of jobs == self.shape[0]
324 obj.jobs = jobs
325 #: the number of machines == self.shape[1]
326 obj.machines = machines
327 #: the lower bound of the makespan of this JSSP instance
328 obj.makespan_lower_bound = makespan_lower_bound
329 #: the upper bound of the makespan of this JSSP instance
330 obj.makespan_upper_bound = ms_upper_bound
331 return obj
333 def __str__(self) -> str:
334 """
335 Get the name of this JSSP instance.
337 :return: the name
338 """
339 return self.name
341 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
342 """
343 Log the parameters describing this JSSP instance to the logger.
345 :param logger: the logger for the parameters
347 >>> from moptipy.utils.logger import InMemoryLogger
348 >>> with InMemoryLogger() as l:
349 ... with l.key_values("I") as kv:
350 ... Instance.from_resource("abz8").log_parameters_to(kv)
351 ... print(repr('@'.join(l.get_log())))
352 'BEGIN_I@name: abz8@class: moptipy.examples.jssp.instance.\
353Instance@machines: 15@jobs: 20@makespanLowerBound: 648\
354@makespanUpperBound: 7586@dtype: h@END_I'
355 """
356 super().log_parameters_to(logger)
357 logger.key_value(MACHINES, self.machines)
358 logger.key_value(JOBS, self.jobs)
359 logger.key_value(MAKESPAN_LOWER_BOUND, self.makespan_lower_bound)
360 logger.key_value(MAKESPAN_UPPER_BOUND, self.makespan_upper_bound)
361 logger.key_value(npu.KEY_NUMPY_TYPE, self.dtype.char)
363 @staticmethod
364 def from_text(name: str, rows: list[str]) -> "Instance":
365 """
366 Convert a name and a set of rows of text to an JSSP instance.
368 :param name: the name of the instance
369 :param rows: the rows
370 :return: the JSSP Instance
371 """
372 if not isinstance(rows, list):
373 raise type_error(rows, "rows", list)
374 if len(rows) < 3:
375 raise ValueError(
376 f"Must have at least 3 rows, but found {rows}.")
377 description = rows[0]
378 if not isinstance(description, str):
379 raise type_error(description, "first element of rows", str)
380 jobs_machines_txt = rows[1]
382 matrix = np.asanyarray([np.fromstring(row, dtype=npu.DEFAULT_INT,
383 sep=" ")
384 for row in rows[2:]])
385 if not np.issubdtype(matrix.dtype, np.integer):
386 raise ValueError("Error when converting array to matrix, "
387 f"got type {str(matrix.dtype)!r}.")
389 min_value = int(matrix.min())
390 if min_value < 0:
391 raise ValueError("JSSP matrix can only contain values >= 0, "
392 f"but found {min_value}.")
394 max_value = int(matrix.max())
395 if max_value <= min_value:
396 raise ValueError(
397 "JSSP matrix must contain value larger than minimum "
398 f"{min_value}, but maximum is {max_value}.")
400 dtype = int_range_to_dtype(min_value=min_value, max_value=max_value,
401 force_unsigned=True)
402 if dtype != matrix.dtype:
403 matrix = matrix.astype(dtype)
405 jobs_machines = jobs_machines_txt.strip().split(" ")
406 jobs = int(jobs_machines[0])
407 machines = int(jobs_machines[len(jobs_machines) - 1])
409 makespan_lower_bound = None
410 i = description.find("lower bound:")
411 if i >= 0:
412 i += 12
413 j = description.find(";", i)
414 if j < i:
415 j = len(description)
416 makespan_lower_bound = int(description[i:j].strip())
418 return Instance(name=name,
419 jobs=jobs,
420 machines=machines,
421 matrix=matrix,
422 makespan_lower_bound=makespan_lower_bound)
424 @staticmethod
425 def from_stream(name: str, stream: Iterable[str]) -> "Instance":
426 """
427 Load an instance from a text stream.
429 :param name: the name of the instance to be loaded
430 :param stream: the text stream
431 :return: the instance
432 """
433 state = 0
434 rows: list[str] | None = None
435 for linestr in stream:
436 line = str.strip(linestr)
437 if len(line) <= 0:
438 continue
439 if state == 0:
440 if line.startswith("+++"):
441 state = 1
442 continue
443 if state == 1:
444 if line.startswith("instance "):
445 inst = line[9:].strip()
446 state = 2 if inst == name else 4
447 continue
448 if state == 2:
449 if line.startswith("+++"):
450 state = 3
451 rows = []
452 continue
453 raise ValueError(f"Unexpected string {line!r}.")
454 if state == 3:
455 if line.startswith("+++"):
456 return Instance.from_text(name=name, rows=rows)
457 rows.append(line)
458 continue
459 if state == 4:
460 if line.startswith("+++"):
461 state = 5
462 continue
463 raise ValueError(f"Unexpected string {line!r}.")
464 if (state == 5) and (line.startswith("+++")):
465 state = 1
467 raise ValueError(f"Could not find instance {name!r}.")
469 @staticmethod
470 def from_resource(name: str) -> "Instance":
471 """
472 Load the JSSP instances `name` provided as part of moptipy.
474 :param name: the instance name
475 :return: the instance
477 >>> jssp = Instance.from_resource("demo")
478 >>> print(jssp.jobs)
479 4
480 >>> print(jssp.machines)
481 5
482 >>> print(jssp)
483 demo
484 """
485 container: Final = Instance.from_resource
486 inst_attr: Final[str] = f"__inst_{name}"
487 if hasattr(container, inst_attr):
488 return cast("Instance", getattr(container, inst_attr))
489 with resources.files(str(__package__)).joinpath(
490 "demo.txt" if (name == "demo")
491 else "instances.txt").open("r", encoding=UTF8) as stream:
492 inst: Final[Instance] = Instance.from_stream(
493 name=name, stream=stream)
494 setattr(container, inst_attr, inst)
495 return inst
497 @staticmethod
498 def list_resources() -> tuple[str, ...]:
499 """
500 Get a tuple with all JSSP instances provided in the moptipy resources.
502 :return: a tuple with all instance names that are valid parameters
503 to :meth:`Instance.from_resource`
505 >>> print(Instance.list_resources()[0:3])
506 ('abz5', 'abz6', 'abz7')
507 """
508 return _INSTANCES
511def check_instance(inst: Instance) -> Instance:
512 """
513 Check whether the contents of a JSSP instance are OK.
515 This method thoroughly checks the contents of an instance and the
516 types of all of its members. If your instances passes this method
517 without any error, it is a valid JSSP instance that can be used for
518 experiments. All instances in our benchmark set listed above will
519 pass this test.
521 :param inst: the instance
522 :returns: the instance, if its contents are OK
523 """
524 if not isinstance(inst, Instance):
525 raise type_error(inst, "instance", Instance)
526 if not isinstance(inst, np.ndarray):
527 raise type_error(inst, "instance", np.ndarray)
528 check_int_range(inst.machines, "inst.machines", 1, 1_000_000)
529 check_int_range(inst.jobs, "inst.jobs", 1, 1_000_000)
530 if not isinstance(inst.name, str):
531 raise type_error(inst.name, "inst.name", str)
532 if (len(inst.name) <= 0) \
533 or (inst.name != sanitize_name(inst.name)):
534 raise ValueError(f"invalid instance name {inst.name!r}")
535 check_int_range(
536 inst.makespan_lower_bound, "inst.makespan_lower_bound",
537 1, 1_000_000_000_000)
538 check_int_range(
539 inst.makespan_upper_bound, "inst.makespan_upper_bound",
540 inst.makespan_lower_bound, 1_000_000_000_000)
541 if len(inst.shape) != 3:
542 raise ValueError(f"inst must be 3d-array, but has shape {inst.shape}"
543 f" for instance {inst.name}.")
544 if inst.shape[0] != inst.jobs:
545 raise ValueError(
546 f"inst.shape[0] must be inst.jobs={inst.jobs}, "
547 f"but inst has shape {inst.shape} for instance {inst.name}.")
548 if inst.shape[1] != inst.machines:
549 raise ValueError(
550 f"inst.machines[1] must be inst.machines={inst.machines}, "
551 f"but inst has shape {inst.shape} for instance {inst.name}.")
552 if inst.shape[2] != 2:
553 raise ValueError(
554 f"inst.machines[2] must be 2, but inst has shape {inst.shape}"
555 f" for instance {inst.name}.")
557 for i in range(inst.jobs):
558 for j in range(inst.machines):
559 machine = inst[i, j, 0]
560 if not (0 <= machine < inst.machines):
561 raise ValueError(
562 f"encountered machine {machine} for job {i} in "
563 f"operation {j}, but there are only "
564 f"{inst.machines} machines for instance {inst.name}.")
565 mslb = compute_makespan_lower_bound(
566 machines=inst.machines, jobs=inst.jobs, matrix=inst)
567 if mslb > inst.makespan_lower_bound:
568 raise ValueError(f"makespan lower bound computed as {mslb},"
569 f"but set to {inst.makespan_upper_bound},"
570 "which is not lower for instance {inst.name}.")
571 msub = sum(inst[:, :, 1].flatten())
572 if msub != inst.makespan_upper_bound:
573 raise ValueError(f"makespan upper bound computed as {msub}, "
574 f"but set to {inst.makespan_upper_bound}"
575 f" for instance {inst.name}.")
576 tub = max(sum(inst[i, :, 1]) for i in range(inst.jobs))
577 if inst.makespan_lower_bound < tub:
578 raise ValueError(f"makespan lower bound {inst.makespan_lower_bound} "
579 f"less then longest job duration {tub}"
580 f" for instance {inst.name}.")
581 return inst