# Graph-Based Modeling in Shop Scheduling Problems: Review and Extensions
## 1 Introduction  
Graph theory is an important and practical division in mathematics. It is defined as the study of graphs which are a visual representation and a mathematical structure showing the relations between elements and/or features of a problem ([1]. Graphs have two major components: nodes (also known as vertices and points) and edges (also known as links, lines, arrows) connecting nodes together, dictating the relationship between nodes. Edges can be directed or undirected. If a node takes precedence over another node, then this relation is represented by a directed edge. otherwise, an undirected edge should be used connecting two symmetric nodes. Graph theory was first published in 1735 by [PERSON] with the solution of the Konigsberg bridge problem [2]. [PERSON] turned land masses into nodes and bridges into undirected edges, finding that his solution depended on a characteristic of the graph: the degrees of each node. Rather than simplifying this problem, [PERSON]'s method clarified the problem into only the necessary components and relationships for understanding and solving. Since 1735,graph theory has expanded vastly in both applications and complexity. Today, graph theory includes hundreds of different types of graphs, algorithms, heuristics, and accompanying mathematical structures. The major application of graph theory is to model a variety of problems across disciplines and industries in which networks exist including physics [3,4], computer science [5,6], social networks [7,8], political science [9], artificial intelligence [10], biology [11], electrical power systems [12, 13, 14], supply chain network [15,16], we well as global crisis research such as COVID-19 outbreak [17]. Manufacturing systems benefit greatly from graph theory because they are all, at a fundamental level, networks of assets processing materials, parts, and information [18]. With this knowledge, they can be converted into graphical models efficiently and then analyzed. Shop scheduling is a critical subsystem of control and planning process in manufacturing systems, and directly affects the system productivity. Shop scheduling problems have been profoundly studied within the past decades. Scheduling generally refers to the assignment of a set of jobs to a set of resources (usually machines) within the course of time. As the size of sets of jobs and machines gets larger, finding a feasible schedule becomes harder. The ultimate goal in a scheduling problem is to find an efficient schedule which yields optimal results for the designated system performance measure/s (objective/s) [19]. Despite the significantly increase in number of publications using graph-based models to address variety of manufacturing system problems and shop scheduling problems, the literature lacks a comprehensive review paper to systematically study the overview and the perspective of this research field. To address this gap, we surveyed those studied utilizing graph theory to model and/or solve different variations of shop scheduling problems in the domain of manufacturing systems. We focused on articles published in peer-reviewed academic journals from 2015 to 2020 and skip conference proceedings and workshop publications. To the best of our knowledge, this paper is the first comprehensive review paper targeting the intersectional of shop scheduling problem and graph theory research. To confirm this statement, an extended search on only review papers published in this fields has been implemented. We used the \"Advance Search\" tool of Google Scholar search engine and did not consider any time boundary for the search. Combination of different keywords were applied including: \"Graph\", \"Scheduling\", \"review\", \"survey\", \"manufacturing\", \"shop\", etc. The results of this search confirmed our statement: Table 1 summarizes and compares the closest review papers found in this specified search. As this indicates, none of these review papers are remotely comparable to our study in terms of scope, topics, contents, and the magnitude of the dataset.