**Table of Contents**

Scheduling algorithms have very close relation to graph algorithms.
Scheduling toolbox offer an object graph (see section Chapter 6, *Graphs*) with several graph algorithms.

List of algorithms related to operations with object graph are summarized in Table 9.1, “List of algorithms”.

algorithm | command | note |
---|---|---|

Minimum spanning tree | `spanningtree` | Polynomial |

Dijkstra's algorithm | `dijkstra` | Polynomial |

Floyd | `floyd` | Polynomial |

Minimum Cost Flow | `mincostflow` | Using LP |

Critical Circuit Ratio | `criticalcircuitratio` | Using LP |

Hamilton circuit | `hamiltoncircuit` | NP-hard |

Quadratic Assignment Problem | `qap` | NP-hard |

**Table 9.1. List of algorithms**

Spanning tree of the graph is a subgraph which is a tree and connects all the vertices together. A minimum spanning tree is then a spanning tree with minimal sum of the edges cost. A greedy algorithm with polynomial complexity is used to solve this problem (for more details see Demel02). The toolbox function has following syntax:

gmin = spanningtree(g)

- gmin
minimum spanning tree represented by graph

- g
input graph

Dijkstra's algorithm is an algorithm that solves the single-source cost of shortest path for a directed graph with nonnegative edge weights. Inptut of this algorithm is a directed graph with costs of invidual edges and reference node r from which we want to find shortest path to other nodes. Output is an array with distances to other nodes.

distances = dijkstra(g,r)

- g
graph object

- r
reference node

Floyd is a well known algorithm from the graph theory
[Diestel00]. This algorithm
finds a matrix of shortest paths for a given graph. Input to the algorithm
is an object graph, where the weights of edges are set in
`UserParam`

variables of edges. Output is a matrix of
shortest paths (**U**) and optionally matrix
of the vertex predecessors (**P**) in the
shortest path and adjacency matrix of lengths (**M**). Algorithm can be run as follows:

[U,P,M] = floyd(g)

The variable `g`

is an instance of graph
object.

The Strongly Connected Components (SCC) of a directed graph are
maximal subgraphs for which hold every couple of nodes
`u`

and `v`

there is a path from
`u`

to `v`

and a path from
`v`

to `u`

. For SCC searching Tarjan
algorithm is usullay used.

The algorithm is based on depth-first search where the nodes are placed on a stack in the order in which they are visited. When the search returns from a subtree, it is determined whether each node is the root of a SCC. If a node is the root of a SCC, then it and all of the nodes taken off before it form that SCC. The detailed describtion of the algorithm is in [DSVF06]. SCC in a graph G can be found as follows:

scc = tarjan(g)

where `scc`

is a vector where the element
`scc(i)`

is number of component where the node
`i`

belongs to. For graph in Figure 9.5, “A simple network with optimal flow in the fourth user parameter
on edges” the algorithm returns fllowing
results.

The minimum cost flow model is the most fundamental of all network
flow problems. In this problem we wish to determine a least cost shipment
of a commodity through a network in order to satisfy demands at certain
nodes from available supplies at other nodes [Ahuja93]. Let `G=(N,A)`

be a
directed network defined by set `N`

of n nodes and a set
`A`

of m directed edges. Each edge
`(i,j)A`

has an associated cost
`c`

_{ij} that denotes the cost per
unit flow on that arc. We also associate with each edge a
*capacity*
`u`

_{ij} that denotes the maximum
amount that can flow on the arc and a *lower bound*
`l`

_{ij} that denotes the minimum
amount that must flow on the arc. We associate with each node
`i`

`N`

an integer number
`b(i)`

representing its suply/demand. If
`b(i)>0`

, node `i`

is a
*supply node*; If `b(i)<0`

, node
`i`

is a *demand* of
`-b(i)`

; and if `b(i)=0`

, node
`i`

is a *transshipment node*. The
problem can be solved using function
`mincostflow`

:

gminf=mincostflow(g)

where `g`

is a graph, where suply/demand
`b(i)`

is stored in the first user parameter (UserParam)
of nodes. Parameters (`c`

_{ij},
`l`

_{ij},
`u`

_{ij}) are given in the first,
second and third user parameter (UserParam) of corresponding edge
`e`

_{ij}. The function returns graph
`G_minf`

where the optimal flow
`f`

_{ij} is stored in the fourth user
parameter (UserParam) on edge
`e`

_{ij}. A simple example is shown
in Figure 9.6, “Mincostflow example.” and Figure 9.7, “A simple network with optimal flow in the fourth user parameter
on edges”.

The algorithm use function 'ilinprog' from the TORSCHE. Solver GLPK must be installed. Installation of TORSCHE

This problem is also called minimum cost-to-time ratio cycle problem
[Ahuja93]. The algorithm assumes
graph `G`

where edges are weighted by a couple of
constants length `l`

and height `h`

. The
objective is to find the critical circuit ratio defined as

where `C`

is a cycle of graph `G`

.
The circuit `C`

with maximal circuit ratio is called
critical circuit. Function

rho=criticalcircuitratio(G)

finds minimal circuit ratio in a graph `G`

, where
length `l`

and height `h`

are specified
in the first and the second user parameters on edges (UserParam). Graph
weighted by a couple `l, h`

can be created from matrices
`L`

and `H`

as shown in Example Critical circuit ratio where element ```
L(i,j),
H(i,j)
```

contains length, height of edge `e(i,j)`

respectively.

