Data-driven Algorithm for Scheduling with Total Tardiness
This work addresses scheduling efficiency for operations research, offering a data-driven improvement over existing heuristics, though it is incremental as it builds on known decomposition methods.
The paper tackles the NP-hard single machine scheduling problem to minimize total tardiness by using a deep neural network as a regressor to guide a decomposition-based algorithm, achieving an optimality gap of about 0.5% on instances up to 350 jobs, which is four times better than the state-of-the-art heuristic.
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.