# Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
## 6 Conclusions and Future Work  
In this paper, we considered the non-permutation Flow Shop Scheduling Problem with Time Couplings and makespan criterion, based on a real-life concreting process in industry. We presented a mathematical model and formulated several problem properties based on the graph representation, including the computation of the goal function and its complexity. More importantly, we used the concept of L- and R-blocks to introduce and prove an elimination property. The elimination property allowed for defining a new type of neighborhood, which is smaller than the regular swap neighborhood and contains more promising solutions than the adjacent swap neighborhood. This means that this elimination method can be easily used with a wide class of local-search metaheuristics, which  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{\(n\times m\)} & \multirow{2}{*}{\(|\mathcal{O}|\)} & \multicolumn{6}{c}{\(PRD\) [\%]} \\ \cline{3-6}  & & **TS** & **TS** & **TS** & **GA** & \(T\) [s] \\  & & **(Block)** & **(Adjacent)** & **(Swap)** & & \\ \hline
20 \(\times\) 5 & 100 & 0.52 & 12.04 & 12.02 & 20.95 & 0.00 \\
20 \(\times\) 10 & 200 & 0.00 \({}^{\dagger}\) & 15.29 & 18.58 & 26.49 & 0.00 \\
20 \(\times\) 20 & 400 & 0.00 \({}^{\  
are commonly used to solve large scheduling problems. Examples besides Tabu Search include Simulated Annealing and Genetic Algorithms (which often uses neighborhoods to implement mutations). Neighborhoods can be also introduced into other metaheuristics (e.g., Artificial Bee Colony). We proposed three solving methods: an exact Branch and Bound approach as well as Tabu Search and Genetic Algorithm metaheuristics. Computer experiments on Taillard instances showed low (under 2.3% for smaller instances) values of deviation from the optimum for the Tabu Search approach and a high influence of processing and machine idle times on running time of the Branch and Bound method. Furthermore, the results showed the Tabu Search method with a neighborhood employing the proposed block property outperforms the two non-block neighborhoods and the Genetic Algorithm in solution quality and convergence speed, allowing for obtaining high-quality solutions in seconds. In practice, tighter schedules obtained using our Tabu Search could allow for less costs and less waste, at the same time ensuring that the equipment is properly used. It is especially important in the context of the concreting process, as incorrect mixing times can lead to potential equipment damage or poor concrete quality. In future research, the proposed approach can be extended to formulate properties for other scheduling problems with time couplings. In particular, both the Job Shop Scheduling Problem and the permutation variant of the Flow Shop Scheduling Problem seem promising, as those two problems are commonly considered in practice. Secondly, the solving method itself can be upgraded. The Tabu Search algorithm we presented in this paper was meant mainly to illustrate the viability and benefits of our approach and can be further improved or interchanged entirely for a different metaheuristic. For example, a promising research direction would be to investigate a procedure for a fast computation of the goal function (via a dedicated accelerator) or a fast neighborhood browsing (via parallel computing) in which both can be used with virtually any underlying local-search based algorithm. These and other improvements would result in a state-of-the-art method, viable for commercial use. Conceptualization, R.I. and J.R.; formal analysis: A.G.; methodology, R.I. and J.R.; software, R.I. and J.R; validation, A.G.; investigation, R.I.; resources, R.I., J.R. and A.G.; data curation, R.I., J.R. and A.G.; writing--original draft preparation, R.I., J.R. and A.G.; writing--review and editing, R.I., J.R. and A.G.; visualization, R.I., J.R.; supervision, J.R.; funding acquisition, R.I. and A.G. All authors have read and agreed to the published version of the manuscript.