Lesson plan
Disjunctive graph
In the mathematical modeling of job shop scheduling problems, disjunctive graphs are a way of modeling a system of tasks to be scheduled and timing constraints that must be respected by the schedule. They are mixed graphs, in which vertices (representing tasks to be performed) may be connected by both directed and undirected edges (representing timing constraints between tasks). The two types of edges represent constraints of two different types: *If one task x must be performed earlier than a second task y, this constraint is represented by a directed edge from x to y. *If, on the other hand, two tasks x and y can be performed in either order, but not simultaneously (perhaps because they both demand the use of the same equipment or other resource), this non-simultaneity constraint is represented by an undirected edge connecting x and y. Pairs of tasks that have no constraint on their ordering – they can be performed in either order or even simultaneously – are disconnected from each other in the graph. A valid schedule for the disjunctive graph may be obtained by finding an acyclic orientation of the undirected edges – that is, deciding for each pair of non-simultaneous tasks which is to be first, without introducing any circular dependencies – and then ordering the resulting directed acyclic graph.…
Article summary
In the mathematical modeling of job shop scheduling problems, disjunctive graphs are a way of modeling a system of tasks to be scheduled and timing constraints that must be respected by the schedule. They are mixed graphs, in which vertices (representing tasks to be performed) may be connected by both directed and undirected edges (representing timing constraints between tasks). The two types of edges represent constraints of two different types: *If one task x must be performed earlier than a second task y, this constraint is represented by a directed edge from x to y. *If, on the other hand, two tasks x and y can be performed in either order, but not simultaneously (perhaps because they both demand the use of the same equipment or other resource), this non-simultaneity constraint is represented by an undirected edge connecting x and y. Pairs of tasks that have no constraint on their ordering – they can be performed in either order or even simultaneously – are disconnected from each other in the graph. A valid schedule for the disjunctive graph may be obtained by finding an acyclic orientation of the undirected edges – that is, deciding for each pair of non-simultaneous tasks which is to be first, without introducing any circular dependencies – and then ordering the resulting directed acyclic graph.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.