Search

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.

This paper, inspired by a real production process of steel hardening, investigates a scheduling problem to minimize the idle energy consumption of machines. The energy minimization is achieved by switching a machine to some power-saving mode when it is idle. For the steel hardening process, the mode of the machine (i.e., furnace) can be associated with its inner temperature. Contrary to the recent methods, which consider only a small number of machine modes, the temperature in the furnace can be changed continuously, and so an infinite number of the power-saving modes must be considered to achieve the highest possible savings. To model the machine modes efficiently, we use the concept of the energy function, which was originally introduced in the domain of embedded systems but has yet to take roots in the domain of production research. The energy function is illustrated with several application examples from the literature. Afterward, it is integrated into a mathematical model of a scheduling problem with parallel identical machines and jobs characterized by release times, deadlines, and processing times. Numerical experiments show that the proposed model outperforms a reference model adapted from the literature., Comment: Accepted to 9th International Conference on Operations Research and Enterprise Systems (ICORES 2020)

In this paper, we investigate the use of deep learning for solving a classical NP-Hard single machine scheduling problem where the criterion is to minimize the total tardiness. Instead of designing an end-to-end machine learning model, we utilize well known decomposition of the problem and we enhance it with a data-driven approach. We have designed a regressor containing a deep neural network that learns and predicts the criterion of a given set of jobs. The network acts as a polynomial-time estimator of the criterion that is used in a single-pass scheduling algorithm based on Lawler's decomposition theorem. Essentially, the regressor guides the algorithm to select the best position for each job. The experimental results show that our data-driven approach can efficiently generalize information from the training phase to significantly larger instances (up to 350 jobs) where it achieves an optimality gap of about 0.5%, which is four times less than the gap of the state-of-the-art NBR heuristic.

This article presents a novel scheduling approach to minimise the energy consumption of a machine during its idle periods. In the scheduling domain, it is common to model the behaviour of the machine by defining a small set of machine modes, e.g. "on", "off" and "stand-by". Then the transitions between the modes are represented by a static transition graph. In this paper, we argue that this type of model might be too restrictive for some types of machines (e.g. the furnaces). For such machines, we propose to employ the complete time-domain dynamics and integrate it into an idle energy function. This way, the scheduling algorithm can exploit the full knowledge about the machine dynamics with minimised energy consumption encapsulated in this function. In this paper, we study a scheduling problem, where the tasks characterised by release times and deadlines are scheduled in the given order such that the idle energy consumption of the machine is minimised. We show that this problem can be solved in polynomial time whenever the idle energy function is concave. To highlight the practical applicability, we analyse a heat-intensive system employing a steel-hardening furnace. We derive an energy optimal control law, and the corresponding idle energy function, for the bilinear system model approximating the dynamics of the furnace (and possibly other heat-intensive systems). Further, we prove that the idle energy function is, indeed, concave in this case. Therefore, the proposed scheduling algorithm can be used. Numerical experiments show that by using our approach, combining both the optimal control and optimal scheduling, higher energy savings can be achieved, compared to the state-of-the-art scheduling approaches.

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.

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 \v{S}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., Comment: Journal paper published in IEEE Industrial Informatics

In this work, we consider a scheduling problem faced by production companies with large electricity consumption. Due to the contract with the electric utility, the production companies are obligated to comply with the total energy consumption limits in the specified time intervals (usually 15-minutes long), otherwise, the companies pay substantial penalty fees. Although it is possible to design production schedules that consider these limits as hard constraints, uncertainties occurring during the execution of the schedules are usually not taken into account. This may lead to situations in which the unexpected delays of the operations cause the violations of the energy consumption limits. Our goal is to design robust production schedules pro-actively guaranteeing that the energy consumption limits are not violated for the given set of uncertainty scenarios. We consider scheduling on one machine with release times of the operations and total tardiness as the objective function. To tackle this problem, we first propose a pseudo-polynomial algorithm for finding the optimal robust schedule for the given permutation of the operations. This algorithm is then utilised in three different algorithms for finding the optimal permutation: two exact (Branch-and-Bound and logic-based Benders decomposition) and one heuristic algorithm (tabu search). All the algorithms were experimentally evaluated on random instances with different sizes of the uncertainty scenarios set. Using the tabu search algorithm, we are able to solve large instances within one minute.

An acceptable response time of a server is an important aspect in many client-server applications; this is evident in situations in which the server is overloaded by many computationally intensive requests. In this work, we consider that the requests, or in this case tasks, generated by the clients are instances of optimization problems solved by anytime algorithms, i.e. the quality of the solution increases with the processing time of a task. These tasks are submitted to the server which schedules them to the available computational resources where the tasks are processed. To tackle the overload problem, we propose a scheduling algorithm which combines traditional scheduling approaches with a quality control heuristic which adjusts the requested quality of the solutions and thus changes the processing time of the tasks. Two efficient quality control heuristics are introduced: the first heuristic sets a global quality for all tasks, whereas the second heuristic sets the quality for each task independently. Moreover, in practice, the relationship between the processing time and the quality is not known a priori. Because it is crucial for scheduling algorithms to know at least the estimation of these relationships, we propose a general procedure for estimating these relationships using information obtained from the already executed tasks. Finally, the performance of the proposed scheduling algorithm is demonstrated on a real-world problem from the domain of personnel rostering with very good results.

Consumer-electronics systems are becoming increasingly complex as the number of integrated applications is growing. Some of these applications have real-time requirements, while other non-real-time applications only require good average performance. For cost-efficient design, contemporary platforms feature an increasing number of cores that share resources, such as memories and interconnects. However, resource sharing causes contention that must be resolved by a resource arbiter, such as Time-Division Multiplexing. A key challenge is to configure this arbiter to satisfy the bandwidth and latency requirements of the real-time applications, while maximizing the slack capacity to improve performance of their non-real-time counterparts. As this configuration problem is NP-hard, a sophisticated automated configuration method is required to avoid negatively impacting design time. The main contributions of this article are: (1) an optimal approach that takes an existing integer linear programming (ILP) model addressing the problem and wraps it in a branch-and-price framework to improve scalability. (2) A faster heuristic algorithm that typically provides near-optimal solutions. (3) An experimental evaluation that quantitatively compares the branch-and-price approach to the previously formulated ILP model and the proposed heuristic. (4) A case study of an HD video and graphics processing system that demonstrates the practical applicability of the approach.

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., Comment: Published in Journal of Parallel and Distributed Computing

In this paper, we study an NP-hard problem of a single machine scheduling minimizing the makespan, where the mixed-critical tasks with an uncertain processing time are scheduled. We show the derivation of F-shaped tasks from the probability distribution function of the processing time, then we study the structure of problems with two and three criticality levels for which we propose efficient exact algorithms and we present computational experiments for instances with up to 200 tasks. Moreover, we show that the considered problem is approximable within a constant multiplicative factor., Comment: 16 pages, 2 figures, 2 tables