# Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm
## 1 Introduction  
Scheduling problems have several different structures and exist in a wide variety of real-life applications [1]. Due to their direct impact on the performance of industrial and service organizations, they are receiving an ever-growing interest from researchers to develop efficient algorithms [2, 3]. Despite the fact that most scheduling problems belong the NP-hard class, there is a demand for exact algorithms as they can be used for solving small to intermediate size instances. They also provide a basis for developing and assessing approximate algorithms. With their combinatorial nature, multi-objective scheduling problems represent a big challenge for exact algorithms development. The multiprocessor open shop scheduling problem (MOSP) is commonly encountered in maintenance and health care diagnostic systems. These systems are composed of a set of workstations that are available to process a set of jobs. Each workstation conducts a specific maintenance or diagnostic task that cannot be done on the other workstations in the system. Each workstation may contain more than one machine working in parallel. These machines are not necessarily identical, meaning that the processing timescan vary for the same job from one machine to another in a workstation. A job requires the processing on a subset of the workstations in the system with no specific visiting order. This paper is concerned with a dynamic case of the MOSP, denoted DMOSP, in which jobs continuously arrive to the system at pre-assigned arrival times during the execution period of a schedule. Each job has a priority represented by a numerical value that represents its level of importance with respect to the other jobs. In the studied DMOSP, it is assumed that a machine cannot process more than one job at a time and a job cannot be processed on more than one machine at a time. Once a job started its processing on a machine, it cannot be interrupted. Job release times and processing times on machines are deterministic and known a priori. In order to allow for rescheduling decisions at any point of time, we consider a situation in which some machines may not be ready for processing arriving jobs at the beginning of the schedule, yet their ready times are known a priori. This allows for a rolling horizon application of the developed algorithm. As pointed out by [PERSON] and [PERSON] (2019), more contributions are still needed for the dynamic rescheduling problems since they represent an important part of the integration of the fourth industrial revolution. Two performance measures are considered. The first measure is the maximum completion time for all jobs (makespan). The second measure is the mean weighted flow time (MWFT) of the jobs. The minimization of the makespan improves the utilization of the machines by reducing their total idle time; meanwhile, the minimization of the MWFT improves customer satisfaction level. Both objectives are considered simultaneously in this paper. Despite its common occurrence in real-life applications, the multi-objective DMOSP has rarely been addressed in the literature. The consideration of the aforementioned two objectives simultaneously is of a practical importance to the decision maker. In this paper, an a posteriori method is followed in which a set of Pareto front solutions will be presented to the decision maker to choose one to implement ([PERSON] et al., 2016). In relevance to the scheduling literature, the studied problem can be represented as \(O(R)|a_{m},r_{j}|C_{max},MWFT\) according to the three-field notation of [PERSON] et al. (2016) with the extension of [PERSON] et al. (1997). Here, \(a_{m}\) refers to the machines' ready times, \(r_{j}\) refers to the jobs' release times, \(C_{max}\) refers to the makespan minimization objective, and \(MWFT\) refers to the mean weighted flow time minimization objective. The NP-hardness of the DMOSP can be easily derived from the NP-hardness of its specialization--the traditional static, deterministic open shop scheduling problem (OSP).