# Graph-Based Modeling in Shop Scheduling Problems: Review and Extensions
## 2 Materials and Methods  
In this paper, a systematic search process was conducted to assess the body of literature on the application of the graph theory in shop scheduling problems. This systematic literature review was implemented through an iterative process of defining relevant and appropriate keywords, reviewing the search results in the literature, reference chasing, and categorizing the final search results. The details of our research process are as follows: \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Model**} & **Review** & **Author-Year of** & **Number of** & **The Time Period of** & **Targeted Topics** & **Additional Description** \\ \cline{3-8}  & **Paper** & **Publication** & **Reviewed Papers** & **Reviewed Papers** & **Targeted Topics** & **Only DAG** \\ \hline \multirow{4}{*}{**Model**} & **Paper** & **[PERSON] et al.** (2015)** & 14 & All before 1998 & The processor scheduling algorithms, DAG DAG, Genetic Algorithm & Only DAG \\  & **Paper** & **[PERSON] \& [PERSON]** (2015)** & 19 & 1979–2014 & Reviewing 9 graph-based systems, e.g., Ant colony, AND/OR, Social Networks, etc. & Investigating applications to manufacturing systems- Not scheduling problems \\  & **Paper** & **[PERSON] \&**[PERSON]** (2015)** & 56 & 1990–2020 & The processor scheduling algorithms, DAG & Only DAG \\  & **Paper** & **[PERSON] \&**[PERSON]** (2020)** & 56 & 1990–2020 & Precedence graphs, unrelated parallel machines scheduling graph & Only Precedence graph \\  & **Paper** & **[PERSON]** (2020)** & 26 & All before 1999 & Unrelated parallel machines scheduling graph & Only Petri-net \\  & **Paper** & **[PERSON]** (2020)** & 20 & 1989–2005 & Petri nets, shop scheduling problem & Only Petri-net Flexible manufacturing systems, Multi-Criteria Decision Making, Petri Net, etc. & \multirow{2}{*}{Only Petri-net} \\  & **Paper** & **[PERSON]** (2020)** & 56 & No time limit & Flow shop- Schematic representations & Not necessarily graph \\  & **Paper** & **[PERSON]** (2020)** & 88 & No time limit & Mixed Graph & Only mathematical theory of mixed graph coloring \\  & **Our paper** & **Our paper** & **Our paper** & **[PERSON]** (2021)** & **[PERSON]** (2020)** & **Graph theory, shop scheduling problem & All types of applied graphs \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparing the existing review papers in the literature with this study. To compile our dataset, we used the most common search engines \"Google\" and \"Google-Scholar\". We confined our search exclusively to peer-reviewed academic journal publication. In our systematic search process, we used the combination of relevant keywords and selected papers which are pertinent to the modeling of manufacturing systems and shop scheduling problems using graph-based models and the application of graph theory in this context. This combination of keywords must include at least one keyword related to manufacturing system and one related to graph-theory. For instance, \"graph+ shop+ scheduling\" was one of the most successful combinations of keywords in our trials. Also, to have a more in-depth and broader search results, we used several well-known publishers' databases such as Elsevier Springer, Taylor & Francis, Emerald Publishing, Wiley Online Library, INFORMS, IEEE Digital Library, etc. This initial search resulted in finding 175 journal articles. Then, the contents of each article were evaluated by three independent researchers and further reference chasing was done. This process has been implemented iteratively until we found a satisfactory number of references. After the final round of data filtering, eventually, 143 papers were selected whose contents were completely in the scope of this study. The finally selected papers were classified and sorted based on the quality of journal and the year of publication. Figure 1 summarizes the steps of our systematic search process to carry out the literature review in the domain of graph theory and shop scheduling problems.