Graph Representation of Scheduling Problems

In an S-graph, the nodes correspond to production tasks except terminal nodes which are to denote the final products. The S-graph arcs are classified into two classes the so-called recipe arcs and schedule arcs. It is noteworthy that recipe arcs are input to the scheduling problem, while schedule arcs result from the S-graph algorithm solution. 

Recipe arcs represent the preceding relationship among tasks. If a recipe arc leads from task ki to task kz means that task kz execution must start at least c k, kz) time units later than task k execution. Here, c(ki, kz) is the weight of the recipe arc (ki, kz). In case of problem initialization and that more than one equipment is suitable to perform a recipe arc (ki, kz) (i.e., execution of task represented by the origin node ki), the arc weight is the minimum processing time for task ki among the suitable equipment units. 

---