# Graph-Based Modeling in Shop Scheduling Problems: Review and Extensions
## 3 The Theory of Shop Scheduling Problems
### Shop Layouts
\begin{table}
\begin{tabular}{c c} \hline \hline
**Term** & **Description** \\ \hline Buffer & A waiting space for jobs between machines. Buffers avoids blocking situation \\ \hline Blocking & This situation occurs when a machine cannot release a job due to lack of buffer. It \\ halts further tasks until the buffer is restored \\ \hline Start Time (\(S_{ij}\)) & The time when job \(j\) starts being processed by machine \(i\). \\ \hline Processing Time (\(Pij\)) & is the time it takes for machine \(i\) to process job \(j\) \\ \hline Travel Time & The time for a job to be transferred from one machine to another \\ \hline Setup Time & The time required to prepare a system or machine for production \\ \hline Bottleneck & The process that directly limits production capacity, i.e., the critical path. \\ \hline Dispatching & Assigning resources to tasks, i.e., scheduling. \\ \hline Assembly & A product of combined components. \\ \hline Subassembly & A component that is built by combining several other components and used in a larger product. \\ \hline Precedence & Job \(j\) can only start processing after jobs in set s have been completed. \\ \hline Machine Eligibility & Machine \(i\) can only perform some subset of job \(j\)’s required processes. \\ \hline Machine Breakdown & Machines have non-continuous availability. \\ \hline Routing & Job \(j\)’s operations must be completed in a specific order. \\ \hline Incompatible jobs & Incompatible jobs cannot be processed by the same machine \\ \hline Waiting Time & This situation occurs when the buffer between machines is too small blocking may \\  & occur, so, upstream machines cannot release jobs. \\ \hline No-Wait & Consecutive operations of a job must be performed without wait-time on \\  & either machine. \\ \hline No-Idle & Machines must continuously process jobs without overlap or pause. \\ \hline Deadlock & This situation occurs when the order of operations creates a cycle, and the entire \\  & process stops under this situation. \\ \hline Preemption & Jobs can be interrupted while being processed on machines. They can then be \\  & resumed on the same machine or a new one. \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Common terminology in Manufacturing system and shop scheduling problems. single-stage layouts, and job shop, flow shop, and open shop systems are the classical multi-stage layouts. We utilized classical classifications and modern models as well as different scholars' literature review studies to propose our comprehensive classification of system layouts as it is represented in Figure 5. In addition to the classical layouts, we incorporated the modern complicated layouts such as mixed shop and just-in-time systems in our classification. These modern system layouts emerged during the recent decades to satisfy the needs of fast-growing manufacturing technology. In this section, the main properties of each layout are briefly explained. Reviewing this background is particularly important to understand how different types of graphs can be applied to address scheduling problems in different manufacturing structures.