TL;DR
This paper introduces a novel application of temporal difference learning (TD(λ)) combined with a time-delay neural network (TDNN) to tackle the complex problem of job-shop scheduling for NASA's space shuttle payload processing. The TDNN learns effective scheduling heuristics automatically from raw data, outperforming previous hand-engineered approaches and traditional iterative repair methods in terms of schedule quality and efficiency.
What Problem Does This Paper Address?
Manufacturing industries, particularly in complex domains like NASA's space shuttle payload processing, face the challenge of job-shop scheduling. This involves sequencing tasks with temporal and resource constraints to minimize the overall completion time (makespan). Existing methods often rely on hand-engineered features, which are time-consuming to develop and limit the system's adaptability. This paper aims to automate the learning of these crucial scheduling heuristics by leveraging neural networks, specifically the time-delay neural network (TDNN), to learn directly from raw input features.
Methods
The core of this paper lies in combining two key techniques:
- Temporal Difference Learning (TD(λ)): This reinforcement learning algorithm is used to learn an evaluation function that estimates the "value" of a given schedule state. The goal is to learn an optimal policy that leads to the best possible schedule.
- Time-Delay Neural Network (TDNN): This architecture is adapted for scheduling by treating a schedule as a sequence of "blocks." Each block represents a time interval where tasks and resource assignments remain constant. The TDNN uses "kernels" to scan these blocks and extract "hidden features" that capture important aspects of the schedule's structure. These features are then aggregated and fed into a larger network to predict the schedule's quality. This approach allows the network to learn position-independent features, meaning it can recognize patterns regardless of where they appear in the schedule.
Datasets
The authors constructed an artificial problem set based on specifications for the NASA SSPP problem. This dataset was divided into:
- 50 problems for final testing.
- 20 problems for validation testing.
- Three training sets of 10 problems each.
Key Insights and Ideas
- Automated Feature Engineering: The TDNN architecture significantly reduces the need for manual "feature-engineering," a major bottleneck in applying machine learning to new domains. The network learns relevant features directly from the raw schedule data.
- Adaptability to Irregular Schedules: The TDNN's ability to process sequences of varying lengths (due to irregular schedule durations) is crucial for real-world scheduling problems.
- Reinforcement Learning for Optimization: Applying TD(λ) to the iterative repair scheduling problem allows the system to learn a policy that not only finds feasible schedules but also optimizes for schedule quality (minimizing the resource dilation factor).
- Bridging the Gap to Industrial Applications: This work demonstrates that the success of reinforcement learning, as seen in games like backgammon, can be effectively translated to complex industrial problems like job-shop scheduling.
Key Results
- The TDNN-TD(λ) network achieved performance comparable to, and in some cases slightly better than, their previous system that relied on hand-engineered features.
- Both neural network approaches (TDNN and hand-engineered) significantly outperformed the best previous non-learning iterative repair scheduler in terms of schedule quality (lower resource dilation factor) and the number of search steps required.
- The learned neural networks found good solutions much more directly than simulated annealing methods, indicating the effectiveness of the learned evaluation functions.
- While the TDNN approach is slightly slower in terms of CPU time per repair, it achieves better overall schedule quality.
Limitations and Future Work
- CPU Time per Repair: The paper notes that the TDNN approach spends more CPU time selecting each repair, which reduces the immediate difference in performance compared to faster methods.
- Efficiency of Updates: The authors suggest that the major CPU cost of the TDNN is in breaking the schedule into blocks and convolving kernel networks. They propose that this can be made more efficient by taking advantage of the fact that each repair only changes parts of the schedule, meaning only parts of the neural network calculation need to be updated. This points towards future work in incremental updates for efficiency.
- Further Exploration of TDNN Variants: While the paper focuses on a specific TDNN modification, further exploration of different TDNN architectures and configurations could yield even better results.
Summary updated