Application of Neural Networks to Scheduling Problem including Transportation Time

Qazi ShoebAhmad, Muhammad Haris KhanInternational Journal of Computer Applications 2012 · DOI

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.

Input data for a 3-job, 4-machine flowshop problem including transportation times.

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.

Pairwise completion times used to determine frequency scores for job sequencing.

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

Abstract

This paper presents an approach for finding an optimal schedule of n-jobs and m-machines flowshop scheduling problem involving transportation time between jobs by using neural networks. An algorithm has been given for finding the optimal sequence in scheduling problem without transportation time Here, this algorithm is applied when transportation times are involved between machines to find the optimal sequence.
BibTeX
@article{shoebahmad2012application,
  author = {Qazi ShoebAhmad and Muhammad Haris Khan},
  title = {{Application of Neural Networks to Scheduling Problem including Transportation Time}},
  journal = {International Journal of Computer Applications},
  year = {2012},
  doi = {10.5120/8560-2152},
}
Figure