Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Disjunctive_graph> ?p ?o. }
Showing items 1 to 12 of
12
with 100 items per page.
- Disjunctive_graph abstract "A disjunctive graph is a mixed graph, frequently used in problems resembling job shop scheduling problems. A disjunctive graph is defined as a graph containing disjunctive edges. The disjunctive edge represents an edge that can connect any two vertices from the possible set of vertices.The disjunctive graph is a directed graph G=(V, C ,D), where V denotes a set of vertices corresponding to tasks of jobs. C is a set of conjunctive arcs (directed edges) which reflect the precedence constraints initially connecting every two consecutive tasks of the same job. Undirected disjunctive edges belonging to set D connect mutually unordered tasks which require the same machine for their execution (a disjunctive edge can be represented by two opposite directed arcs). Each arc is labelled with the positive weight equal to the processing time of the task where the arc begins.The job shop scheduling problem requires to find an optimal order of all tasks on the machines, resulting in a schedule with the minimal length. In the disjunctive graph model, this is equivalent to select one arc in each disjunction, i.e. to turn each undirected disjunctive edge into a directed conjunctive one. By fixing directions of all disjunctive edges, the execution order of all conflicting tasks requiring the same machine is determined and a complete schedule is obtained. Moreover, the resultinggraph has to be acyclic and if it is optimal, the length of the longest path from the source to the sink is minimum. This longest path determines the makespan, it is the duration of the longest chain of tasks in a job shop.".
- Disjunctive_graph wikiPageID "36964367".
- Disjunctive_graph wikiPageRevisionID "595905666".
- Disjunctive_graph hasPhotoCollection Disjunctive_graph.
- Disjunctive_graph subject Category:Graphs.
- Disjunctive_graph comment "A disjunctive graph is a mixed graph, frequently used in problems resembling job shop scheduling problems. A disjunctive graph is defined as a graph containing disjunctive edges. The disjunctive edge represents an edge that can connect any two vertices from the possible set of vertices.The disjunctive graph is a directed graph G=(V, C ,D), where V denotes a set of vertices corresponding to tasks of jobs.".
- Disjunctive_graph label "Disjunctive graph".
- Disjunctive_graph sameAs m.0m0l1v4.
- Disjunctive_graph sameAs Q5282271.
- Disjunctive_graph sameAs Q5282271.
- Disjunctive_graph wasDerivedFrom Disjunctive_graph?oldid=595905666.
- Disjunctive_graph isPrimaryTopicOf Disjunctive_graph.