Parser¶
The parser module contains functions to parse job shop scheduling instances from text files into NumPy arrays. The module also contains functions to convert the NumPy arrays.
Two commonly used formats for job shop scheduling instances are the standard format and the talliard format. The standard format is a text file with the following structure:
6 6
2 1 0 3 1 6 3 7 5 3 4 6
1 8 2 5 4 10 5 10 0 10 3 4
2 5 3 4 5 8 0 9 1 1 4 7
1 5 0 5 2 5 3 3 4 8 5 9
2 9 1 3 4 5 5 4 0 3 3 1
1 3 3 3 5 9 0 10 4 4 2 1
The exact format of talliard instances is explained in jsp_instance_utils.instance_parser.parse_jps_standard_specification().
The talliard format is a text file with the following structure:
6 6
1 3 6 7 3 6
8 5 10 10 10 4
5 4 8 9 1 7
5 5 5 3 8 9
9 3 5 4 3 1
3 3 9 10 4 1
3 1 2 4 6 5
2 3 5 6 1 4
3 4 6 1 2 5
2 1 3 4 5 6
3 2 5 6 1 4
2 4 6 1 5 3
The exact format of talliard instances is explained in jsp_instance_utils.instance_parser.parse_jps_taillard_specification().
- jsp_instance_utils.instance_parser.parse_jps_standard_specification(instance_path: ~pathlib.Path) -> (<class 'numpy.ndarray'>, <class 'numpy.ndarray'>)¶
- Note: the description of the specification indexes machines at 1. The instance .txt file indexes machines
with index 0. So ‘machine 1’ in the description is denoted as ‘0’ in the instance .txt file.
Description of the standard specification (src: http://jobshop.jjvh.nl/explanation.php)
On the first line are two numbers, the first is the number of jobs and the second the number of machines. Following there is a line for each job. The order for visiting the machines is presented together with the corresponding processing time. The numbering of the machines starts at 0.
For example an instance with only a single job on three machines where the processing time is 5 on machine 1, 6 on machine 2 and 7 on machine 3 and the order that the machines are to be visited by that job is 2,3,1. The instance would be presented as:
1 3 1 6 2 7 0 5
Explanation of the provided example
Notation: mi -> machine i t(mi) -> procession time of the corresponding operation on machine i
Annotated example:
1(jobs: j1) 3(machines: m1,m2,m3)
[j1:] 1(m2) 6(t(m2)) 2(m3) 7(t(m3)) 0(m1) 5(t(m1))
Order of j1: m2, m3, m4
- Notation:
m_i -> machine i t(m_i) -> procession time of the corresponding operation on machine i
output format
- [
[(m_0,t(m_0)), (m0,t(m0)), …], # job0 [(m_0,t(m_0)), (m0,t(m0)), …], # job1 …
]
- Parameters:
instance_path – path to the jsp instance
- Returns:
jsp as numpy array, standard style jsp numpy array
- jsp_instance_utils.instance_parser.parse_jps_taillard_specification(instance_path: ~pathlib.Path) -> (<class 'numpy.ndarray'>, <class 'numpy.ndarray'>)¶
Description of the Taillard specification (src: http://jobshop.jjvh.nl/explanation.php)
On the first line are two numbers, the first is the number of jobs and the second the number of machines. Following there are two matrices the first with a line for each job containing the processor times for each operation the second with the order for visiting the machines. The numbering of the machines starts at 1.
For example the same instance as above would be presented as:
1 3 6 7 5 2 3 1
Explanation of the provided example
Notation: mi -> machine i t(mi) -> procession time of the corresponding operation on machine i
[JPS size] 1(jobs: j1) 3(machines: m1,m2,m3)
[processing times] 6(t(m2)) 7(t(m3)) 5(t(m1))
[order machines] 2(m2) 3(m3) 1(m1)
- Parameters:
instance_path – path to the jsp instance
- Returns:
jsp as numpy array, Taillard style jsp numpy array