1"""Module for Job Shop Scheduling Problem (JSSP)."""
2
3from collections import defaultdict
4from typing import Literal
5
6from qiskit.quantum_info import SparsePauliOp
7
8from qlauncher import models
9from qlauncher.base import Problem
10from qlauncher.hampy import Equation
11from qlauncher.problems.optimization.jssp_utils import HamPyScheduler, PyQuboScheduler
12
13
[docs]
14class JSSP(Problem):
15 """
16 Class for Job Shop Scheduling Problem.
17
18 This class represents Job Shop Scheduling Problem (JSSP) which is a combinatorial optimization problem that involves
19 scheduling a set of jobs on a set of machines. Each job consists of a sequence of operations that must be performed
20 on different machines. The objective is to find a schedule that minimizes the makespan, i.e., the total time required
21 to complete all jobs. The class contains an instance of the problem, so it can be passed into QLauncher.
22
23
24 Attributes:
25 max_time (int): The maximum time for the scheduling problem.
26 onehot (str): The one-hot encoding method to be used.
27 optimization_problem (bool): Flag indicating whether the problem is an optimization problem or a decision problem.
28 results (dict): Dictionary to store the results of the problem instance.
29
30 """
31
32 def __init__(
33 self,
34 max_time: int,
35 instance: dict[str, list[tuple[str, int]]],
36 instance_name: str = 'unnamed',
37 optimization_problem: bool = False,
38 ) -> None:
39 super().__init__(instance=instance, instance_name=instance_name)
40 self.max_time = max_time
41 self.optimization_problem = optimization_problem
42 self.variant: Literal['decision', 'optimization'] = 'optimization' if optimization_problem else 'decision'
43
44 @property
45 def setup(self) -> dict:
46 return {
47 'jobs': self.instance,
48 'max_time': self.max_time,
49 'optimization_problem': self.optimization_problem,
50 'instance_name': self.instance_name,
51 }
52
53 def _get_path(self) -> str:
54 return f'{self.name}@{self.instance_name}@{self.max_time}@{"optimization" if self.optimization_problem else "decision"}'
55
[docs]
56 @staticmethod
57 def from_preset(instance_name: Literal['default'], **kwargs) -> 'JSSP':
58 match instance_name:
59 case 'default':
60 max_time = 3
61 instance = {'cupcakes': [('mixer', 2), ('oven', 1)], 'smoothie': [('mixer', 1)], 'lasagna': [('oven', 2)]}
62 case _:
63 raise ValueError(f"Instance {instance_name} does not exist choose instance_name from the following: ('toy')")
64
65 return JSSP(max_time=max_time, instance=instance, instance_name=instance_name, **kwargs)
66
[docs]
67 @classmethod
68 def from_file(cls, path: str, **kwargs) -> 'JSSP':
69 job_dict = defaultdict(list)
70 with open(path, encoding='utf-8') as file_:
71 file_.readline()
72 for i, line in enumerate(file_):
73 lint = list(map(int, line.split()))
74 job_dict[i + 1] = list(
75 zip(
76 lint[::2], # machines
77 lint[1::2], # operation lengths
78 strict=False,
79 )
80 )
81 return JSSP(instance=job_dict, **kwargs)
82
[docs]
83 def to_bqm(
84 self,
85 lagrange_one_hot: float = 1,
86 lagrange_precedence: float = 2,
87 lagrange_share: float = 5,
88 ) -> models.BQM:
89 # Define the matrix Q used for QUBO
90 scheduler = PyQuboScheduler(self.instance, self.max_time)
91 result = scheduler.get_result(lagrange_one_hot, lagrange_precedence, lagrange_share)
92 if isinstance(result, SparsePauliOp):
93 raise TypeError
94 return models.BQM(result)
95
[docs]
96 def to_hamiltonian(
97 self,
98 lagrange_one_hot: float = 1,
99 lagrange_precedence: float = 2,
100 lagrange_share: float = 5,
101 onehot: Literal['exact', 'quadratic'] = 'exact',
102 ) -> models.Hamiltonian:
103 scheduler = HamPyScheduler(self.instance, self.max_time, onehot)
104 result = scheduler.get_result(lagrange_one_hot, lagrange_precedence, lagrange_share, self.variant)
105 if not isinstance(result, Equation):
106 raise TypeError
107 return models.Hamiltonian(result)
