# Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
## 1 Introduction  
The Flow Shop Scheduling Problem (or FSSP), formulated in both permutation and non-permutation variants [1], remains one of the most well-known optimization problems in operations research. It is widely used for modeling theoretical and real-life problems in manufacturing and production planning [2]. In this problem, a number of jobs and machines are given. The objective is to determine a production schedule such that each job is processed on each machine in the same fixed order (given by the technological process) and the given criterion, usually the completion time of all jobs, is minimized. In the permutation variant, each machine processes jobs in the same order, while non-permutation variant has no such restriction. Due to its practical applications, a great variety of FSSP variants and extensions have been considered over the years. For example, the authors of [3] considered a cyclic variant, where the initial set of jobs (called Minimal Part Set) is scheduled repeatedly in a cycle with the goal to minimize the cycle time. Another cyclic variant of FSSP, where machines are replaced by single-operator robotic cells, was researched in [4]. Due to the nature of real-life production processes, another common FSSP variant is based on consideration of uncertainty in the data, as shown in [5]. Another FSSP variant, represented by both the previous paper and [6], is multi-criteria FSSP, where two or more optimization criteria are considered simultaneously and the goal is to obtain the Pareto front. For this category of problems, Genetic Algorithms are especially popular recently. For example, the authors in [7] considered a hybrid variant of FSSP, where energy consumption was chosen as an additional objective. Due to a complex nature of the problem, the mixed integer formulationwas solved using a modified NSGA-II (Non-dominated Sorting Genetic Algorithm) [8]. A Genetic Algorithm (GA) utilizing the concept of a relative entropy of fuzzy sets was proposed in [9]. To evaluate a Pareto front, the front is first mapped to a fuzzy set and then the relational entropy coefficient is used to measure the similarity to an ideal solution. In experiments for 4, 7, and 10 different criteria, the approach was shown to outperform multiple existing algorithms, including the popular NSGA-III [8,10]. GA approaches are commonly used for solving a wide range of problems ranging from multi-objective train scheduling [11] to continuous process improvement [12]. FSSP is an NP-hard problem and thus considered difficult even for small instances. As a result, there is a great number of different approaches for tackling FSSP. Machine Learning (ML) is a very popular topic nowadays. The methodology is especially well-suited for data-driven problems, with a large volume of noisy information available. However, purely ML-based end-to-end solving methods are usually inferior in the context of classical scheduling and routing problems. For example, the authors in [13] solved Travelling Salesman Problem (TSP) with the Pointer Networks that output a permutation of vertices. However, the approach was strictly worse than the best classical TSP solvers, such as Concorde [14]. Many other authors tried solving TSP using ML methods [15,16], but none succeeded in outperforming the state-of-art. In [17], a more general, data-driven approximation for solving NP-hard problems was presented. The methodology was tested on the Quadratic Assignment Problem. The method was outperformed by a general-purpose commercial solver. On the other hand, ML can also be used as a part of a larger solving algorithm. In a proof-of-concept work [18], the authors proposed an input-size agnostic deep neural network, integrated with [PERSON]'s decomposition for solving single machine total tardiness problem. The results showed that the algorithm outperformed the former state-of-the-art heuristics and the method can potentially be applied for other problems.