Coverage for moptipyapps / prodsched / instance.py: 79%
661 statements
« prev ^ index » next coverage.py v7.13.0, created at 2025-12-11 04:40 +0000
1"""
2A production scheduling instance.
4Production instances have names :attr:`Instance.name`.
6Notice that production times are used in a cycling fashion.
7The time when a certain product is finished can be computed via
8:func:`~compute_finish_time` in an efficient way.
10>>> name = "my_instance"
12The number of products be 3.
14>>> n_products = 3
16The number of customers be 5.
18>>> n_customers = 5
20The number of stations be 4.
22>>> n_stations = 4
24There will be 6 customer demands.
26>>> n_demands = 6
28The end of the warmup period.
30>>> time_end_warmup = 10
32The end of the measurement period.
34>>> time_end_measure = 10000
36Each product may take a different route through different stations.
38>>> route_p0 = [0, 3, 2]
39>>> route_p1 = [0, 2, 1, 3]
40>>> route_p2 = [1, 2, 3]
41>>> routes = [route_p0, route_p1, route_p2]
43Each demand is a tuple of demand_id, customer_id, product_id, amount,
44release time, and deadline.
46>>> d0 = [0, 0, 1, 20, 1240, 3000]
47>>> d1 = [1, 1, 0, 10, 2300, 4000]
48>>> d2 = [2, 2, 2, 7, 8300, 11000]
49>>> d3 = [3, 3, 1, 12, 7300, 9000]
50>>> d4 = [4, 4, 2, 23, 5410, 16720]
51>>> d5 = [5, 3, 0, 19, 4234, 27080]
52>>> demands = [d0, d1, d2, d3, d4, d5]
54There is a fixed amount of each product in the warehouse at time step 0.
56>>> warehous_at_t0 = [10, 0, 6]
58Each station requires a certain working time for each unit of each product.
59This production time may vary over time.
60For example, maybe station 0 needs 10 time units for 1 unit of product 0 from
61time step 0 to time step 19, then 11 time units from time step 20 to 39, then
628 time units from time step 40 to 59.
63These times are cyclic, meaning that at time step 60 to 79, it will again need
6410 time units, and so on.
65Of course, production times are only specified for stations that a product is
66actually routed through.
68>>> m0_p0 = [10.0, 20.0, 11.0, 40.0, 8.0, 60.0]
69>>> m0_p1 = [12.0, 20.0, 7.0, 40.0, 11.0, 70.0]
70>>> m0_p2 = []
71>>> m1_p0 = []
72>>> m1_p1 = [20.0, 50.0, 30.0, 120.0, 7.0, 200.0]
73>>> m1_p2 = [21.0, 50.0, 29.0, 130.0, 8.0, 190.0]
74>>> m2_p0 = [ 8.0, 20.0, 9.0, 60.0]
75>>> m2_p1 = [10.0, 90.0]
76>>> m2_p2 = [12.0, 70.0, 30.0, 120.0]
77>>> m3_p0 = [70.0, 200.0, 3.0, 220.0]
78>>> m3_p1 = [60.0, 220.0, 5.0, 260.0]
79>>> m3_p2 = [30.0, 210.0, 10.0, 300.0]
80>>> station_product_unit_times = [[m0_p0, m0_p1, m0_p2],
81... [m1_p0, m1_p1, m1_p2],
82... [m2_p0, m2_p1, m2_p2],
83... [m3_p0, m3_p1, m3_p2]]
85We can (but do not need to) provide additional information as key-value pairs.
87>>> infos = {"source": "manually created",
88... "creation_date": "2025-11-09"}
90From all of this data, we can create the instance.
92>>> instance = Instance(name, n_products, n_customers, n_stations, n_demands,
93... time_end_warmup, time_end_measure,
94... routes, demands, warehous_at_t0,
95... station_product_unit_times, infos)
96>>> instance.name
97'my_instance'
99>>> instance.n_customers
1005
102>>> instance.n_stations
1034
105>>> instance.n_demands
1066
108>>> instance.n_products
1093
111>>> instance.routes
112((0, 3, 2), (0, 2, 1, 3), (1, 2, 3))
114>>> instance.time_end_warmup
11510.0
117>>> instance.time_end_measure
11810000.0
120>>> instance.demands
121(Demand(arrival=1240.0, deadline=3000.0, demand_id=0, customer_id=0,\
122 product_id=1, amount=20, measure=True),\
123 Demand(arrival=2300.0, deadline=4000.0, demand_id=1, customer_id=1,\
124 product_id=0, amount=10, measure=True),\
125 Demand(arrival=4234.0, deadline=27080.0, demand_id=5, customer_id=3,\
126 product_id=0, amount=19, measure=True),\
127 Demand(arrival=5410.0, deadline=16720.0, demand_id=4, customer_id=4,\
128 product_id=2, amount=23, measure=True),\
129 Demand(arrival=7300.0, deadline=9000.0, demand_id=3, customer_id=3,\
130 product_id=1, amount=12, measure=True),\
131 Demand(arrival=8300.0, deadline=11000.0, demand_id=2, customer_id=2,\
132 product_id=2, amount=7, measure=True))
134>>> instance.warehous_at_t0
135(10, 0, 6)
137>>> instance.station_product_unit_times
138((array([10., 20., 11., 40., 8., 60.]), \
139array([12., 20., 7., 40., 11., 70.]), array([], dtype=float64)), (\
140array([], dtype=float64), array([ 20., 50., 30., 120., 7., 200.]), \
141array([ 21., 50., 29., 130., 8., 190.])), (array([ 8., 20., 9., 60.]), \
142array([10., 90.]), array([ 12., 70., 30., 120.])), (\
143array([ 70., 200., 3., 220.]), array([ 60., 220., 5., 260.]), array(\
144[ 30., 210., 10., 300.])))
146>>> instance.n_measurable_demands
1476
149>>> instance.n_measurable_demands_per_product
150(2, 2, 2)
152>>> dict(instance.infos)
153{'source': 'manually created', 'creation_date': '2025-11-09'}
155We can serialize instances to a stream of strings and also load them back
156from a stream of strings.
157Here, we store `instance` to a stream.
158We then load the independent instance `i2` from that stream.
160>>> i2 = from_stream(to_stream(instance))
161>>> i2 is instance
162False
163>>> i2 == instance
164True
166You can see that the loaded instance has the same data as the stored one.
168>>> i2.name == instance.name
169True
170>>> i2.n_customers == instance.n_customers
171True
172>>> i2.n_stations == instance.n_stations
173True
174>>> i2.n_demands == instance.n_demands
175True
176>>> i2.n_products == instance.n_products
177True
178>>> i2.routes == instance.routes
179True
180>>> i2.demands == instance.demands
181True
182>>> i2.time_end_warmup == instance.time_end_warmup
183True
184>>> i2.time_end_measure == instance.time_end_measure
185True
186>>> i2.warehous_at_t0 == instance.warehous_at_t0
187True
188>>> eq: bool = True
189>>> for i in range(i2.n_stations):
190... ma1 = i2.station_product_unit_times[i]
191... ma2 = instance.station_product_unit_times[i]
192... for j in range(i2.n_products):
193... pr1 = ma1[j]
194... pr2 = ma2[j]
195... if not np.array_equal(pr1, pr2):
196... eq = False
197>>> eq
198True
200True
201>>> i2.infos == instance.infos
202True
203"""
205from dataclasses import dataclass
206from itertools import batched
207from math import ceil, isfinite
208from string import ascii_letters, digits
209from typing import (
210 Callable,
211 Final,
212 Generator,
213 Iterable,
214 Iterator,
215 Mapping,
216 cast,
217)
219import numba # type: ignore
220import numpy as np
221from moptipy.api.component import Component
222from moptipy.utils.logger import (
223 COMMENT_START,
224 KEY_VALUE_SEPARATOR,
225)
226from moptipy.utils.strings import sanitize_name
227from pycommons.ds.cache import repr_cache
228from pycommons.ds.immutable_map import immutable_mapping
229from pycommons.io.csv import CSV_SEPARATOR
230from pycommons.io.path import Path, directory_path, write_lines
231from pycommons.math.int_math import try_int
232from pycommons.strings.string_conv import bool_to_str, float_to_str, num_to_str
233from pycommons.types import check_int_range, check_to_int_range, type_error
235#: The maximum for the number of stations, products, or customers.
236MAX_ID: Final[int] = 1_000_000_000
238#: No value bigger than this is permitted in any tuple anywhere.
239MAX_VALUE: Final[int] = 2_147_483_647
241#: the index of the demand ID
242DEMAND_ID: Final[int] = 0
243#: the index of the customer ID
244DEMAND_CUSTOMER: Final[int] = 1
245#: the index of the product ID
246DEMAND_PRODUCT: Final[int] = 2
247#: the index of the demanded amount
248DEMAND_AMOUNT: Final[int] = 3
249#: the index of the demand release time
250DEMAND_ARRIVAL: Final[int] = 4
251#: the index of the demand deadline
252DEMAND_DEADLINE: Final[int] = 5
255@dataclass(order=True, frozen=True)
256class Demand(Iterable[int | float]):
257 """
258 The record for demands.
260 >>> Demand(arrival=0.6, deadline=0.8, demand_id=1,
261 ... customer_id=2, product_id=6, amount=12, measure=True)
262 Demand(arrival=0.6, deadline=0.8, demand_id=1, customer_id=2,\
263 product_id=6, amount=12, measure=True)
264 >>> Demand(arrival=16, deadline=28, demand_id=1,
265 ... customer_id=2, product_id=6, amount=12, measure=False)
266 Demand(arrival=16.0, deadline=28.0, demand_id=1, customer_id=2,\
267 product_id=6, amount=12, measure=False)
268 """
270 #: the arrival time, i.e., when the demand enters the system
271 arrival: float
272 #: the deadline, i.e., when the customer expects the result
273 deadline: float
274 #: the ID of the demand
275 demand_id: int
276 #: the customer ID
277 customer_id: int
278 #: the ID of the product
279 product_id: int
280 #: the amount
281 amount: int
282 #: is this demand measurement relevant?
283 measure: bool
285 def __init__(self, arrival: int | float,
286 deadline: int | float, demand_id: int,
287 customer_id: int, product_id: int, amount: int,
288 measure: bool) -> None:
289 """
290 Initialize the record.
292 :param arrival: the arrival time
293 :param deadline: the deadline
294 :param demand_id: the demand id
295 :param customer_id: the customer id
296 :param product_id: the product id
297 :param amount: the amount
298 :param measure: is this demand relevant for measurement?
299 """
300 if isinstance(arrival, int):
301 t: float = float(arrival)
302 if t != arrival:
303 raise ValueError(f"invalid arrival time {arrival}")
304 arrival = t
305 if not isinstance(arrival, float):
306 raise type_error(arrival, "arrival", float)
307 if not (isfinite(arrival) and (
308 0 < arrival < MAX_VALUE)):
309 raise ValueError(f"invalid arrival={arrival}")
311 if isinstance(deadline, int):
312 t = float(deadline)
313 if t != deadline:
314 raise ValueError(f"invalid deadline time {deadline}")
315 deadline = t
316 if not isinstance(deadline, float):
317 raise type_error(deadline, "deadline", float)
318 if not (isfinite(deadline) and (0 < deadline < MAX_VALUE)):
319 raise ValueError(f"invalid deadline={deadline}")
321 if deadline < arrival:
322 raise ValueError(
323 f"arrival={arrival} and deadline={deadline}")
324 object.__setattr__(self, "arrival", arrival)
325 object.__setattr__(self, "deadline", deadline)
326 object.__setattr__(self, "demand_id", check_int_range(
327 demand_id, "demand_id", 0, MAX_ID))
328 object.__setattr__(self, "customer_id", check_int_range(
329 customer_id, "customer_id", 0, MAX_ID))
330 object.__setattr__(self, "product_id", check_int_range(
331 product_id, "product_id", 0, MAX_ID))
332 object.__setattr__(self, "amount", check_int_range(
333 amount, "amount", 1, MAX_ID))
334 if not isinstance(measure, bool):
335 raise type_error(measure, "measure", bool)
336 object.__setattr__(self, "measure", measure)
338 def __str__(self) -> str:
339 """
340 Get a string representation of the demand.
342 :return: the string representation
344 >>> str(Demand(arrival=16, deadline=28.0, demand_id=1,
345 ... customer_id=2, product_id=6, amount=12, measure=False))
346 'd(id: 1, p: 6, c: 2, am: 12, ar: 16, dl: 28, me: F)'
347 """
348 fts: Final[Callable] = float_to_str
349 return (f"d(id: {self.demand_id}, p: {self.product_id}, "
350 f"c: {self.customer_id}, am: {self.amount}, "
351 f"ar: {fts(self.arrival)}, dl: {fts(self.deadline)}, "
352 f"me: {bool_to_str(self.measure)})")
354 def __getitem__(self, item: int) -> int | float:
355 """
356 Access an element of this demand via an index.
358 :param item: the index
359 :return: the demand value at that index
361 >>> d = Demand(arrival=16, deadline=28, demand_id=1,
362 ... customer_id=2, product_id=6, amount=12, measure=True)
363 >>> d[0]
364 1
365 >>> d[1]
366 2
367 >>> d[2]
368 6
369 >>> d[3]
370 12
371 >>> d[4]
372 16
373 >>> d[5]
374 28
375 """
376 if item == DEMAND_ID:
377 return self.demand_id
378 if item == DEMAND_CUSTOMER:
379 return self.customer_id
380 if item == DEMAND_PRODUCT:
381 return self.product_id
382 if item == DEMAND_AMOUNT:
383 return self.amount
384 if item == DEMAND_ARRIVAL:
385 return try_int(self.arrival)
386 if item == DEMAND_DEADLINE:
387 return try_int(self.deadline)
388 raise IndexError(
389 f"index {item} out of bounds [0,{DEMAND_DEADLINE}].")
391 def __iter__(self) -> Iterator[int | float]:
392 """
393 Iterate over the values in this demand.
395 :return: the demand iterable
397 >>> d = Demand(arrival=16, deadline=28, demand_id=1,
398 ... customer_id=2, product_id=6, amount=12, measure=True)
399 >>> list(d)
400 [1, 2, 6, 12, 16, 28]
401 """
402 yield self.demand_id # DEMAND_ID
403 yield self.customer_id # DEMAND_CUSTOMER
404 yield self.product_id # DEMAND_PRODUCT:
405 yield self.amount # DEMAND_AMOUNT:
406 yield try_int(self.arrival) # DEMAND_ARRIVAL
407 yield try_int(self.deadline) # DEMAND_DEADLINE
409 def __len__(self) -> int:
410 """
411 Get the length of the demand record.
413 :returns `6`: always
415 >>> len(Demand(arrival=16, deadline=28, demand_id=1,
416 ... customer_id=2, product_id=6, amount=12, measure=True))
417 6
418 """
419 return 6
422def __to_tuple(source: Iterable[int | float],
423 cache: Callable, empty_ok: bool = False,
424 type_var: type = int) -> tuple:
425 """
426 Convert an iterable of type integer to a tuple.
428 :param source: the data source
429 :param cache: the cache
430 :param empty_ok: are empty tuples OK?
431 :param type_var: the type variable
432 :return: the tuple
434 >>> ppl = repr_cache()
435 >>> k1 = __to_tuple([1, 2, 3], ppl)
436 >>> print(k1)
437 (1, 2, 3)
439 >>> __to_tuple({2}, ppl)
440 (2,)
442 >>> k2 = __to_tuple([1, 2, 3], ppl)
443 >>> print(k2)
444 (1, 2, 3)
445 >>> k1 is k2
446 True
448 >>> k3 = __to_tuple([3.4, 2.3, 3.1], ppl, type_var=float)
449 >>> print(k3)
450 (3.4, 2.3, 3.1)
451 >>> k1 is k3
452 False
454 >>> k4 = __to_tuple([3.4, 2.3, 3.1], ppl, type_var=float)
455 >>> print(k4)
456 (3.4, 2.3, 3.1)
457 >>> k3 is k4
458 True
460 >>> try:
461 ... __to_tuple([], ppl)
462 ... except Exception as e:
463 ... print(e)
464 row has length 0.
466 >>> __to_tuple([], ppl, empty_ok=True)
467 ()
469 >>> try:
470 ... __to_tuple([1, 2.0], ppl)
471 ... except Exception as e:
472 ... print(e)
473 row[1] should be an instance of int but is float, namely 2.0.
475 >>> try:
476 ... __to_tuple([1.1, 2.0, 4, 3.4], ppl, type_var=float)
477 ... except Exception as e:
478 ... print(e)
479 row[2] should be an instance of float but is int, namely 4.
480 """
481 use_row = source if isinstance(source, tuple) else tuple(source)
482 if (tuple.__len__(use_row) <= 0) and (not empty_ok):
483 raise ValueError("row has length 0.")
484 for j, v in enumerate(use_row):
485 if not isinstance(v, type_var):
486 raise type_error(v, f"row[{j}]", type_var)
487 if not (isfinite(v) and (0 <= v <= MAX_VALUE)): # type: ignore
488 raise ValueError(f"row[{j}]={v} not in 0..{MAX_VALUE}")
490 return cache(use_row)
493def __to_npfloats(source: Iterable[int | float], # pylint: disable=W1113
494 cache: Callable, empty_ok: bool = False,
495 *_) -> np.ndarray: # pylint: disable=W1113
496 """
497 Convert to numpy floats.
499 :param source: the source data
500 :param cache: the cache
501 :param empty_ok: are empty arrays OK?
502 :return: the arrays
504 >>> ppl = repr_cache()
505 >>> a = __to_npfloats([3.4, 2.3, 3.1], ppl)
506 >>> a
507 array([3.4, 2.3, 3.1])
508 >>> b = __to_npfloats([3.4, 2.3, 3.1], ppl)
509 >>> b is a
510 True
512 >>> c = __to_npfloats([], ppl, empty_ok=True)
513 >>> c
514 array([], dtype=float64)
516 >>> d = __to_npfloats([], ppl, empty_ok=True)
517 >>> d is c
518 True
519 """
520 return cache(np.array(__to_tuple(
521 source, cache, empty_ok, float), np.float64))
524def __to_nested_tuples(source: Iterable,
525 cache: Callable, empty_ok: bool = False,
526 type_var: type = int,
527 inner: Callable = __to_tuple) -> tuple:
528 """
529 Turn nested iterables of ints into nested tuples.
531 :param source: the source list
532 :param cache: the cache
533 :param empty_ok: are empty tuples OK?
534 :param type_var: the type variable
535 :param inner: the inner function
536 :return: the tuple or array
538 >>> ppl = repr_cache()
539 >>> k1 = __to_nested_tuples([(1, 2), [3, 2]], ppl)
540 >>> print(k1)
541 ((1, 2), (3, 2))
543 >>> k2 = __to_nested_tuples([(1, 2), (1, 2, 4), (1, 2)], ppl)
544 >>> print(k2)
545 ((1, 2), (1, 2, 4), (1, 2))
547 >>> k2[0] is k2[2]
548 True
550 >>> k1[0] is k2[0]
551 True
552 >>> k1[0] is k2[2]
553 True
555 >>> __to_nested_tuples([(1, 2), (1, 2, 4), (1, 2), []], ppl, True)
556 ((1, 2), (1, 2, 4), (1, 2), ())
558 >>> __to_nested_tuples([(), {}, []], ppl, True)
559 ()
561 >>> __to_nested_tuples([(1.0, 2.4), (1.0, 2.2)], ppl, True, float)
562 ((1.0, 2.4), (1.0, 2.2))
563 """
564 if not isinstance(source, Iterable):
565 raise type_error(source, "source", Iterable)
566 dest: list = []
567 ins: int = 0
568 for row in source:
569 use_row = inner(row, cache, empty_ok, type_var)
570 ins += len(use_row)
571 dest.append(use_row)
573 if (ins <= 0) and empty_ok: # if all inner tuples are empty,
574 dest.clear() # clear the tuple source
576 n_rows: Final[int] = list.__len__(dest)
577 if (n_rows <= 0) and (not empty_ok):
578 raise ValueError("Got empty set of rows!")
580 return cache(tuple(dest))
583def __to_tuples(source: Iterable[Iterable],
584 cache: Callable, empty_ok: bool = False, type_var=int,
585 inner: Callable = __to_tuple) \
586 -> tuple[tuple, ...]:
587 """
588 Turn 2D nested iterables into 2D nested tuples.
590 :param source: the source
591 :param cache: the cache
592 :param empty_ok: are empty tuples OK?
593 :param type_var: the type variable
594 :param inner: the inner callable
595 :return: the nested tuples
597 >>> ppl = repr_cache()
598 >>> k1 = __to_tuples([(1, 2), [3, 2]], ppl)
599 >>> print(k1)
600 ((1, 2), (3, 2))
602 >>> k2 = __to_tuples([(1, 2), (1, 2, 4), (1, 2)], ppl)
603 >>> print(k2)
604 ((1, 2), (1, 2, 4), (1, 2))
606 >>> k2[0] is k2[2]
607 True
608 >>> k1[0] is k2[0]
609 True
610 >>> k1[0] is k2[2]
611 True
612 """
613 return __to_nested_tuples(source, cache, empty_ok, type_var, inner)
616def __to_2d_npfloat(source: Iterable[Iterable], # pylint: disable=W1113
617 cache: Callable, empty_ok: bool = False,
618 *_) -> tuple[np.ndarray, ...]: # pylint: disable=W1113
619 """
620 Turn 2D nested iterables into 2D nested tuples.
622 :param source: the source
623 :param cache: the cache
624 :param empty_ok: are empty tuples OK?
625 :param inner: the inner callable
626 :return: the nested tuples
628 >>> ppl = repr_cache()
629 >>> k2 = __to_2d_npfloat([(1.0, 2.0), (1.0, 2.0, 4.0), (1.0, 0.2)], ppl)
630 >>> print(k2)
631 (array([1., 2.]), array([1., 2., 4.]), array([1. , 0.2]))
632 """
633 return __to_nested_tuples(source, cache, empty_ok, float, __to_npfloats)
636def __to_3d_npfloat(source: Iterable[Iterable[Iterable]],
637 cache: Callable, empty_ok: bool) \
638 -> tuple[tuple[np.ndarray, ...], ...]:
639 """
640 Turn 3D nested iterables into 3D nested tuples.
642 :param source: the source
643 :param cache: the cache
644 :param empty_ok: are empty tuples OK?
645 :return: the nested tuples
647 >>> ppl = repr_cache()
648 >>> k1 = __to_3d_npfloat([[[3.0, 2.0], [44.0, 5.0], [2.0]],
649 ... [[2.0], [5.0, 7.0]]], ppl, False)
650 >>> print(k1)
651 ((array([3., 2.]), array([44., 5.]), array([2.])), \
652(array([2.]), array([5., 7.])))
653 >>> k1[0][2] is k1[1][0]
654 True
655 """
656 return __to_nested_tuples(source, cache, empty_ok, float, __to_2d_npfloat)
659def _make_routes(
660 n_products: int, n_stations: int,
661 source: Iterable[Iterable[int]],
662 cache: Callable) -> tuple[tuple[int, ...], ...]:
663 """
664 Create the routes through stations for the products.
666 Each product passes through a set of stations. It can pass through each
667 station at most once. It can only pass through valid stations.
669 :param n_products: the number of products
670 :param n_stations: the number of stations
671 :param source: the source data
672 :param cache: the cache
673 :return: the routes, a tuple of tuples
675 >>> ppl = repr_cache()
676 >>> _make_routes(2, 3, ((1, 2), (1, 0)), ppl)
677 ((1, 2), (1, 0))
679 >>> _make_routes(3, 3, ((1, 2), (1, 0), (0, 1, 2)), ppl)
680 ((1, 2), (1, 0), (0, 1, 2))
682 >>> k = _make_routes(3, 3, ((1, 2), (1, 2), (0, 1, 2)), ppl)
683 >>> k[0] is k[1]
684 True
685 """
686 check_int_range(n_products, "n_products", 1, MAX_ID)
687 check_int_range(n_stations, "n_stations", 1, MAX_ID)
688 dest: tuple[tuple[int, ...], ...] = __to_tuples(source, cache)
690 n_rows: Final[int] = tuple.__len__(dest)
691 if n_rows != n_products:
692 raise ValueError(f"{n_products} products, but {n_rows} routes.")
693 for i, route in enumerate(dest):
694 stations: int = tuple.__len__(route)
695 if stations <= 0:
696 raise ValueError(
697 f"len(row[{i}])={stations} but n_stations={n_stations}")
698 for j, v in enumerate(route):
699 if not 0 <= v < n_stations:
700 raise ValueError(
701 f"row[{i},{j}]={v}, but n_stations={n_stations}")
702 return dest
705def __to_demand(
706 source: Iterable[int | float], time_end_warmup: float,
707 cache: Callable) -> Demand:
708 """
709 Convert an integer source to a tuple or a demand.
711 :param source: the source
712 :param time_end_warmup: the end of the warmup time
713 :param cache: the cache
714 :return: the Demand
716 >>> ppl = repr_cache()
717 >>> d1 = __to_demand([1, 2, 3, 20, 10, 100], 10.0, ppl)
718 >>> d1
719 Demand(arrival=10.0, deadline=100.0, demand_id=1, \
720customer_id=2, product_id=3, amount=20, measure=True)
721 >>> d2 = __to_demand([1, 2, 3, 20, 10, 100], 10.0, ppl)
722 >>> d1 is d2
723 True
724 """
725 if isinstance(source, Demand):
726 return cast("Demand", source)
727 tup: tuple[int | float, ...] = tuple(source)
728 dl: int = tuple.__len__(tup)
729 if dl != 6:
730 raise ValueError(f"Expected 6 values, got {dl}.")
731 arrival: int | float = tup[DEMAND_ARRIVAL]
732 return cache(Demand(
733 demand_id=cast("int", tup[DEMAND_ID]),
734 customer_id=cast("int", tup[DEMAND_CUSTOMER]),
735 product_id=cast("int", tup[DEMAND_PRODUCT]),
736 amount=cast("int", tup[DEMAND_AMOUNT]),
737 arrival=arrival, deadline=tup[DEMAND_DEADLINE],
738 measure=time_end_warmup <= arrival))
741def _make_demands(n_products: int, n_customers: int, n_demands: int,
742 source: Iterable[Iterable[int | float]],
743 time_end_warmup: float,
744 time_end_measure: float, cache: Callable) \
745 -> tuple[Demand, ...]:
746 """
747 Create the demand records, sorted by release time.
749 Each demand is a tuple of demand_id, customer_id, product_id, amount,
750 release time, and deadline.
752 :param n_products: the number of products
753 :param n_customers: the number of customers
754 :param n_demands: the number of demands
755 :param time_end_warmup: the end of the warmup time
756 :param time_end_measure: the end of the measure time period
757 :param source: the source data
758 :param cache: the cache
759 :return: the demand tuples
761 >>> ppl = repr_cache()
762 >>> _make_demands(10, 10, 4, [[0, 2, 1, 4, 20, 21],
763 ... [2, 5, 2, 6, 17, 27],
764 ... [1, 6, 7, 12, 17, 21],
765 ... [3, 7, 3, 23, 5, 21]], 10.0, 1000.0, ppl)
766 (Demand(arrival=5.0, deadline=21.0, demand_id=3, customer_id=7,\
767 product_id=3, amount=23, measure=False),\
768 Demand(arrival=17.0, deadline=21.0, demand_id=1, customer_id=6,\
769 product_id=7, amount=12, measure=True),\
770 Demand(arrival=17.0, deadline=27.0, demand_id=2, customer_id=5,\
771 product_id=2, amount=6, measure=True),\
772 Demand(arrival=20.0, deadline=21.0, demand_id=0, customer_id=2,\
773 product_id=1, amount=4, measure=True))
774 """
775 check_int_range(n_products, "n_products", 1, MAX_ID)
776 check_int_range(n_customers, "n_customers", 1, MAX_ID)
777 check_int_range(n_demands, "n_demands", 1, MAX_ID)
779 def __make_demand(ssss: Iterable[int | float],
780 ccc: Callable, *_) -> Demand:
781 return __to_demand(ssss, time_end_warmup, ccc)
783 temp: tuple[Demand, ...] = __to_nested_tuples(
784 source, cache, False, inner=__make_demand)
785 n_dem: int = tuple.__len__(temp)
786 if n_dem != n_demands:
787 raise ValueError(f"Expected {n_demands} demands, got {n_dem}?")
789 used_ids: set[int] = set()
790 min_id: int = 1000 * MAX_ID
791 max_id: int = -1000 * MAX_ID
792 dest: list[Demand] = []
794 for i, demand in enumerate(temp):
795 d_id: int = demand.demand_id
796 if not 0 <= d_id < n_demands:
797 raise ValueError(f"demand[{i}].id = {d_id}")
798 if d_id in used_ids:
799 raise ValueError(f"demand[{i}].id {d_id} appears twice!")
800 used_ids.add(d_id)
801 min_id = min(min_id, d_id)
802 max_id = max(max_id, d_id)
804 c_id: int = demand.customer_id
805 if not 0 <= c_id < n_customers:
806 raise ValueError(f"demand[{i}].customer = {c_id}, "
807 f"but n_customers={n_customers}")
809 p_id: int = demand.product_id
810 if not 0 <= p_id < n_products:
811 raise ValueError(f"demand[{i}].product = {p_id}, "
812 f"but n_products={n_products}")
814 amount: int = demand.amount
815 if not 0 < amount < MAX_ID:
816 raise ValueError(f"demand[{i}].amount = {amount}.")
818 arrival: float = demand.arrival
819 if not (isfinite(arrival) and (0 < arrival < MAX_ID)):
820 raise ValueError(f"demand[{i}].arrival = {arrival}.")
822 deadline: float = demand.deadline
823 if not (isfinite(deadline) and arrival <= deadline < MAX_ID):
824 raise ValueError(f"demand[{i}].deadline = {deadline}.")
826 if arrival >= time_end_measure:
827 raise ValueError(f"Demand[{i}]={demand!r} has arrival after "
828 "end of measurement period.")
829 dest.append(demand)
831 sl: int = set.__len__(used_ids)
832 if sl != n_demands:
833 raise ValueError(f"Got {n_demands} demands, but {sl} ids???")
834 if ((max_id - min_id + 1) != n_demands) or (min_id != 0):
835 raise ValueError(f"Invalid demand id range [{min_id}, {max_id}].")
836 dest.sort()
837 return cache(tuple(dest))
840def _make_in_warehouse(n_products: int, source: Iterable[int],
841 cache: Callable) \
842 -> tuple[int, ...]:
843 """
844 Make the amount of product in the warehouse at time 0.
846 :param n_products: the total number of products
847 :param source: the data source
848 :param cache: the tuple cache
849 :return: the amount of products in the warehouse
851 >>> _make_in_warehouse(3, [1, 2, 3], repr_cache())
852 (1, 2, 3)
853 """
854 ret: tuple[int, ...] = __to_tuple(source, cache)
855 rl: Final[int] = tuple.__len__(ret)
856 if rl != n_products:
857 raise ValueError(f"We have {n_products} products, "
858 f"but the warehouse list length is {rl}.")
859 for p, v in enumerate(ret):
860 if not 0 <= v <= MAX_ID:
861 raise ValueError(f"Got {v} units of product {p} in warehouse?")
862 return ret
865def _make_station_product_unit_times(
866 n_products: int, n_stations: int,
867 routes: tuple[tuple[float, ...], ...],
868 source: Iterable[Iterable[Iterable[float]]],
869 cache: Callable) -> tuple[tuple[np.ndarray, ...], ...]:
870 """
871 Create the structure for the work times per product unit per station.
873 Here we have for each station, for each product, a sequence of per-unit
874 production settings. Each such "production settings" is a tuple with a
875 per-unit production time and an end time index until which it is valid.
876 Production times cycle, so if we produce something after the last end
877 time index, we begin again at production time index 0.
879 :param n_products: the number of products
880 :param n_stations: the number of stations
881 :param routes: the routes of the products through the stations
882 :param source: the source array
883 :param cache: the cache
884 :return: the station unit times
886 >>> ppl = repr_cache()
887 >>> rts = _make_routes(3, 2, [[0, 1], [0], [1, 0]], ppl)
888 >>> print(rts)
889 ((0, 1), (0,), (1, 0))
891 >>> mpt1 = _make_station_product_unit_times(3, 2, rts, [
892 ... [[1.0, 2.0, 3.0, 5.0], [1.0, 2.0, 3.0, 5.0],
893 ... [1.0, 10.0, 2.0, 30.0]],
894 ... [[2.0, 20.0, 3.0, 40.0], [], [4.0, 56.0, 34.0, 444.0]]], ppl)
895 >>> print(mpt1)
896 ((array([1., 2., 3., 5.]), array([1., 2., 3., 5.]), \
897array([ 1., 10., 2., 30.])), (array([ 2., 20., 3., 40.]), \
898array([], dtype=float64), array([ 4., 56., 34., 444.])))
899 >>> mpt1[0][0] is mpt1[0][1]
900 True
902 >>> mpt2 = _make_station_product_unit_times(3, 2, rts, [
903 ... [[1.0, 2.0, 3.0, 5.0], [1.0, 2.0, 3.0, 5.0],
904 ... [1.0, 10.0, 2.0, 30.0]],
905 ... [[2.0, 20.0, 3.0, 40.0], [], [4.0, 56.0, 34.0, 444.0]]], ppl)
906 >>> print(mpt2)
907 ((array([1., 2., 3., 5.]), array([1., 2., 3., 5.]), \
908array([ 1., 10., 2., 30.])), (array([ 2., 20., 3., 40.]), \
909array([], dtype=float64), array([ 4., 56., 34., 444.])))
910 >>> mpt1 is mpt2
911 True
912 """
913 ret: tuple[tuple[np.ndarray, ...], ...] = __to_3d_npfloat(
914 source, cache, True)
916 if tuple.__len__(routes) != n_products:
917 raise ValueError("invalid routes!")
919 d1: int = tuple.__len__(ret)
920 if d1 != n_stations:
921 raise ValueError(
922 f"Got {d1} station-times, but {n_stations} stations.")
923 for mid, station in enumerate(ret):
924 d2: int = tuple.__len__(station)
925 if d2 <= 0:
926 for pid, r in enumerate(routes):
927 if mid in r:
928 raise ValueError(
929 f"Station {mid} in route for product {pid}, "
930 "but has no production time")
931 continue
932 if d2 != n_products:
933 raise ValueError(f"got {d2} products for station {mid}, "
934 f"but have {n_products} products")
935 for pid, product in enumerate(station):
936 needs_times: bool = mid in routes[pid]
937 d3: int = np.ndarray.__len__(product)
938 if (not needs_times) and (d3 > 0):
939 raise ValueError(
940 f"product {pid} does not pass through station {mid}, "
941 "so there must not be production times!")
942 if needs_times and (d3 <= 0):
943 raise ValueError(
944 f"product {pid} does pass through station {mid}, "
945 "so there must be production times!")
946 if (d3 % 2) != 0:
947 raise ValueError(
948 f"production times for {pid} does pass through station "
949 f"{mid}, must be of even length, but got length {d3}.")
950 last_end = 0
951 for pt, time in enumerate(batched(product, 2)):
952 if tuple.__len__(time) != 2:
953 raise ValueError(f"production times must be 2-tuples, "
954 f"but got {time} for product {pid} on "
955 f"station {mid} at position {pt}")
956 unit_time, end = time
957 if not ((unit_time > 0) and (last_end < end < MAX_ID)):
958 raise ValueError(
959 f"Invalid unit time {unit_time} and end time "
960 f"{end} for product {pid} on station {mid}")
961 last_end = end
963 return ret
966def _make_infos(source: Iterable[tuple[str, str]] | Mapping[str, str] | None)\
967 -> Mapping[str, str]:
968 """
969 Make the additional information record.
971 :param source: the information to represent
972 :return: the information record
973 """
974 use_source: Iterable[tuple[str, str]] = () if source is None else (
975 source.items() if isinstance(source, Mapping) else source)
976 if not isinstance(use_source, Iterable):
977 raise type_error(source, "infos", Iterable)
978 dst: dict[str, str] = {}
979 for i, tup in enumerate(use_source):
980 if tuple.__len__(tup) != 2:
981 raise ValueError(f"Invalid tuple {tup} at index {i} in infos.")
982 k: str = str.strip(tup[0])
983 v: str = str.strip(tup[1])
984 if (str.__len__(k) <= 0) or (str.__len__(v) <= 0):
985 raise ValueError(f"Invalid key/values {k!r}/{v!r} in tuple "
986 f"{tup} at index {i} in infos.")
987 if __FORBIDDEN_INFO_KEYS(str.lower(k)):
988 raise ValueError(
989 f"Info key {k!r} in tuple {tup} forbidden at index {i}.")
990 if not all(map(__ALLOWED_INFO_KEY_CHARS, k)):
991 raise ValueError(
992 f"Malformed info key {k!r} in tuple {tup} at index {i}.")
993 if k in dst:
994 raise ValueError(f"Duplicate key {k!r} found in tuple {tup} "
995 f"at index {i} in infos.")
996 dst[k] = v
997 return immutable_mapping(dst)
1000class Instance(Component):
1001 """An instance of the Production Scheduling Problem."""
1003 def __init__(
1004 self, name: str,
1005 n_products: int, n_customers: int, n_stations: int,
1006 n_demands: int,
1007 time_end_warmup: int | float, time_end_measure: int | float,
1008 routes: Iterable[Iterable[int]],
1009 demands: Iterable[Iterable[int | float]],
1010 warehous_at_t0: Iterable[int],
1011 station_product_unit_times: Iterable[Iterable[Iterable[float]]],
1012 infos: Iterable[tuple[str, str]] | Mapping[
1013 str, str] | None = None) \
1014 -> None:
1015 """
1016 Create an instance of the production scheduling time.
1018 :param name: the instance name
1019 :param n_products: the number of products
1020 :param n_customers: the number of customers
1021 :param n_stations: the number of stations
1022 :param n_demands: the number of demand records
1023 :param time_end_warmup: the time unit when the warmup time ends and the
1024 actual measurement begins
1025 :param time_end_measure: the time unit when the actual measure time
1026 ends
1027 :param routes: for each product, the sequence of stations that it has
1028 to pass
1029 :param demands: a sequences of demands of the form (
1030 customer_id, product_id, product_amount, release_time) OR a
1031 sequence of :class:`Demand` records.
1032 :param warehous_at_t0: the amount of products in the warehouse at time
1033 0 for each product
1034 :param station_product_unit_times: for each station and each product
1035 the per-unit-production time schedule, in the form of
1036 "per_unit_time, duration", where duration is the number of time
1037 units for which the per_unit_time is value
1038 :param station_product_unit_times: the cycling unit times for each
1039 product on each station, each with a validity duration
1040 :param infos: additional infos to be stored with the instance.
1041 These are key-value pairs with keys that are not used by the
1042 instance. They have no impact on the instance performance, but may
1043 explain settings of an instance generator.
1044 """
1045 use_name: Final[str] = sanitize_name(name)
1046 if name != use_name:
1047 raise ValueError(f"Name {name!r} is not a valid name.")
1048 if not all(map(_ALLOWED_NAME_CHARS, name)):
1049 raise ValueError(f"Name {name!r} contains invalid characters.")
1050 #: the name of this instance
1051 self.name: Final[str] = name
1053 #: the number of products in the scenario
1054 self.n_products: Final[int] = check_int_range(
1055 n_products, "n_products", 1, MAX_ID)
1056 #: the number of customers in the scenario
1057 self.n_customers: Final[int] = check_int_range(
1058 n_customers, "n_customers", 1, MAX_ID)
1059 #: the number of stations or workstations in the scenario
1060 self.n_stations: Final[int] = check_int_range(
1061 n_stations, "n_stations", 1, MAX_ID)
1062 #: the number of demands in the scenario
1063 self.n_demands: Final[int] = check_int_range(
1064 n_demands, "n_demands", 1, MAX_ID)
1066 if not isinstance(time_end_warmup, int | float):
1067 raise type_error(time_end_warmup, "time_end_warmup", (int, float))
1068 time_end_warmup = float(time_end_warmup)
1069 if not (isfinite(time_end_warmup) and (
1070 0 <= time_end_warmup < MAX_VALUE)):
1071 raise ValueError(f"Invalid time_end_warmup={time_end_warmup}.")
1072 #: the end of the warmup time
1073 self.time_end_warmup: Final[float] = time_end_warmup
1075 if not isinstance(time_end_measure, int | float):
1076 raise type_error(time_end_measure, "time_end_measure", (
1077 int, float))
1078 time_end_measure = float(time_end_measure)
1079 if not (isfinite(time_end_measure) and (
1080 time_end_warmup < time_end_measure < MAX_VALUE)):
1081 raise ValueError(f"Invalid time_end_measure={time_end_measure} "
1082 f"for time_end_warmup={time_end_warmup}.")
1083 #: the end of the measurement time
1084 self.time_end_measure: Final[float] = time_end_measure
1086 cache: Final[Callable] = repr_cache() # the pool for resolving tuples
1088 #: the product routes, i.e., the stations through which each product
1089 #: must pass
1090 self.routes: Final[tuple[tuple[int, ...], ...]] = _make_routes(
1091 n_products, n_stations, routes, cache)
1092 #: The demands: Each demand is a tuple of demand_id, customer_id,
1093 #: product_id, amount, release_time, and deadline.
1094 #: The customer makes their order at time step release_time.
1095 #: They expect to receive their product by the deadline.
1096 #: The demands are sorted by release time and then deadline.
1097 #: The release time is always > 0.
1098 #: The deadline is always >= release time.
1099 #: Demand ids are unique.
1100 self.demands: Final[tuple[Demand, ...]] = _make_demands(
1101 n_products, n_customers, n_demands, demands, time_end_warmup,
1102 time_end_measure, cache)
1104 # count the demands that fall in the measure time window
1105 n_measure: int = 0
1106 n_measures: list[int] = [0] * n_products
1107 for d in self.demands:
1108 if d.arrival >= self.time_end_measure:
1109 raise ValueError(f"Invalid arrival time of demand {d!r}.")
1110 if d.measure != (self.time_end_warmup <= d.arrival):
1111 raise ValueError(
1112 f"Inconsistent measure property for demand {d!r}.")
1113 if d.measure:
1114 n_measure += 1
1115 n_measures[d.product_id] += 1
1116 if n_measure <= 0:
1117 raise ValueError("There are no measurable demands!")
1118 for pid, npm in enumerate(n_measures):
1119 if npm <= 0:
1120 raise ValueError(f"No measurable demand for product {pid}!")
1121 #: the number of demands that actually fall into the time measured
1122 #: window
1123 self.n_measurable_demands: Final[int] = n_measure
1124 #: the measurable demands on a per-product basis
1125 self.n_measurable_demands_per_product: Final[tuple[int, ...]] = tuple(
1126 n_measures)
1128 #: The units of product in the warehouse at time step 0.
1129 #: For each product, we have either 0 or a positive amount of product.
1130 self.warehous_at_t0: Final[tuple[int, ...]] = _make_in_warehouse(
1131 n_products, warehous_at_t0, cache)
1133 #: The per-station unit production times for each product.
1134 #: Each station can have different production times per product.
1135 #: Let's say that this is tuple `A`.
1136 #: For each product, it has a tuple `B` at the index of the product
1137 #: id.
1138 #: If the product does not pass through the station, `B` is empty.
1139 #: Otherwise, it holds one or multiple tuples `C`.
1140 #: Each tuple `C` consists of two numbers:
1141 #: A per-unit-production time for the product.
1142 #: An end time index for this production time.
1143 #: Once the real time surpasses the end time of the last of these
1144 #: production specs, the production specs are recycled and begin
1145 #: again.
1146 self.station_product_unit_times: Final[tuple[tuple[
1147 np.ndarray, ...], ...]] = _make_station_product_unit_times(
1148 n_products, n_stations, self.routes, station_product_unit_times,
1149 cache)
1151 #: Additional information about the nature of the instance can be
1152 #: stored here. This has no impact on the behavior of the instance,
1153 #: but it may explain, e.g., settings of an instance generator.
1154 self.infos: Final[Mapping[str, str]] = _make_infos(infos)
1156 def __str__(self):
1157 """
1158 Get the name of this instance.
1160 :return: the name of this instance
1161 """
1162 return self.name
1164 def _tuple(self) -> tuple:
1165 """
1166 Convert this object to a tuple.
1168 :return: the tuple
1170 >>> Instance(name="test1", n_products=1, n_customers=1, n_stations=2,
1171 ... n_demands=1, time_end_warmup=12, time_end_measure=30,
1172 ... routes=[[0, 1]], demands=[[0, 0, 0, 10, 20, 100]],
1173 ... warehous_at_t0=[0],
1174 ... station_product_unit_times=[[[10.0, 10000.0]],
1175 ... [[30.0, 10000.0]]])._tuple()
1176 ('test1', 2, 1, 1, 1, 12.0, 30.0, (Demand(arrival=20.0,\
1177 deadline=100.0, demand_id=0, customer_id=0, product_id=0, amount=10,\
1178 measure=True),), ((0, 1),), (0,), (), ((10.0, 10000.0), (30.0, 10000.0)))
1179 """
1180 return (self.name, self.n_stations, self.n_products,
1181 self.n_demands, self.n_customers, self.time_end_warmup,
1182 self.time_end_measure, self.demands,
1183 self.routes, self.warehous_at_t0, tuple(self.infos.items()),
1184 tuple(tuple(float(x) for x in a2) for a1 in
1185 self.station_product_unit_times for a2 in a1))
1187 def __eq__(self, other):
1188 """
1189 Compare this object with another object.
1191 :param other: the other object
1192 :return: `NotImplemented` if the other object is not an `Instance`,
1193 otherwise the equality comparison result.
1195 >>> i1 = Instance(name="test1", n_products=1, n_customers=1,
1196 ... n_stations=2, n_demands=1,
1197 ... time_end_warmup=12, time_end_measure=30,
1198 ... routes=[[0, 1]],
1199 ... demands=[[0, 0, 0, 10, 20, 100]],
1200 ... warehous_at_t0=[0],
1201 ... station_product_unit_times=[[[10.0, 10000.0]],
1202 ... [[30.0, 10000.0]]])
1203 >>> i2 = Instance(name="test1", n_products=1, n_customers=1,
1204 ... n_stations=2, n_demands=1,
1205 ... time_end_warmup=12, time_end_measure=30,
1206 ... routes=[[0, 1]],
1207 ... demands=[[0, 0, 0, 10, 20, 100]],
1208 ... warehous_at_t0=[0],
1209 ... station_product_unit_times=[[[10.0, 10000.0]],
1210 ... [[30.0, 10000.0]]])
1211 >>> i1 == i2
1212 True
1213 >>> i3 = Instance(name="test1", n_products=1, n_customers=1,
1214 ... n_stations=2, n_demands=1,
1215 ... time_end_warmup=12, time_end_measure=30,
1216 ... routes=[[0, 1]],
1217 ... demands=[[0, 0, 0, 10, 20, 100]],
1218 ... warehous_at_t0=[0],
1219 ... station_product_unit_times=[[[10.0, 10000.1]],
1220 ... [[30.0, 10000.0]]])
1221 >>> i1 == i3
1222 False
1223 """
1224 if other is None:
1225 return False
1226 if not isinstance(other, Instance):
1227 return NotImplemented
1228 return self._tuple() == cast("Instance", other)._tuple()
1230 def __hash__(self) -> int:
1231 """
1232 Get the hash code of this object.
1234 :return: the hash code of this object
1235 """
1236 return hash(self._tuple())
1239#: the instance name key
1240KEY_NAME: Final[str] = "name"
1241#: the key for the number of products
1242KEY_N_PRODUCTS: Final[str] = "n_products"
1243#: the key for the number of customers
1244KEY_N_CUSTOMERS: Final[str] = "n_customers"
1245#: the key for the number of stations
1246KEY_N_STATIONS: Final[str] = "n_stations"
1247#: the number of demands in the scenario
1248KEY_N_DEMANDS: Final[str] = "n_demands"
1249#: the end of the warmup period
1250KEY_TIME_END_WARMUP: Final[str] = "time_end_warmup"
1251#: the end of the measure period
1252KEY_TIME_END_MEASURE: Final[str] = "time_end_measure"
1253#: the start of a key index
1254KEY_IDX_START: Final[str] = "["
1255#: the end of a key index
1256KEY_IDX_END: Final[str] = "]"
1257#: the first part of the product route key
1258KEY_ROUTE: Final[str] = "product_route"
1259#: the first part of the demand key
1260KEY_DEMAND: Final[str] = "demand"
1261#: The amount of products in the warehouse at time step 0.
1262KEY_IN_WAREHOUSE: Final[str] = "products_in_warehouse_at_t0"
1263#: the first part of the production time
1264KEY_PRODUCTION_TIME: Final[str] = "production_time"
1266#: the key value split string
1267_KEY_VALUE_SPLIT: Final[str] = str.strip(KEY_VALUE_SEPARATOR)
1269#: the forbidden keys
1270__FORBIDDEN_INFO_KEYS: Final[Callable[[str], bool]] = {
1271 KEY_NAME, KEY_N_PRODUCTS, KEY_N_CUSTOMERS, KEY_N_STATIONS,
1272 KEY_N_DEMANDS, KEY_TIME_END_MEASURE, KEY_TIME_END_WARMUP,
1273 KEY_ROUTE, KEY_DEMAND, KEY_IN_WAREHOUSE, KEY_PRODUCTION_TIME}.__contains__
1275#: the allowed information key characters
1276__ALLOWED_INFO_KEY_CHARS: Final[Callable[[str], bool]] = set(
1277 ascii_letters + digits + "_." + KEY_IDX_START + KEY_IDX_END).__contains__
1279#: the allowed characters in names
1280_ALLOWED_NAME_CHARS: Final[Callable[[str], bool]] = set(
1281 ascii_letters + digits + "_").__contains__
1284def to_stream(instance: Instance) -> Generator[str, None, None]:
1285 """
1286 Convert an instance to a stream of data.
1288 :param instance: the instance to convert to a stream
1289 :return: the stream of data
1290 """
1291 if not isinstance(instance, Instance):
1292 raise type_error(instance, "instance", Instance)
1294 yield f"{COMMENT_START} --- the data of instance {instance.name!r} ---"
1295 yield COMMENT_START
1296 yield (f"{COMMENT_START} Lines beginning with {COMMENT_START!r} are "
1297 f"comments.")
1298 yield COMMENT_START
1299 yield f"{COMMENT_START} the unique identifying name of the instance"
1300 yield f"{KEY_NAME}{KEY_VALUE_SEPARATOR}{instance.name}"
1301 yield COMMENT_START
1302 yield f"{COMMENT_START} the number of products in the instance, > 0"
1303 yield f"{KEY_N_PRODUCTS}{KEY_VALUE_SEPARATOR}{instance.n_products}"
1304 yield (f"{COMMENT_START} Valid product indices are in 0.."
1305 f"{instance.n_products - 1}.")
1306 yield COMMENT_START
1307 yield f"{COMMENT_START} the number of customers in the instance, > 0"
1308 yield f"{KEY_N_CUSTOMERS}{KEY_VALUE_SEPARATOR}{instance.n_customers}"
1309 yield (f"{COMMENT_START} Valid customer indices are in 0.."
1310 f"{instance.n_customers - 1}.")
1311 yield COMMENT_START
1312 yield f"{COMMENT_START} the number of stations in the instance, > 0"
1313 yield f"{KEY_N_STATIONS}{KEY_VALUE_SEPARATOR}{instance.n_stations}"
1314 yield (f"{COMMENT_START} Valid station indices are in 0.."
1315 f"{instance.n_stations - 1}.")
1316 yield COMMENT_START
1317 yield (f"{COMMENT_START} the number of customer orders (demands) issued "
1318 f"by the customers, > 0")
1319 yield f"{KEY_N_DEMANDS}{KEY_VALUE_SEPARATOR}{instance.n_demands}"
1320 yield (f"{COMMENT_START} Valid demand/order indices are in 0.."
1321 f"{instance.n_demands - 1}.")
1322 yield COMMENT_START
1323 yield (f"{COMMENT_START} end of the warmup period in the simulations, "
1324 f">= 0")
1325 wm: Final[str] = float_to_str(instance.time_end_warmup)
1326 yield f"{KEY_TIME_END_WARMUP}{KEY_VALUE_SEPARATOR}{wm}"
1327 yield (f"{COMMENT_START} The simulation will not measure anything "
1328 f"during the first {wm} time units.")
1329 yield COMMENT_START
1330 yield (f"{COMMENT_START} end of the measurement period in the "
1331 f"simulations, > {wm}")
1332 meas: Final[str] = float_to_str(instance.time_end_measure)
1333 yield f"{KEY_TIME_END_MEASURE}{KEY_VALUE_SEPARATOR}{meas}"
1334 yield (f"{COMMENT_START} The simulation will only measure things during "
1335 f" left-closed and right-open interval [{wm},{meas}).")
1337 yield COMMENT_START
1338 yield (f"{COMMENT_START} For each product, we now specify the indices of "
1339 f"the stations by which it will be processed, in the order in "
1340 f"which it will be processed by them.")
1341 yield (f"{COMMENT_START} {KEY_ROUTE}{KEY_IDX_START}0"
1342 f"{KEY_IDX_END} is the production route by the first product, "
1343 "which has index 0.")
1344 route_0: tuple[int, ...] = instance.routes[0]
1345 yield (f"{COMMENT_START} This product is processed by "
1346 f"{tuple.__len__(route_0)} stations, namely first by the "
1347 f"station with index {int(route_0[0])} and last by the station "
1348 f"with index {int(route_0[-1])}.")
1349 for p, route in enumerate(instance.routes):
1350 yield (f"{KEY_ROUTE}{KEY_IDX_START}{p}{KEY_IDX_END}"
1351 f"{KEY_VALUE_SEPARATOR}"
1352 f"{CSV_SEPARATOR.join(map(str, route))}")
1354 yield COMMENT_START
1355 yield (f"{COMMENT_START} For each customer order/demand, we now "
1356 f"specify the following values:")
1357 yield f"{COMMENT_START} 1. the demand ID in square brackets"
1358 yield f"{COMMENT_START} 2. the ID of the customer who made the order"
1359 yield f"{COMMENT_START} 3. the ID of the product that the customer ordered"
1360 yield (f"{COMMENT_START} 4. the amount of the product that the customer"
1361 " ordered")
1362 yield (f"{COMMENT_START} 5. the arrival time of the demand, > 0, i.e., "
1363 f"the moment in time when the customer informed us that they want "
1364 f"the product")
1365 yield (f"{COMMENT_START} 6. the deadline, i.e., when the customer expects "
1366 f"the product, >= arrival time")
1367 srt: list[Demand] = sorted(instance.demands, key=lambda d: d.demand_id)
1368 fd: Demand = srt[0]
1369 yield (f"{COMMENT_START} For example, the demand with ID {fd.demand_id} "
1370 f"was issued by the customer with ID {fd.customer_id} for "
1371 f"{fd.amount} units of the product with ID "
1372 f"{fd.product_id}.")
1373 yield (f"{COMMENT_START} The order comes into the "
1374 f"system at time unit {fd.arrival} and the customer expects "
1375 f"the product to be ready at time unit {fd.deadline}.")
1376 for demand in srt:
1377 it = iter(demand)
1378 next(it) # pylint: disable=R1708
1379 row: str = CSV_SEPARATOR.join(map(num_to_str, it))
1380 yield (f"{KEY_DEMAND}{KEY_IDX_START}{demand.demand_id}{KEY_IDX_END}"
1381 f"{KEY_VALUE_SEPARATOR}"
1382 f"{row}")
1384 yield COMMENT_START
1385 yield (f"{COMMENT_START} For each product, we now specify the amount "
1386 f"that is in the warehouse at time step 0.")
1387 yield (f"{COMMENT_START} For example, there are "
1388 f"{instance.warehous_at_t0[0]} units of product 0 in the "
1389 f"warehouse at the beginning of the simulation.")
1390 yield (f"{KEY_IN_WAREHOUSE}{KEY_VALUE_SEPARATOR}"
1391 f"{CSV_SEPARATOR.join(map(str, instance.warehous_at_t0))}")
1393 yield COMMENT_START
1394 yield (f"{COMMENT_START} For each station, we now specify the production "
1395 f"times for each product that passes through the station.")
1396 empty_pdx: tuple[int, int] | None = None
1397 filled_pdx: tuple[int, int, np.ndarray] | None = None
1398 need: int = 2
1399 for mid, station in enumerate(instance.station_product_unit_times):
1400 for pid, product in enumerate(station):
1401 pdl: int = np.ndarray.__len__(product)
1402 if (pdl <= 0) and (empty_pdx is None):
1403 empty_pdx = mid, pid
1404 need -= 1
1405 if need <= 0:
1406 break
1407 elif (pdl > 0) and (filled_pdx is None):
1408 filled_pdx = mid, pid, product
1409 need -= 1
1410 if need <= 0:
1411 break
1412 if need <= 0:
1413 break
1414 if empty_pdx is not None:
1415 yield (f"{COMMENT_START} For example, product {empty_pdx[1]} does "
1416 f"not pass through station {empty_pdx[0]}, so it is not "
1417 "listed here.")
1418 if filled_pdx is not None:
1419 yield (f"{COMMENT_START} For example, one unit of product "
1420 f"{filled_pdx[1]} passes through station {filled_pdx[0]}.")
1421 yield (f"{COMMENT_START} There, it needs {filled_pdx[2][0]} time "
1422 f"units per product unit from t=0 to t={filled_pdx[2][1]}.")
1423 if np.ndarray.__len__(filled_pdx[2]) > 2:
1424 yield (f"{COMMENT_START} After that, it needs {filled_pdx[2][2]}"
1425 " time units per product unit until t="
1426 f"{filled_pdx[2][3]}.")
1428 cache: dict[str, str] = {}
1429 for mid, station in enumerate(instance.station_product_unit_times):
1430 for pid, product in enumerate(station):
1431 if np.ndarray.__len__(product) <= 0:
1432 continue
1433 value: str = CSV_SEPARATOR.join(map(num_to_str, map(
1434 try_int, map(float, product))))
1435 key: str = (f"{KEY_PRODUCTION_TIME}{KEY_IDX_START}{mid}"
1436 f"{CSV_SEPARATOR}{pid}{KEY_IDX_END}")
1437 if value in cache:
1438 value = cache[value]
1439 else:
1440 cache[value] = key
1441 yield f"{key}{KEY_VALUE_SEPARATOR}{value}"
1443 n_infos: Final[int] = len(instance.infos)
1444 if n_infos > 0:
1445 yield COMMENT_START
1446 yield (f"{COMMENT_START} The following {n_infos} key/value pairs "
1447 "denote additional information about the instance.")
1448 yield (f"{COMMENT_START} They have no impact whatsoever on the "
1449 "instance behavior.")
1450 yield (f"{COMMENT_START} A common use case is that we may have "
1451 "used a method to randomly sample the instance.")
1452 yield (f"{COMMENT_START} In this case, we could store the parameters "
1453 f"of the instance generator, such as the random seed and/or "
1454 f"the distributions used in this section.")
1455 for k, v in instance.infos.items():
1456 yield f"{k}{KEY_VALUE_SEPARATOR}{v}"
1459def __get_key_index(full_key: str) -> str:
1460 """
1461 Extract the key index from a key.
1463 :param full_key: the full key
1464 :return: the key index
1466 >>> __get_key_index("s[12 ]")
1467 '12'
1468 """
1469 start: int = str.index(full_key, KEY_IDX_START)
1470 end: int = str.index(full_key, KEY_IDX_END, start)
1471 if not 0 < start < end < str.__len__(full_key):
1472 raise ValueError(f"Invalid key {full_key!r}.")
1473 idx: str = str.strip(full_key[start + 1:end])
1474 if str.__len__(idx) <= 0:
1475 raise ValueError(f"Invalid index in key {full_key!r}.")
1476 return idx
1479def __pe(message: str, oline: str, line_idx: int) -> ValueError:
1480 """
1481 Create a value error to be raised inside the parser.
1483 :param message: the message
1484 :param oline: the original line
1485 :param line_idx: the line index
1486 :return: the error
1487 """
1488 return ValueError(f"{message} at line {line_idx + 1} ({oline!r})")
1491def from_stream(stream: Iterable[str]) -> Instance:
1492 """
1493 Read an instance from a data stream.
1495 :param stream: the data stream
1496 :return: the instance
1497 """
1498 if not isinstance(stream, Iterable):
1499 raise type_error(stream, "stream", Iterable)
1500 name: str | None = None
1501 n_products: int | None = None
1502 n_customers: int | None = None
1503 n_stations: int | None = None
1504 n_demands: int | None = None
1505 time_end_warmup: int | float | None = None
1506 time_end_measure: int | float | None = None
1507 routes: list[list[int]] | None = None
1508 demands: list[list[int | float]] | None = None
1509 in_warehouse: list[int] | None = None
1510 station_product_times: list[list[list[float]]] | None = None
1511 infos: dict[str, str] = {}
1513 for line_idx, oline in enumerate(stream):
1514 line = str.strip(oline)
1515 if str.startswith(line, COMMENT_START):
1516 continue
1518 split_idx: int = str.find(line, _KEY_VALUE_SPLIT)
1519 if split_idx > -1:
1520 key: str = str.lower(str.strip(line[:split_idx]))
1521 value: str = str.strip(
1522 line[split_idx + str.__len__(_KEY_VALUE_SPLIT):])
1523 if (str.__len__(key) <= 0) or (str.__len__(value) <= 0):
1524 raise __pe(f"Invalid key/value pair {key!r}/{value!r}",
1525 oline, line_idx)
1527 if key == KEY_NAME:
1528 if name is not None:
1529 raise __pe(f"{KEY_NAME} already defined as {name!r}, "
1530 f"cannot be set to {value!r}", oline, line_idx)
1531 name = value
1533 elif key == KEY_N_STATIONS:
1534 if n_stations is not None:
1535 raise __pe(
1536 f"{KEY_N_STATIONS} already defined as {n_stations!r},"
1537 f" cannot be set to {value!r}", oline, line_idx)
1538 n_stations = check_to_int_range(
1539 value, KEY_N_STATIONS, 1, 1_000_000)
1541 elif key == KEY_N_PRODUCTS:
1542 if n_products is not None:
1543 raise __pe(
1544 f"{KEY_N_PRODUCTS} already defined as {n_products!r},"
1545 f" cannot be set to {value!r}", oline, line_idx)
1546 n_products = check_to_int_range(
1547 value, KEY_N_PRODUCTS, 1, 1_000_000)
1549 elif key == KEY_N_CUSTOMERS:
1550 if n_customers is not None:
1551 raise __pe(
1552 f"{KEY_N_CUSTOMERS} already defined as "
1553 f"{n_customers!r}, cannot be set to {value!r}",
1554 oline, line_idx)
1555 n_customers = check_to_int_range(
1556 value, KEY_N_CUSTOMERS, 1, 1_000_000)
1558 elif key == KEY_N_DEMANDS:
1559 if n_demands is not None:
1560 raise __pe(
1561 f"{KEY_N_DEMANDS} already defined as {n_demands!r}, "
1562 f"cannot be set to {value!r}", oline, line_idx)
1563 n_demands = check_to_int_range(
1564 value, KEY_N_DEMANDS, 1, 1_000_000)
1566 elif key == KEY_TIME_END_WARMUP:
1567 if time_end_warmup is not None:
1568 raise __pe(f"{KEY_TIME_END_WARMUP} already defined",
1569 oline, line_idx)
1570 time_end_warmup = float(value)
1571 if not (isfinite(time_end_warmup) and (time_end_warmup > 0)):
1572 raise __pe(f"time_end_warmup={time_end_warmup} invalid",
1573 oline, line_idx)
1575 elif key == KEY_TIME_END_MEASURE:
1576 if time_end_measure is not None:
1577 raise __pe(f"{KEY_TIME_END_MEASURE} already defined",
1578 oline, line_idx)
1579 time_end_measure = float(value)
1580 if not (isfinite(time_end_measure) and (
1581 time_end_measure > 0)):
1582 raise __pe(f"time_end_measure={time_end_measure} invalid",
1583 oline, line_idx)
1584 if (time_end_warmup is not None) and (
1585 time_end_measure <= time_end_warmup):
1586 raise __pe(f"time_end_warmup={time_end_warmup} and "
1587 f"time_end_measure={time_end_measure}",
1588 oline, line_idx)
1590 elif key == KEY_IN_WAREHOUSE:
1591 if in_warehouse is not None:
1592 raise __pe(f"{KEY_IN_WAREHOUSE} already defined",
1593 oline, line_idx)
1594 if n_products is None:
1595 raise __pe(f"Must define {KEY_N_PRODUCTS} before "
1596 f"{KEY_IN_WAREHOUSE}.", oline, line_idx)
1597 in_warehouse = list(map(int, str.split(
1598 value, CSV_SEPARATOR)))
1599 if list.__len__(in_warehouse) != n_products:
1600 raise __pe(
1601 f"Expected {n_products} products in warehouse, got "
1602 f"{in_warehouse}.", oline, line_idx)
1604 elif str.startswith(key, KEY_ROUTE):
1605 if n_products is None:
1606 raise __pe(f"Must define {KEY_N_PRODUCTS} before "
1607 f"{KEY_ROUTE}.", oline, line_idx)
1608 if n_stations is None:
1609 raise ValueError(f"Must define {KEY_N_STATIONS} before "
1610 f"{KEY_ROUTE}.", oline, line_idx)
1611 if routes is None:
1612 routes = [[] for _ in range(n_products)]
1614 product_id: int = check_to_int_range(
1615 __get_key_index(key), KEY_ROUTE, 0, n_products - 1)
1616 rlst: list[int] = routes[product_id]
1617 if list.__len__(rlst) != 0:
1618 raise __pe(
1619 f"Already gave {KEY_ROUTE}{KEY_IDX_START}{product_id}"
1620 f"{KEY_IDX_END}", oline, line_idx)
1621 rlst.extend(map(int, str.split(value, CSV_SEPARATOR)))
1622 if list.__len__(rlst) <= 0:
1623 raise __pe(f"Route for product {product_id} is empty",
1624 oline, line_idx)
1626 elif str.startswith(key, KEY_DEMAND):
1627 if n_customers is None:
1628 raise __pe(f"Must define {KEY_N_CUSTOMERS} before "
1629 f"{KEY_DEMAND}", oline, line_idx)
1630 if n_products is None:
1631 raise __pe(f"Must define {KEY_N_PRODUCTS} before "
1632 f"{KEY_DEMAND}.", oline, line_idx)
1633 if n_demands is None:
1634 raise __pe(f"Must define {KEY_N_DEMANDS} before "
1635 f"{KEY_DEMAND}", oline, line_idx)
1636 if demands is None:
1637 demands = [[i] for i in range(n_demands)]
1639 demand_id: int = check_to_int_range(
1640 __get_key_index(key), KEY_DEMAND, 0, n_demands - 1)
1641 dlst: list[int | float] = demands[demand_id]
1642 if list.__len__(dlst) != 1:
1643 raise __pe(f"Already gave {KEY_DEMAND}{KEY_IDX_START}"
1644 f"{demand_id}{KEY_IDX_END}", oline, line_idx)
1645 str_lst = str.split(value, CSV_SEPARATOR)
1646 if list.__len__(str_lst) != 5:
1647 raise __pe(
1648 f"Demand {demand_id} must have 5 entries, but got: "
1649 f"{str_lst!r}", oline, line_idx)
1650 dlst.extend((int(str_lst[0]), int(str_lst[1]),
1651 int(str_lst[2]), float(str_lst[3]),
1652 float(str_lst[4])))
1654 elif str.startswith(key, KEY_PRODUCTION_TIME):
1655 if n_products is None:
1656 raise __pe(f"Must define {KEY_N_PRODUCTS} before "
1657 f"{KEY_PRODUCTION_TIME}", oline, line_idx)
1658 if n_stations is None:
1659 raise __pe(f"Must define {KEY_N_STATIONS} before"
1660 f" {KEY_PRODUCTION_TIME}", oline, line_idx)
1661 station, product = str.split(
1662 __get_key_index(key), CSV_SEPARATOR)
1663 station_id: int = check_to_int_range(
1664 station, "station", 0, n_stations - 1)
1665 product_id = check_to_int_range(
1666 product, "product", 0, n_products - 1)
1668 if station_product_times is None:
1669 station_product_times = \
1670 [[[] for _ in range(n_products)]
1671 for __ in range(n_stations)]
1673 if str.startswith(value, KEY_PRODUCTION_TIME):
1674 station, product = str.split(
1675 __get_key_index(value), CSV_SEPARATOR)
1676 use_station_id: int = check_to_int_range(
1677 station, "station", 0, n_stations - 1)
1678 use_product_id = check_to_int_range(
1679 product, "product", 0, n_products - 1)
1680 station_product_times[station_id][product_id] = (
1681 station_product_times)[use_station_id][use_product_id]
1682 else:
1683 mpd: list[float] = station_product_times[
1684 station_id][product_id]
1685 if list.__len__(mpd) > 0:
1686 raise __pe(
1687 f"Already gave {KEY_PRODUCTION_TIME}"
1688 f"{KEY_IDX_START}{station_id}{CSV_SEPARATOR}"
1689 f"{product_id}{KEY_IDX_END}", oline, line_idx)
1690 mpd.extend(
1691 map(float, str.split(value, CSV_SEPARATOR)))
1692 else:
1693 infos[key] = value
1695 if name is None:
1696 raise ValueError(f"Did not specify instance name ({KEY_NAME}).")
1697 if n_products is None:
1698 raise ValueError("Did not specify instance n_products"
1699 f" ({KEY_N_PRODUCTS}).")
1700 if n_customers is None:
1701 raise ValueError("Did not specify instance n_customers"
1702 f" ({KEY_N_CUSTOMERS}).")
1703 if n_stations is None:
1704 raise ValueError("Did not specify instance n_stations"
1705 f" ({KEY_N_STATIONS}).")
1706 if n_demands is None:
1707 raise ValueError("Did not specify instance n_demands"
1708 f" ({KEY_N_DEMANDS}).")
1709 if time_end_warmup is None:
1710 raise ValueError("Did not specify instance time_end_warmup"
1711 f" ({KEY_TIME_END_WARMUP}).")
1712 if time_end_measure is None:
1713 raise ValueError("Did not specify instance time_end_measure"
1714 f" ({KEY_TIME_END_MEASURE}).")
1715 if routes is None:
1716 raise ValueError(f"Did not specify instance routes ({KEY_ROUTE}).")
1717 if demands is None:
1718 raise ValueError(f"Did not specify instance demands ({KEY_DEMAND}).")
1719 if in_warehouse is None:
1720 raise ValueError("Did not specify instance warehouse values"
1721 f" ({KEY_IN_WAREHOUSE}).")
1722 if station_product_times is None:
1723 raise ValueError("Did not specify per-station product production"
1724 f"times ({KEY_PRODUCTION_TIME}).")
1726 return Instance(name, n_products, n_customers, n_stations, n_demands,
1727 time_end_warmup, time_end_measure,
1728 routes, demands, in_warehouse, station_product_times,
1729 infos)
1732@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
1733def compute_finish_time(start_time: float, amount: int,
1734 production_times: np.ndarray) -> float:
1735 """
1736 Compute the time when one job is finished.
1738 The production times are cyclic intervals of unit production times and
1739 interval ends.
1741 :param start_time: the starting time of the job
1742 :param amount: the number of units to be produced
1743 :param production_times: the production times array
1744 :return: the end time
1746 Here, the production time is 10 time units / 1 product unit, valid until
1747 end time 100.
1749 >>> compute_finish_time(0.0, 1, np.array((10.0, 100.0), np.float64))
1750 10.0
1752 Here, the production time is 10 time units / 1 product unit, valid until
1753 end time 100. We begin producing at time unit 250. Since the production
1754 periods are cyclic, this is OK: we would be halfway through the third
1755 production period when the request comes in. It will consume 10 time units
1756 and be done at time unit 260.
1758 >>> compute_finish_time(250.0, 1, np.array((10.0, 100.0)))
1759 260.0
1761 Here, the end time of the production time validity is at time unit 100.
1762 However, we begin producing 1 product unit at time step 90. This unit will
1763 use 10 time units, meaning that its production is exactly finished when
1764 the production time validity ends.
1765 It will be finished at time step 100.
1767 >>> compute_finish_time(90.0, 1, np.array((10.0, 100.0)))
1768 100.0
1770 Here, the end time of the production time validity is at time unit 100.
1771 However, we begin producing 1 product unit at time step 95. This unit would
1772 use 10 time units. It will use these units, even though this extends beyond
1773 the end of the production time window.
1775 >>> compute_finish_time(95.0, 1, np.array((10.0, 100.0)))
1776 105.0
1778 Now we have two production periods. The production begins again at time
1779 step 95. It will use 10 time units, even though this extends into the
1780 second period.
1782 >>> compute_finish_time(95.0, 1, np.array((10.0, 100.0, 20.0, 200.0)))
1783 105.0
1785 Now things get more complex. We want to do 10 units of product.
1786 We start in the first period, so one unit will be completed there.
1787 This takes the starting time for the next job to 105, which is in the
1788 second period. Here, one unit of product takes 20 time units. We can
1789 finish producing one unit until time 125 and start the production of a
1790 second one, taking until 145. Now the remaining three units are produced
1791 until time 495
1792 >>> compute_finish_time(95.0, 10, np.array((
1793 ... 10.0, 100.0, 20.0, 140.0, 50.0, 5000.0)))
1794 495.0
1795 >>> 95 + (1*10 + 2*20 + 7*50)
1796 495
1798 We again produce 10 product units starting at time step 95. The first one
1799 takes 10 time units, taking us into the second production interval at time
1800 105. Then we can again do two units here, which consume 40 time units,
1801 taking us over the edge into the third interval at time unit 145. Here we
1802 do two units using 50 time units. We ahen are at time 245, which wraps back
1803 to 45. So the remaining 5 units take 10 time units each.
1805 >>> compute_finish_time(95.0, 10, np.array((
1806 ... 10.0, 100.0, 20.0, 140.0, 50.0, 200.0)))
1807 295.0
1808 >>> 95 + (1*10 + 2*20 + 2*50 + 5*10)
1809 295
1811 This is the same as the last example, but this time, the last interval
1812 (3 time units until 207) is skipped over by the long production of the
1813 second 50-time-unit product.
1815 >>> compute_finish_time(95.0, 10, np.array((
1816 ... 10.0, 100.0, 20.0, 140.0, 50.0, 200.0, 3.0, 207.0)))
1817 295.0
1818 >>> 95 + (1*10 + 2*20 + 2*50 + 5*10)
1819 295
1821 Production unit times may extend beyond the intervals.
1823 >>> compute_finish_time(0.0, 5, np.array((1000.0, 100.0, 10.0, 110.0)))
1824 5000.0
1825 >>>
1826 5 * 1000
1827 """
1828 time_mod: Final[float] = production_times[-1]
1829 low_end: Final[int] = len(production_times)
1830 total: Final[int] = low_end // 2
1832 # First, we need to find the segment in the production cycle
1833 # where the production begins. We use a binary search for that.
1834 remaining: int | float = amount
1835 seg_start: float = start_time % time_mod
1836 low: int = 0
1837 high: int = total
1838 while low < high:
1839 mid: int = (low + high) // 2
1840 th: float = production_times[mid * 2 + 1]
1841 if th <= seg_start:
1842 low = mid + 1
1843 else:
1844 high = mid - 1
1845 low *= 2
1847 # Now we can cycle through the production cycle until the product has
1848 # been produced.
1849 while True:
1850 max_time = production_times[low + 1]
1851 while max_time <= seg_start:
1852 low += 2
1853 if low >= low_end:
1854 low = 0
1855 seg_start = 0.0
1856 max_time = production_times[low + 1]
1858 unit_time = production_times[low]
1859 can_do: int = ceil(min(
1860 max_time - seg_start, remaining) / unit_time)
1861 duration = can_do * unit_time
1862 seg_start += duration
1863 start_time += duration
1864 remaining -= can_do
1865 if remaining <= 0:
1866 return float(start_time)
1869def store_instances(dest: str, instances: Iterable[Instance]) -> None:
1870 """
1871 Store an iterable of instances to the given directory.
1873 :param dest: the destination directory
1874 :param instances: the instances
1875 """
1876 dest_dir: Final[Path] = Path(dest)
1877 dest_dir.ensure_dir_exists()
1879 if not isinstance(instances, Iterable):
1880 raise type_error(instances, "instances", Iterable)
1881 names: Final[set[str]] = set()
1882 for i, instance in enumerate(instances):
1883 if not isinstance(instance, Instance):
1884 raise type_error(instance, f"instance[{i}]", Instance)
1885 name: str = instance.name
1886 if name in names:
1887 raise ValueError(
1888 f"Name {name!r} of instance {i} already occurred!")
1889 dest_file = dest_dir.resolve_inside(f"{name}.txt")
1890 if dest_file.exists():
1891 raise ValueError(f"File {dest_file!r} already exists, cannot "
1892 f"store {i}th instance {name!r}.")
1893 try:
1894 with dest_file.open_for_write() as stream:
1895 write_lines(to_stream(instance), stream)
1896 except OSError as ioe:
1897 raise ValueError(f"Error when writing instance {i} with name "
1898 f"{name!r} to file {dest_file!r}.") from ioe
1901def instance_sort_key(inst: Instance) -> str:
1902 """
1903 Get a sort key for instances.
1905 :param inst: the instance
1906 :return: the sort key
1907 """
1908 return inst.name
1911def load_instances(source: str) -> tuple[Instance, ...]:
1912 """
1913 Load the instances from a given irectory.
1915 :param source: the source directory
1916 :return: the tuple of instances
1918 >>> inst1 = Instance(
1919 ... name="test1", n_products=1, n_customers=1, n_stations=2,
1920 ... n_demands=1, time_end_warmup=10, time_end_measure=4000,
1921 ... routes=[[0, 1]],
1922 ... demands=[[0, 0, 0, 10, 20, 100]],
1923 ... warehous_at_t0=[0],
1924 ... station_product_unit_times=[[[10.0, 10000.0]],
1925 ... [[30.0, 10000.0]]])
1927 >>> inst2 = Instance(
1928 ... name="test2", n_products=2, n_customers=1, n_stations=2,
1929 ... n_demands=3, time_end_warmup=21, time_end_measure=10000,
1930 ... routes=[[0, 1], [1, 0]],
1931 ... demands=[[0, 0, 1, 10, 20, 90], [1, 0, 0, 5, 22, 200],
1932 ... [2, 0, 1, 7, 30, 200]],
1933 ... warehous_at_t0=[2, 1],
1934 ... station_product_unit_times=[[[10.0, 50.0, 15.0, 100.0],
1935 ... [ 5.0, 20.0, 7.0, 35.0, 4.0, 50.0]],
1936 ... [[ 5.0, 24.0, 7.0, 80.0],
1937 ... [ 3.0, 21.0, 6.0, 50.0,]]])
1939 >>> from pycommons.io.temp import temp_dir
1940 >>> with temp_dir() as td:
1941 ... store_instances(td, [inst2, inst1])
1942 ... res = load_instances(td)
1943 >>> res == (inst1, inst2)
1944 True
1945 """
1946 src: Final[Path] = directory_path(source)
1947 instances: Final[list[Instance]] = []
1948 for file in src.list_dir(files=True, directories=False):
1949 if file.endswith(".txt"):
1950 with file.open_for_read() as stream:
1951 instances.append(from_stream(stream))
1952 if list.__len__(instances) <= 0:
1953 raise ValueError(f"Found no instances in directory {src!r}.")
1954 instances.sort(key=instance_sort_key)
1955 return tuple(instances)