Coverage for moptipy / examples / jssp / ob_encoding.py: 60%
48 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2An implementation of the operation-based encoding for JSSPs.
41. Mitsuo Gen, Yasuhiro Tsujimura, and Erika Kubota. Solving Job-Shop
5 Scheduling Problems by Genetic Algorithm. In *Humans, Information and
6 Technology: Proceedings of the 1994 IEEE International Conference on
7 Systems, Man and Cybernetics,* October 2-5, 1994, San Antonio, TX, USA,
8 volume 2. Piscataway, NJ, USA: IEEE. ISBN: 0-7803-2129-4.
9 doi: https://doi.org/10.1109/ICSMC.1994.400072.
10 http://read.pudn.com/downloads151/doc/658565/00400072.pdf.
112. Christian Bierwirth. A Generalized Permutation Approach to Job Shop
12 Scheduling with Genetic Algorithms. *Operations-Research-Spektrum
13 (OR Spectrum)*, 17(2-3):87-92, June 1995.
14 doi: https://doi.org/10.1007/BF01719250.
15 https://www.researchgate.net/publication/240263036.
163. Christian Bierwirth, Dirk C. Mattfeld, and Herbert Kopfer. On Permutation
17 Representations for Scheduling Problems. In Hans-Michael Voigt, Werner
18 Ebeling, Ingo Rechenberg, and Hans-Paul Schwefel, editors, *Proceedings of
19 the 4th International Conference on Parallel Problem Solving from Nature
20 (PPSN IV),* September 22-24, 1996, Berlin, Germany, pages 310-318.
21 Volume 1141/1996 of Lecture Notes in Computer Science (LNCS), Berlin,
22 Germany: Springer-Verlag GmbH. ISBN: 3-540-61723-X.
23 doi: https://doi.org/10.1007/3-540-61723-X_995.
24 https://www.researchgate.net/publication/2753293.
254. Guoyong Shi, Hitoshi Iima, and Nobuo Sannomiya. New Encoding Scheme for
26 Solving Job Shop Problems by Genetic Algorithm. In *Proceedings of the 35th
27 IEEE Conference on Decision and Control (CDC'96),* December 11-13, 1996,
28 Kobe, Japan, volume 4, pages 4395-4400. Piscataway, NJ, USA: IEEE.
29 ISBN: 0-7803-3590-2. doi: https://doi.org/10.1109/CDC.1996.577484.
30 https://www.researchgate.net/publication/224238934.
31"""
32from typing import Final
34import numba # type: ignore
35import numpy as np
36from pycommons.types import type_error
38from moptipy.api.encoding import Encoding
39from moptipy.examples.jssp.instance import Instance
40from moptipy.utils.logger import KeyValueLogSection
41from moptipy.utils.nputils import (
42 KEY_NUMPY_TYPE,
43 int_range_to_dtype,
44 numpy_type_to_str,
45)
47#: the numpy data type for machine indices
48KEY_NUMPY_TYPE_MACHINE_IDX: Final[str] = f"{KEY_NUMPY_TYPE}MachineIdx"
49#: the numpy data type for job indices
50KEY_NUMPY_TYPE_JOB_IDX: Final[str] = f"{KEY_NUMPY_TYPE}JobIdx"
51#: the numpy data type for job times
52KEY_NUMPY_TYPE_JOB_TIME: Final[str] = f"{KEY_NUMPY_TYPE}JobTime"
55# start book
56@numba.njit(nogil=True, cache=True)
57def decode(x: np.ndarray, machine_idx: np.ndarray,
58 job_time: np.ndarray, job_idx: np.ndarray,
59 instance: np.ndarray, y: np.ndarray) -> None:
60 """
61 Map an operation-based encoded array to a Gantt chart.
63 :param x: the source array, i.e., multi-permutation
64 :param machine_idx: array of length `m` for machine indices
65 :param job_time: array of length `n` for job times
66 :param job_idx: length `n` array of current job operations
67 :param instance: the instance data matrix
68 :param y: the output array, i.e., the Gantt chart
69 """
70 machine_idx.fill(-1) # all machines start by having done no jobs
71 job_time.fill(0) # each job has initially consumed 0 time units
72 job_idx.fill(0) # each job starts at its first operation
74 for job in x: # iterate over multi-permutation
75 idx = job_idx[job] # get the current operation of the job
76 job_idx[job] = idx + 1 # and step it to the next operation
77 machine = instance[job, idx, 0] # get the machine id
78 start = job_time[job] # end time of previous operation of job
79 mi = machine_idx[machine] # get jobs finished on machine - 1
80 if mi >= 0: # we already have one job done?
81 start = max(start, y[machine, mi, 2]) # earliest start
82 mi += 1 # step the machine index
83 machine_idx[machine] = mi # step the machine index
84 end = start + instance[job, idx, 1] # compute end time
85 y[machine, mi, 0] = job # store job index
86 y[machine, mi, 1] = start # store start of job's operation
87 y[machine, mi, 2] = end # store end of job's operation
88 job_time[job] = end # time next operation of job can start
89 # end book
92# start book
93class OperationBasedEncoding(Encoding):
94 # reusable variables __machine_time, __job_time, and __job_idx are
95 # allocated in __init__; __matrix refers to instance data matrix
96 # end book
97 """
98 An operation-based encoding for the Job Shop Scheduling Problem (JSSP).
100 The operation-based encoding for the Job Shop Scheduling Problem (JSSP)
101 maps permutations with repetitions to Gantt charts.
102 In the operation-based encoding, the search space consists of permutations
103 with repetitions of length `n*m`, where `n` is the number of jobs in the
104 JSSP instance and `m` is the number of machines.
105 In such a permutation with repetitions, each of the job ids from `0..n-1`
106 occurs exactly `m` times.
107 In the encoding, the permutations are processed from beginning to end and
108 the jobs are assigned to machines in exactly the order in which they are
109 encountered. If a job is encountered for the first time, we place its
110 first operation onto the corresponding machine. If we encounter it for the
111 second time, its second operation is placed on its corresponding machine,
112 and so on.
113 """
115 def __init__(self, instance: Instance) -> None:
116 """
117 Instantiate the operation based encoding.
119 :param instance: the JSSP instance
120 """
121 if not isinstance(instance, Instance):
122 raise type_error(instance, "instance", Instance)
123 self.__machine_idx: Final[np.ndarray] = \
124 np.zeros(instance.machines,
125 int_range_to_dtype(-1, instance.jobs - 1))
126 self.__job_time: Final[np.ndarray] = \
127 np.zeros(instance.jobs,
128 int_range_to_dtype(0, instance.makespan_upper_bound))
129 self.__job_idx: Final[np.ndarray] = \
130 np.zeros(instance.jobs,
131 int_range_to_dtype(0, instance.machines - 1))
132 self.__instance: Final[Instance] = instance
134 def decode(self, x: np.ndarray, y: np.ndarray) -> None: # +book
135 """
136 Map an operation-based encoded array to a Gantt chart.
138 :param x: the array
139 :param y: the Gantt chart
140 """
141 decode(x, self.__machine_idx, self.__job_time, # +book
142 self.__job_idx, self.__instance, y) # +book
144 def __str__(self) -> str:
145 """
146 Get the name of this encoding.
148 :return: `"operation_based_encoding"`
149 :rtype: str
150 """
151 return "operation_based_encoding"
153 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
154 """
155 Log all parameters of this component as key-value pairs.
157 :param logger: the logger for the parameters
158 """
159 super().log_parameters_to(logger)
160 logger.key_value(KEY_NUMPY_TYPE_MACHINE_IDX,
161 numpy_type_to_str(self.__machine_idx.dtype))
162 logger.key_value(KEY_NUMPY_TYPE_JOB_IDX,
163 numpy_type_to_str(self.__job_idx.dtype))
164 logger.key_value(KEY_NUMPY_TYPE_JOB_TIME,
165 numpy_type_to_str(self.__job_time.dtype))