# Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
## 1 Introduction
Among classical exact algorithms for FSSP, one can name approaches like Branch and Bound (B&B) [19] and Mixed-Integer Linear Programming (MILP) formulations [20]. Heuristic methods include both simpler greedy- or rule-based algorithms [21] and dozens of different metaheuristic algorithms [6,22,23]. Other modeling and solving techniques include the use of fuzzy set theory to represent uncertain data [24] or speeding up computation by the use of parallel computing [25,26]. As reported in of the recent reviews on non-permutation FSSP [2], Genetic Algorithm (GA), Tabu Search (TS), Simulated Annealing, and Ant Colony Optimization are the most popular metaheuristic algorithms for FSSP. As noted earlier, GA has been used recently to solve many multi-criteria variants FSSP. However, the algorithm is also well-suited for a single-objective FSSP. For example, in [27], GA was used to solve a variant of a hybrid FSSP with unrelated machines, machine eligibility, and total tardiness minimization. The authors incorporated a new decoding method tuned for the specific objective function considered. The resulting algorithm proved to be competitive in numerical experiments. The authors in [28] considered a permutational FSSP with flow time minimization. A Biased Random-Key Genetic Algorithm was proposed, introducing a new feature called shaking. Authors compared the results obtained by their algorithms with an Iterated Greedy Search, an Iterated Local Search, and a commercial solver. Variants of the proposed algorithm outperformed the competition, especially for larger instances. Despite a large variety of extensions, the existing variants of FSSP are often insufficient in practice, when considering problems with machines that have unusual characteristics. Our motivation and an example of such problem is the concreting process, where one of the tasks performed on the site is concrete mix pouring. The concrete mixer needs to load the next batch of the mixture before proceeding with the next site. Moreover, the mixture has to be mixed for appropriate time before pouring--too long or too short mixing can affect the properties of the mixture or even damage the vehicle. However, the mixing should not be included in task time because work on the site can proceed as soon as the concrete mixer leaves the site. In scheduling, we can describe this as an additional dependency between starting or completion times of operations within a single machine (the concrete mixer in our case). As a result, additional gaps of minimum and maximum allowed lengths are inserted into the schedule. We will refer to such restrictions as _time couplings_ and to FSSP with those restrictions as Flow Shop Scheduling Problem with Time Couplings (or FSSP-TC). The minimal waiting time needed for the concrete mixing can be modeled as a setup time [22], but this does not model the maximal waiting time. Other similar time constraints found in the literature include a classic no-idle [29; 30], where each machine, once processing operations are started, cannot be idle until all its operations are completed. Setups and no-idle constraints together were considered in [31], where subsequent operations or setups must start immediately after previous ones have completed. The authors proposed an MILP formulation as well as several versions of a heuristic based on the Beam Search approach. Similarly to no-idle, a no-wait constraint describes a requirement whose next operation in a job has to be started directly after completing the previous one. An example of such constraint for FSSP was considered in [32] and solved through various local-search metaheuristics. In [33], the authors proposed an application of genetic operators to an Ant Colony Optimization algorithm for the same variant of FSSP. The described algorithm was applied to the 192 benchmark instances from literature. Results were compared with an Adaptive Learning Approach and Genetic Heuristic algorithm.