Skip to Main Content
 

Global Search Box

 
 
 

ETD Abstract Container

Abstract Header

Efficient Algorithms for Calculating the System Matrix and the Kleene Star Operator for Systems Defined by Directed Acyclic Graphs over Dioids

Bahalkeh, Esmaeil
http://orcid.org/0000-0003-0288-0606
http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1440116216

Abstract Details

2015, Master of Science (MS), Ohio University, Industrial and Systems Engineering (Engineering and Technology).
Calculating the performance measures of a manufacturing system is of fundamental importance in many industrial engineering problems, particularly scheduling. The max-plus algebra representation of a system is given by the system matrix, shown by A, that can be used to calculate different performance measurements. This study proposes an efficient and structured algorithm to calculate A from the graph representation of the system. The proposed algorithm uses Kahn algorithm to topologically sort the nodes in the graph. In addition, using the same algorithm the Kleene star of a matrix can be computed in a slightly more efficient way. Kleene star contains longest path values between any two vertices. It is used to solve linear equations and also for performance measure purposes. Moreover, this study performs interval analysis on proposed algorithms. In interval system, unlike deterministic systems, input data of the system such as processing times are shown by intervals.
Robert Judd, Ph.D. (Advisor)
Gursel Suer, Ph.D. (Committee Chair)
Dusan Sormaz, Ph.D. (Committee Member)
Faizul Huq, Ph.D. (Committee Member)
63 p.
Computer Science; Engineering; Industrial Engineering; Mathematics; Operations Research
System Matrix; Kleene Star; Interval Analysis; Dioid; Max-plus Algebra; Directed Acyclic Graph; Manufacturing System; Scheduling

Recommended Citations

Citations

  • Bahalkeh, E. (2015). Efficient Algorithms for Calculating the System Matrix and the Kleene Star Operator for Systems Defined by Directed Acyclic Graphs over Dioids [Master's thesis, Ohio University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1440116216

    APA Style (7th edition)

  • Bahalkeh, Esmaeil. Efficient Algorithms for Calculating the System Matrix and the Kleene Star Operator for Systems Defined by Directed Acyclic Graphs over Dioids. 2015. Ohio University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1440116216.

    MLA Style (8th edition)

  • Bahalkeh, Esmaeil. "Efficient Algorithms for Calculating the System Matrix and the Kleene Star Operator for Systems Defined by Directed Acyclic Graphs over Dioids." Master's thesis, Ohio University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1440116216

    Chicago Manual of Style (17th edition)

ohiou1440116216
867
© 2015, all rights reserved.
This open access ETD is published by Ohio University and OhioLINK.