Efficient system matrix calculation for manufacturing systems

Conference Paper


  • Calculating the performance measures of a manufacturing system is of fundamental importance in many industrial engineering problems, particularly scheduling. Graph theory and max-plus algebra provide mathematical tools that aid in the analysis of these systems. The max-plus algebra representation of a system is represented by the system matrix A. It can be shown that A can be used to calculate different performance measurements such as makespan, critical path, cycle time, tardiness, lateness, etc. This study proposes an efficient algorithm to calculate A from the graph representation of the system. Element ij of A Matrix represents the delay between job j entering the system and job i completing. The algorithm uses Kahn’s algorithm [1] to topologically sort the nodes in the graph. Since we used Kahn’s algorithm, which is the most efficient know to do the sort, our algorithm is the most efficient way to calculate system matrix.
  • Authors

  • Bahalkeh, Esmaeil
  • Madraki, Golshan
  • Judd, Robert
  • Publication Date

  • 2015
  • Start Page

  • 1943
  • End Page

  • 1950