# Graph-Based Modeling in Shop Scheduling Problems: Review and Extensions
## 7 Analysis and Discussion  
Beyond proposing a systematically data collection and categorization methodology, this paper seeks to provide meaningful insights while extracting and analyzing potential correlation among multiple categories and subcategories. Performing analysis on the dataset might have obstacles that could lead to misleading results. A challenge in analyzing our dataset is related to the size of some subcategories: Comparing to other survey studies in literature (reviewing other manufacturing/scheduling related topics), the size of our dataset is adequately large. However, since the mainstreams of our research (shop scheduling and graph theory) require detailed breakdown, some of the described micro categories have a few entries which can be problematic in terms of statistical analysis and comparisons. To resolve the insufficient data issue in some subcategories, the majority of our analysis has been done by grouping these subcategories under more general labels. For example, Permutation Flow Shop, Single Stage Flow Shop, Multi-Stage Flow Shop, and Flexible Flow Shop are all combined into a blanket Flow Shop. Also, it should be noted that a large proportion of our dataset features more than one of the several categorizations in each area. For example, one paper may discuss both 'Job Shop' and 'Flow Shop' while utilizing both 'Disjunctive' and 'Bipartite Graph' to model their problems. Our dataset shows that on average, more than one layout type was discussed in each paper. This means that when we look at the presence of a specific feature as a percent and compare it to other features in the same macro category, the sum of percentages might be greater than 100%. Despite this detracting factor, percentage presence is still a very useful tool in our analysis as it simplifies making comparisons especially between differently sized categories. Our analysis starts with interpreting the impact of the system layout on the choice of type of graphs to model the system (the overlap between macro categories of graph types and layouts) shown in Figure 28. Overall, undirected graphs are the least popular across all different type of systems. An observation in this figure is that un/directed graphs are used more in job shop systems than others, particularly flow shop systems. A possible reason for this observation is that job shop systems are generally more flexible than most flow shop systems; also, most of un/directed graphs can potentially feature more flexibility to model the system. Therefore, un/directed graphs might be a better modeling tool for job shop systems. This justification can become more valid when we look at the highest percentage of the application of directed graph in flow shop problems comparing to other systems: using obligatory oriented edges in a directed graph can make the directed graph a more precise tool to model flow shop systems with a predefined routing. After understanding the system and formally defining the problem using potential graph-based models, an appropriate method to solve the scheduling problem should be selected. Figure 29 summarizes the relationship between the usages of solution methods and types of graphs. Despite the dominant usage of approximate methods within our dataset, almost the same proportions of different types of graphs are observed in the subsets  
Figure 28: Overlap between Graph types and Shop types. of papers applying exact and approximate methods. This means that, excluding those solution methods requiring a particular graph structure (e.g., Ant colony graph which require disjunctive graph-Un/Directed), a variety of graph types can be used in problems which are solved by either exact or approximate methods. Finally, the selected model and solution method should be verified with a case study. The choice of case study (numerical example, benchmark problem, or a real case) is seemingly independent of the type of graph used, so an in-depth analysis is not necessary. The usage of benchmark problems dominates our dataset while real cases were rarely utilized.