1""" Module for Job Shop Scheduling Problem (JSSP)."""
2from collections import defaultdict
3from typing import Dict, List, Literal, Tuple
4try:
5 from quantum_launcher.problems.problem_formulations.jssp.qiskit_scheduler import get_jss_hamiltonian
6except ModuleNotFoundError:
7 pass
8from quantum_launcher.base import Problem
9
10
[docs]
11class JSSP(Problem):
12 """
13 Class for Job Shop Scheduling Problem.
14
15 This class represents Job Shop Scheduling Problem (JSSP) which is a combinatorial optimization problem that involves
16 scheduling a set of jobs on a set of machines. Each job consists of a sequence of operations that must be performed
17 on different machines. The objective is to find a schedule that minimizes the makespan, i.e., the total time required
18 to complete all jobs. The class contains an instance of the problem, so it can be passed into Quantum Launcher.
19
20
21 Attributes:
22 max_time (int): The maximum time for the scheduling problem.
23 onehot (str): The one-hot encoding method to be used.
24 optimization_problem (bool): Flag indicating whether the problem is an optimization problem or a decision problem.
25 results (dict): Dictionary to store the results of the problem instance.
26
27 """
28
29 def __init__(self, max_time: int, instance: Dict[str, List[Tuple[str, int]]],
30 instance_name: str = 'unnamed', optimization_problem: bool = False, onehot: Literal['exact', 'quadratic'] = 'exact') -> None:
31 super().__init__(instance=instance, instance_name=instance_name)
32 self.max_time = max_time
33 self.onehot = onehot
34 self.optimization_problem = optimization_problem
35
36 self.h_d, self.h_o, self.h_pos_by_label, self.h_label_by_pos = get_jss_hamiltonian(self.instance, max_time,
37 onehot)
38
39 self.results = {'instance_name': instance_name,
40 'max_time': max_time,
41 'onehot': onehot,
42 'H_pos_by_label': self.h_pos_by_label,
43 'H_label_by_pos': self.h_label_by_pos}
44
45 self.variant = 'optimization' if optimization_problem else 'decision'
46
47 @property
48 def setup(self) -> dict:
49 return {
50 'max_time': self.max_time,
51 'onehot': self.onehot,
52 'optimization_problem': self.optimization_problem,
53 'instance_name': self.instance_name
54 }
55
56 def _get_path(self) -> str:
57 return f'{self.name}@{self.instance_name}@{self.max_time}@{"optimization" if self.optimization_problem else "decision"}@{self.onehot}'
58
[docs]
59 @staticmethod
60 def from_preset(instance_name: str, **kwargs) -> "JSSP":
61 match instance_name:
62 case 'toy':
63 max_time = 3
64 instance = {"cupcakes": [("mixer", 2), ("oven", 1)],
65 "smoothie": [("mixer", 1)],
66 "lasagna": [("oven", 2)]}
67 case _:
68 raise ValueError(f"Instance {instance_name} does not exist choose instance_name from the following: ('toy')")
69
70 return JSSP(max_time=max_time, instance=instance, instance_name=instance_name, **kwargs)
71
[docs]
72 @classmethod
73 def from_file(cls, path: str, **kwargs) -> "JSSP":
74 job_dict = defaultdict(list)
75 with open(path, 'r', encoding='utf-8') as file_:
76 file_.readline()
77 for i, line in enumerate(file_):
78 lint = list(map(int, line.split()))
79 job_dict[i + 1] = [x for x in
80 zip(lint[::2], # machines
81 lint[1::2] # operation lengths
82 )]
83 return JSSP(instance=job_dict, **kwargs)