>> L=[inf 2 inf;2 inf 1; 1 inf inf] L = Inf 2 Inf 2 Inf 1 1 Inf Inf >> H=[inf 0 inf;1 inf 0;2 inf inf] H = Inf 0 Inf 1 Inf 0 2 Inf Inf >> G=graph((L~=inf)*1) adjacency matrix: 0 1 0 1 0 1 1 0 0 >> G=matrixparam2edges(G,L,1); >> G=matrixparam2edges(G,H,2); >> rho=criticalcircuitratio(G) rho = 4.0000

**Figure 9.8. Critical circuit ratio.**

A Hamilton circuit in a graph `G`

, is a graph cycle
through `G`

that visits each node exactly once. The
general problem of finding a Hamilton circuit is NP-complete
[Diestel00]. The solution in the
toolbox is based on Integer Linear Programming.

gham=hamiltoncircuit(g,edgesdirection)

- gham
hamilton circuit represented by a graph

- g
input graph

`G`

- edgesdirection
specifies whether

`g`

is undirected ('u') or directed ('d') (directed graphs are default)

A simple example representing a traffic network in Czech Republic is shown in Example Hamilton Circuit Identification and Figure 9.10, “An example of Hamilton circuit.”.

`>> load ``<Matlab root>\toolbox`

\scheduling\stdemos\...
benchmarks\tsp\czech_rep
>> gham=hamiltoncircuit(g,'u');
>> graphedit(gham);

**Figure 9.9. Hamilton circuit identification example.**

The algorithm use function 'ilinprog' from the Scheduling toolbox. Solver GLPK must be installed. Installation of TORSCHE.

Graph coloring is assignment of values representing colors to nodes in a graph. Any two nodes, which are connected by an edge, cannot be assigned (colored) the same value. Graphcoloring algorithm is intended to colour graph by minimal number of colors. The least number of colors needed for coloring is called chromatic number of the graph χ. This algorithm, based on backtracking, was taken over from Demel02. Assigned values are of integer type saved as user parameter of each node and RGB color for nodes graphical representation.

G2 = graphcoloring(G1, userparamposition)

- G1
input graph

- G2
colored graph

- userparamposition
specifies position (index) in userparam of node to save "color". This parameter is optional. Default index is 1.

This algorithm solves the Quadratic Assignment Problem (QAP) Stützle99. The problem can be stated as follows. Consider
a set of `n`

activities that have to be assigned to
`n`

locations (or vice versa). A matrix **D**=
[`d`

_{ih}]_{n,n}
gives distances between locations, where
`d`

_{ih} is distance between location
`i`

and location `h`

, and a matrix
**F** =
[`f`

_{jk}]_{n,n}
characterizes flows among activities (transfer of data, material, etc.),
where `f`

_{jk} is the flow between
activity `j`

and activity `k`

. An
assignment is a permutation π of {1,...,`n`

}, where π(i)
is the activity that is assigned to location `i`

. The
problem is to find a permutation π_{m} such that the
product of the flows among activities is minimized by the distances
between their locations. Formally, the QAP can be formulated as the
problem of finding the permutation π which minimizes the following
objective function:

The optimal permutation π_{opt} is defined by
where Π(`n`

) is the set of all
permutations of {1,...,n}.

The problem can be reformulated to show the quadratic nature of the
objective function: solving the problem means identifying a permutation
matrix **X** of dimension n × n (whose
elements `x`

_{ij} are 1 if the
activity `j`

is assigned to location `i`

and 0 in the other cases) such that:

subject to the constraints and . In the toolbox the problem can be solved using Mixed Integer Quadratic Programming (MIQP).

[xmin,fmin,status,extra]=qap(distancesgraph,flowsgraph)

The function returns a nonempty output if a solution is found.
Matrix `xmin`

is optimal value of decision variables,
`fmin`

is equal to 0.5 times optimal value of the
objective function, `status`

is a status of the
optimization (1-solution is optimal) and `extra`

is a
data structure containing field `time`

- time (in
seconds) used for solving. Parameters `distancesgraph`

and `flowsgraph`

are graphs, where distances and flows
are specified in first user parameter on edges
(`UserParam`

). Graphs can be created form matrices
**D** and **F**
as shown in Quadratic Assignment Problem example in Quadratic Assignment Problem. Some benchmark instances QAPLIB06 are located in
`\scheduling\stdemos\benchmarks\qap\`

directory.

>> D = [0 1 1 2 3;1 0 2 1 2;1 2 0 1 2;2 1 1 0 1;3 2 2 1 0] D = 0 1 1 2 3 1 0 2 1 2 1 2 0 1 2 2 1 1 0 1 3 2 2 1 0 >> F = [0 5 2 4 1;5 0 3 0 2;2 3 0 0 0;4 0 0 0 5;1 2 0 5 0] F = 0 5 2 4 1 5 0 3 0 2 2 3 0 0 0 4 0 0 0 5 1 2 0 5 0 %Create graph of distances >> distancesgraph=graph('adj', 1*(D~=0)); %Insert distances into the graph >> distancesgraph=matrixparam2edges(distancesgraph,D,1,0); %Create graph of flow >> flowsgraph=graph('adj', 1*(F~=0)); %Insert flows into the graph >> flowsgraph=matrixparam2edges(flowsgraph,F,1,0); >> [xmin,fmin,status,extra]=qap(distancesgraph,flowsgraph) xmin = 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 fmin = 25 status = 1 extra = time: 1.2660

**Figure 9.12. Quadratic Assignment Problem.**

The algorithm use function `iquadprog`

from the
toolbox.

Smaller benchmark instance (not presented in QAPLIB06) can be found e.g. on http://ina2.eivd.ch/collaborateurs/etd/problemes.dir/qap.dir/qap.html.