Přemysl Šůcha

Marek Vlk, Premysl Sucha, Jaroslaw Rudy et al.

The food production industry, especially the meat production sector, faces many challenges that have even escalated due to the recent outbreak of the energy crisis in the European Union. Therefore, efficient use of input materials is an essential aspect affecting the profit of such companies. This paper addresses an optimization problem concerning the purchase and subsequent material processing we solved for a meat processing company. Unlike the majority of existing papers, we do not concentrate on how this problem concerns supply chain management, but we focus purely on the production stage. The problem involves the concept of alternative ways of material processing, stock of material with different expiration dates, and extra constraints widely neglected in the current literature, namely, the minimum order quantity and the minimum percentage in alternatives. We prove that each of these two constraints makes the problem \mbox{$\mathcal{NP}$-hard}, and hence we design a simple iterative approach based on integer linear programming that allows us to solve real-life instances even using an open-source integer linear programming solver. Another advantage of this approach is that it mitigates numerical issues, caused by the extensive range of data values, we experienced with a commercial solver. The results obtained using real data from the meat processing company showed that our algorithm can find the optimum solution in a few seconds for all considered use cases.

Michal Bouška, Přemysl Šůcha, Antonín Novák et al.

In this paper, we investigate the use of the deep learning method for solving a well-known NP-hard single machine scheduling problem with the objective of minimizing the total tardiness. We propose a deep neural network that acts as a polynomial-time estimator of the criterion value used in a single-pass scheduling algorithm based on Lawler's decomposition and symmetric decomposition proposed by Della Croce et al. Essentially, the neural network guides the algorithm by estimating the best splitting of the problem into subproblems. The paper also describes a new method for generating the training data set, which speeds up the training dataset generation and reduces the average optimality gap of solutions. The experimental results show that our machine learning-driven approach can efficiently generalize information from the training phase to significantly larger instances. Even though the instances used in the training phase have from 75 to 100 jobs, the average optimality gap on instances with up to 800 jobs is 0.26%, which is almost five times less than the gap of the state-of-the-art heuristic.

Nikolai Antonov, Prěmysl Šůcha, Mikoláš Janota et al.

Existing research on single-machine scheduling is largely focused on exact algorithms, which perform well on typical instances but can significantly deteriorate on certain regions of the problem space. In contrast, data-driven approaches provide strong and scalable performance when tailored to the structure of specific datasets. Leveraging this idea, we focus on a single-machine scheduling problem where each job is defined by its weight, duration, due date, and deadline, aiming to minimize the total weight of tardy jobs. We introduce a novel data-driven scheduling heuristic that combines machine learning with problem-specific characteristics, ensuring feasible solutions, which is a common challenge for ML-based algorithms. Experimental results demonstrate that our approach significantly outperforms the state-of-the-art in terms of optimality gap, number of optimal solutions, and adaptability across varied data scenarios, highlighting its flexibility for practical applications. In addition, we conduct a systematic exploration of ML models, addressing a common gap in similar studies by offering a detailed model selection process and providing insights into why the chosen model is the best fit.

Roman Václavík, Přemysl Šůcha, Zdeněk Hanzálek

The personnel scheduling problem is a well-known NP-hard combinatorial problem. Due to the complexity of this problem and the size of the real-world instances, it is not possible to use exact methods, and thus heuristics, meta-heuristics, or hyper-heuristics must be employed. The majority of heuristic approaches are based on iterative search, where the quality of intermediate solutions must be calculated. Unfortunately, this is computationally highly expensive because these problems have many constraints and some are very complex. In this study, we propose a machine learning technique as a tool to accelerate the evaluation phase in heuristic approaches. The solution is based on a simple classifier, which is able to determine whether the changed solution (more precisely, the changed part of the solution) is better than the original or not. This decision is made much faster than a standard cost-oriented evaluation process. However, the classification process cannot guarantee 100% correctness. Therefore, our approach, which is illustrated using a tabu search algorithm in this study, includes a filtering mechanism, where the classifier rejects the majority of the potentially bad solutions and the remaining solutions are then evaluated in a standard manner. We also show how the boosting algorithms can improve the quality of the final solution compared with a simple classifier. We verified our proposed approach and premises, based on standard and real-world benchmark instances, to demonstrate the significant speedup obtained with comparable solution quality.

Libor Bukata, Přemysl Šůcha, Zdeněk Hanzálek et al.

This study focuses on the energy optimization of industrial robotic cells, which is essential for sustainable production in the long term. A holistic approach that considers a robotic cell as a whole toward minimizing energy consumption is proposed. The mathematical model, which takes into account various robot speeds, positions, power-saving modes, and alternative orders of operations, can be transformed into a mixed-integer linear programming formulation that is, however, suitable only for small instances. To optimize complex robotic cells, a hybrid heuristic accelerated by using multicore processors and the Gurobi simplex method for piecewise linear convex functions is implemented. The experimental results showed that the heuristic solved 93 % of instances with a solution quality close to a proven lower bound. Moreover, compared with the existing works, which typically address problems with three to four robots, this study solved real-size problem instances with up to 12 robots and considered more optimization aspects. The proposed algorithms were also applied on an existing robotic cell in Škoda Auto. The outcomes, based on simulations and measurements, indicate that, compared with the previous state (at maximal robot speeds and without deeper power-saving modes), the energy consumption can be reduced by about 20 % merely by optimizing the robot speeds and applying power-saving modes. All the software and generated datasets used in this research are publicly available.

Libor Bukata, Premysl Sucha, Zdenek Hanzalek

In the paper, a parallel Tabu Search algorithm for the Resource Constrained Project Scheduling Problem is proposed. To deal with this NP-hard combinatorial problem many optimizations have been performed. For example, a resource evaluation algorithm is selected by a heuristic and an effective Tabu List was designed. In addition to that, a capacity-indexed resource evaluation algorithm was proposed and the GPU (Graphics Processing Unit) version uses a homogeneous model to reduce the required communication bandwidth. According to the experiments, the GPU version outperforms the optimized parallel CPU version with respect to the computational time and the quality of solutions. In comparison with other existing heuristics, the proposed solution often gives better quality solutions.