Application of Neural Networks to Scheduling Problem including Transportation Time
Abstract
This paper explores an optimized approach for the $n$-job, $m$-machine flowshop scheduling problem, specifically incorporating variable transportation times between machines. By leveraging a pairwise comparison heuristic inspired by neural network logic, the authors propose an algorithm that efficiently determines an optimal job sequence to minimize total completion time (makespan). The method is validated through a numerical example involving three jobs and four machines, demonstrating its potential to reduce computational complexity from factorial to polynomial time.
Introduction
In industrial manufacturing, flowshop scheduling is a critical task that involves determining the processing order of $n$ jobs across a sequence of $m$ machines. The primary objective is typically to minimize the makespan—the total time required to complete all jobs. While traditional models often assume instantaneous movement between machines, real-world scenarios involve significant transportation lags due to loading, transit, and unloading. These lags can drastically alter the optimal schedule. Given that flowshop scheduling is NP-hard, finding an exact solution for large-scale problems is computationally prohibitive. This paper presents a heuristic approach that accounts for these transit times using a competitive neural logic framework.
Methodology
The proposed algorithm utilizes a Pairwise Comparison Heuristic. The process begins with a data matrix containing processing times ($p_{ij}$) for each job $i$ on machine $j$, and transportation times ($t_{i(j, j+1)}$) between consecutive machines.
The core logic involves evaluating every possible pair of jobs $(i, j)$. For each pair, the algorithm calculates the partial makespan for the sequence $i \rightarrow j$ and compares it to the sequence $j \rightarrow i$. If sequence $i \rightarrow j$ results in a shorter completion time, Job $i$ is assigned a frequency value of 1, while Job $j$ receives 0. This competitive scoring mimics the behavior of certain neural network architectures where nodes compete to represent the optimal state. After all $n(n-1)$ pairs are evaluated, jobs are ranked based on their total frequency scores. In cases of tied scores, a secondary criterion—minimizing machine idleness—is applied to break the tie.
Key Results
The algorithm was tested on a constructed example with 3 jobs and 4 machines. The pairwise evaluations provided the necessary data to rank the jobs based on their relative efficiency in sequence.
As shown in the results, the sequence (1, 2) had a completion time of 90, whereas (2, 1) took 96. Consequently, Job 1 gained a point over Job 2. Following all comparisons, Job 1 achieved a total frequency of 2, Job 2 a frequency of 1, and Job 3 a frequency of 0. This led to the optimal sequence 1-2-3, which produced a total makespan of 112 units. By reducing the search space from $n!$ to $n^2$, the heuristic offers a significant computational advantage for larger industrial applications.
Conclusion
The integration of transportation time into flowshop scheduling models provides a more realistic framework for industrial planning. The pairwise comparison heuristic successfully identifies near-optimal sequences with reduced computational overhead. Future research should focus on benchmarking this approach against established heuristics like NEH on larger datasets and incorporating dynamic variables such as stochastic processing times or real-time transit delays.
Summary updated