# Graph-Based Modeling in Shop Scheduling Problems: Review and Extensions
## 8 Summary of Our Results  
In this section, a summary of our results will be presented and the interpretation of these results and future research directions are discussed in the next section, Conclusion. Our dataset contains 143 academic peer-reviewed journal papers published from 2015 to 2020 targeting the intersection of shop scheduling and graph theory research. Given the size and scope of the literature, focusing on relevant publications within the recent years could offer interesting insights to coincide with the current trends of the field. Next, our paper offered a brief analysis over the metadata (e.g., journals, publishers, years, etc.) of the collected references (Section 2). We proposed a novel subjective measurement to evaluate the quality of the journals in our dataset. The three subjective categories over the quality of the target journals are Premier, Major, and Others. This procedure and categorization have not been observed in any previous review papers. About 70% of our dataset had been published by either 'Premier' or 'Major' journals which confirm the validity of the references used in this survey (Figure 4). Then, comprehensive categorizations over system layouts, scheduling problem, scheduling solutions methods, different type of graphs were proposed in Sections 3-5. The classification of graph-based models applied in shop scheduling problems in Figure 8 is novel and created from scratch in this study. The macro categories include Directed, Undirected, and Un/Directed graphs categories. The latest category refers to those graphs with both directed and undirected edges at the same time, or those graphs that can have either all directed or undirected edges. The basic concepts of all these graph types and their applications to the shop scheduling problems were described in Section 5. The statistical analyses over individual categories and across multiple categories were performed in Sections 6 and 7. The overview of the full dataset (in Section 6) shows that more than half of the graphs (54%) used in our dataset are in Un/Directed category; while \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multicolumn{1}{c}{**Reference**} & \multicolumn{1}{c}{**Graph Type**} & \multicolumn{1}{c}{**Metric**} & \multicolumn{1}{c}{**Metric**} & \multicolumn{1}{c}{**Metric**} & \multicolumn{1}{c}{**Metric**} & \multicolumn{1}{c}{**Metric**} & \multicolumn{1}{c}{**Metric**} & \multicolumn{1}{c}{**Metric**} \\ \hline
[31] & ([PERSON] et al., 2018) & Disjunctive graph & 3 & 1 & 1 & 8 & 1 & 2 \\ \hline
[179] & ([PERSON] et al., 2020) & Petri-net & 10 & 1 & 2 & 11 & 2 & 2 \\ \hline
[218] & ([PERSON] and [PERSON], 2018) &
\begin{tabular}{c} Multiple graphs: \\ AND-OR graph \& \\ disjunctive graph \\ \end{tabular} & 2 & 2 & 1 & 7 & 1 & 1 \\ \hline
[69] & ([PERSON] and [PERSON], 2015) & DAG & 4 & 1 & 1 & 5,6 & 1 & 2 \\ \hline
[213] & ([PERSON] et al., 2017) & Disjunctive graph & 2 & 1 & 2 & 11 & 1,2 & 2 \\ \hline
[199] & ([PERSON] and [PERSON], 2016) & Disjunctive graph & 2 & 1 & 1 & 5 & 1 & 2 \\ \hline
[152] & ([PERSON] et al., 2017) & Game tree & 3 & 2 & 2 & 11 & 3 & 2 \\ \hline
[180] & ([PERSON] et al., 2020) & Precedence graph & 3 & 1 & 1 & 2,5,9,11 & 1,3 & 2 \\ \hline
[70] & ([PERSON] et al., 2020) & B\&B tree & 4 & 1 & 1 & 1 & 1 & 2 \\ \hline
[145] & ([PERSON] et al., 2020) & Tree & 3 & 2 & 2 & 6 & 2 & 2 \\ \hline
[200] & ([PERSON] et al., 2016b) & Disjunctive graph & 3 & 1 & 1 & 6,8 & 1 & 2 \\ \hline
[216] & ([PERSON] and [PERSON], 2018) & Disjunctive graph & 3 & 1 & 1 & 11 & 1 & 2 \\ \hline
[52] & ([PERSON] et al., 2017) & Ant colony graph & 3 & 1 & 1 & 2,7 & 1 & 2 \\ \hline
[124] & ([PERSON] et al., 2015) & DAG & 3 & 1 & 1 & 5,8 & 1 & 2 \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Properties of the problems in the top 10% most cited papers. only 14% are undirected graphs which reveals a gap of literature to applied graphs such as Social Network, MRFs, etc. In our dataset, 56% of the total problems addressed a type of job shop systems.