# Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm
## 1 Introduction
In the OSP, there is exactly one machine in each workstation, all jobs arrive at the beginning of the schedule, and each job must visit all workstations. The NP-hardness of the OSP with more than two machines is proven by [PERSON] and [PERSON] (2018) for the minimization of the makespan, and by [PERSON] and [PERSON] (2019) for the minimization of the total weighted completion time that is equivalent to MWFT when all jobs arrive at the beginning of the schedule. Despite this fact, small size instances can still be solved by generating optimal Pareto front solutions. Due to its relevance to many real-life applications, the OSP has received a lot of attention in the literature for the single-objective cases. However, the multi-objective OSP has received little attention in the literature. [PERSON] et al. (2019) studied the OSP with the objectives of minimizing total tardiness and mean completion time simultaneously. Based on a mixed-integer linear programming model, they proposed a fuzzy programming method for finding efficient solutions and compared it with a tabu search approach. Only one paper is found to deal with the makespan and total completion time minimization objectives by [PERSON] et al. (2019). Although they considered the minimization of the total machine idle time as well that objective is correlated with the minimization of the makespan. They proposed a particle swarm optimization approach for solving the problem. In the literature, more attention is given to the minimization of due date related objectives along with another completion time-based objective. [PERSON] et al. (2018) and [PERSON] and [PERSON] (2019) studied the OSP with the minimization of the total tardiness and the minimization of the makespan simultaneously. They proposedan ant colony optimization approach hybridized with simulated annealing and compared the results with the non-dominated sorting genetic algorithm (NSGA-II). Later, a hybrid immune algorithm is developed by [PERSON] et al. [PERSON] et al. (2018) for the total tardiness and the total completion time minimization objectives. In the literature of the special case of the MOSP in which each workstation contains identical parallel machines, different constructive heuristics are proposed for minimizing the makespan by [PERSON] and [PERSON] [PERSON] and [PERSON] (2015), [PERSON] and [PERSON] [PERSON] and [PERSON] (2016), and [PERSON] and [PERSON] (2017). Those heuristics are linear-time approximation algorithms that have proven bounds on their gaps from the optimal solution. [PERSON] et al. [PERSON] et al. (2018) provided a mixed integer linear programming (MILP) model and developed a hybrid memetic algorithm-simulated annealing approach for the objective of minimizing the total completion time. [PERSON] et al. [PERSON] et al. (2018) considered a special case in which there are job independent setup times and sequence-dependent job removal times. They developed a mathematical programming model and proposed a hybrid imperialist competitive algorithm. Later, a general case of the MOSP in which workstations may not have identical machines and jobs do not have to visit all workstations is studied by [PERSON] (2018). He developed an MILP model and proposed a scatter search with a path relinking approach that is shown to generate optimal or near optimal solutions for the objective of minimizing the makespan. Another closely related specialization of the MOSP is the proportionate multiprocessor open shop scheduling problem (PMOSP) in which the machines in each workstation are identical and the processing times on the workstations do not vary among jobs. Different metaheuristic approaches have been proposed in the literature for the objective of minimizing the makespan including genetic algorithm by [PERSON] (2018), tabu search by [PERSON] et al. [PERSON] et al. (2019), a hybrid particle swarm optimization-tabu search approach by [PERSON] (2018), and scatter search with a path relinking approach by [PERSON] (2018). For the objective of minimizing the total completion time, [PERSON] et al.