TORSCHE Scheduling
Toolbox for Matlab

@graph/criticalcircuitratio.m - finds the minimal circuit ratio of the input graph.
@graph/dijkstra.m - finds the shortest path between reference node and other nodes in graph.
@graph/edge2param.m - returns user parameters of edges in graph
@graph/floyd.m - finds a matrix of shortest paths for given digraph
@graph/graph.m - creates the graph object.
@graph/graphcoloring.m - algorithm for coloring graph by minimal number of colors.
@graph/hamiltoncircuit.m - finds Hamilton circuit in graph
@graph/mincostflow.m - finds the least cost flow in graph G.
@graph/node2param.m - returns user parameters of nodes in graph
@graph/param2edge.m - add to graph's user parameters datas from cell or matrix.
@graph/param2node.m - add to graph's user parameters datas from cell or matrix.
@graph/qap.m - solves the Quadratic Assignment Problem
@graph/spanningtree.m - finds spanning tree of the graph
@graph/tarjan.m - finds Strongly Connected Component
@problem/problem.m - creation of object problem.
@schedobj/get.m - access/query SCHEDOBJ property values.
@schedobj/get_graphic_param.m - gets graphics params for object drawing
@schedobj/set.m - sets properties to set of objects.
@schedobj/set_graphic_param.m - set graphics params for drawing
@task/add_scht.m - adds schedule (starts time and lenght of time) into a task
@task/get_scht.m - gets schedule (starts time and length of time) from a task
@task/plot.m - graphic display of task
@task/task.m - creates object task.
@taskset/add_schedule.m - adds schedule (starts time and lenght of time) for set of tasks
@taskset/alap.m - compute ALAP(As Late As Posible) for taskset
@taskset/asap.m - computes ASAP(As Soon As Posible) for taskset
@taskset/colour.m - returns taskset where tasks have set the color property
@taskset/count.m - returns number of tasks in the Set of Tasks
@taskset/get_schedule.m - gets schedule (starts time, lenght of time and processor) from a taskset
@taskset/plot.m - graphic display of set of tasks
@taskset/schparam.m - returns parameters about schedule inside the set of tasks
@taskset/setprio.m - sets priority (weight) of tasks acording to some rules.
@taskset/size.m - returns number of tasks in the Set of Tasks
@taskset/sort.m - return sorted set of tasks over selected parameter.
@taskset/taskset.m - creates a set of TASKs
alg1rjcmax.m - computes schedule with Earliest Release Date First algorithm
alg1sumuj.m - computes schedule with Hodgson's algorithm
algpcmax.m - computes schedule for 'P||Cmax'problem
algprjdeadlinepreccmax.m - computes schedule for P|rj,prec,~dj|Cmax problem
bratley.m - computes schedule by algorithm described by Bratley
brucker76.m - Brucker's scheduling algorithm
coffmangraham.m - is scheduling algorithm (Coffman and Graham) for P2|prec,pj=1|Cmax problem
cssimin.m - Cyclic Scheduling Simulator - input parser.
cssimout.m - Cyclic Scheduling Simulator - True-Time interface.
cycsch.m - solves general cyclic scheduling problem.
graphedit.m - launch user-friendly editor of graphs able to export and import graphs between GUI and Matlab workspace.
horn.m - computes schedule with Horn'74 algorithm
hu.m - is scheduling algorithm for P|in-tree,pj=1|Cmax problem (can be called on labeled taskset with problem P2|prec,pj=1|Cmax )
ilinprog.m - universal interface for integer linear programming.
iquadprog.m - Universal interface for mixed integer quadratic programming.
listsch.m - Computes schedule by algorithm described by Graham 1966
mcnaughtonrule.m - computes schedule with McNaughtons's algorithm
private/bezier.m - computes points on Bezier curve
randdfg.m - random Data Flow Graph (DFG) generator.
randtaskset.m - Generates set of tasks of random parameters selected from uniform distribution.
satsch.m - computes schedule by algorithm described in [TORSCHE06]
schoptionsset.m - Creates/alters SCHEDULING TOOLBOX OPTIONS structure.
spntl.m - computes schedule with Positive and Negative Time-Lags
xmlsave.m - saves variables to file in xml format.

Literature

List of Figures

2.1. The taskset schedule
3.1. Graphics representation of task parameters
3.2. Creating task objects
3.3. Plot example
4.1. Creating a set of tasks and adding precedence constraints
4.2. Gantt chart for a set of scheduled tasks
4.3. Access to the virtual property examples
4.4. Schedule inserting example
4.5. Schedule parameters
4.6. Taskset sort example
4.7. Example of random taskset use
6.1. Creating a graphs from adjacency matrix
6.2. Command set for graph
6.3. Graphedit
7.1. Structure of scheduling algorithms in the toolbox.
7.2. Scheduling problem 1|r_j|Cmax solving.
7.3. Alg1rjcmax algorithm - problem 1|r_j|Cmax
7.4. Scheduling problem 1|r_j,~d_j|Cmax solving.
7.5. Bratley’s algorithm - problem 1|r_j,~d_j|Cmax
7.6. Scheduling problem 1||ΣUj solving.
7.7. Hodgson’s algorithm - problem 1||ΣUj
7.8. Scheduling problem P||Cmax solving.
7.9. Algpcmax algorithm - problem P||Cmax
7.10. Scheduling problem P|pmtn|Cmax solving.
7.11. McNaughton's algorithm - problem P|pmtn|Cmax
7.12. Scheduling problem P|p_j,prec,~d_j|Cmax solving.
7.13. Algprjdeadlinepreccmax algorithm - problem P|p_j,prec,~d_j|Cmax
7.14. An example of P|prec|Cmax scheduling problem.
7.15. Scheduling problem P|prec|Cmax solving.
7.16. Result of List Scheduling.
7.17. Problem P|prec|Cmax by LS algorithm with LPT strategy solving.
7.18. Result of LS algorithm with LPT strategy.
7.19. Solving P|prec|Cmax by LS algorithm with SPT strategy.
7.20. Result of LS algorithm with SPT strategy.
7.21. Solving P|rj|∑Cj by ECT
7.22. Result of LS algorithm with ECT strategy.
7.23. Problem P|rj|∑Cj by LS algorithm with EST strategy solving.
7.24. Result of LS algorithm with EST strategy.
7.25. An example of OwnStrategy function.
7.26. Scheduling problem 1|in-tree,p_j=1|Lmax solving.
7.27. Brucker’s algorithm - problem 1|in-tree,p_j=1|Lmax
7.28. Graph G representing tasks constrained by positive and negative time-lags.
7.29. Resulting schedule of instance in Figure 7.28, “Graph G representing tasks constrained by positive and negative time-lags.”.
7.30. Cyclic Data Flow Graph of WDF.
7.31. Graph G weighted by l_ij and h_ij of WDF.
7.32. Resulting schedule with optimal period w=8.
7.33. Jaumann wave digital filter
7.34. The optimal schedule of Jaumann filter
7.35. An example of in-tree precedence constraints
7.36. Scheduling problem P|in-tree,p_j=1|Cmax using hu command
7.37. Hu's algorithm example solution
7.38. Coffman and Graham example setting
7.39. Coffman and Graham algorithm example solution
8.1. Calculating the response time using resptime
8.2. PT_FPS example code
8.3. Result of FPS algorithm
9.1. Spanning tree example
9.2. Example of minimum spanning tree
9.3. Dijkstra's algorithm example
9.4. Strongly Connected Components example.
9.5. A simple network with optimal flow in the fourth user parameter on edges
9.6. Mincostflow example.
9.7. A simple network with optimal flow in the fourth user parameter on edges
9.8. Critical circuit ratio.
9.9. Hamilton circuit identification example.
9.10. An example of Hamilton circuit.
9.11. An example of Graph coloring
9.12. Quadratic Assignment Problem.
10.1. Simulation scheme with TrueTime Kernel block
10.2. Result of simulation
11.1. Result of case study as Gantt chart
11.2. Result of case study as Gantt chart
11.3. Graph representation of Chair manufacturing
11.4. Result of case study as Gantt chart
11.5. An application of Recursive Least Squares filter for active noise cancellation.
11.6. The RLS filter algorithm.
11.7. Graph G modeling the scheduling problem on one add unit of HSLA.
11.8. Resulting schedule of RLS filter.

List of Tables

6.1. List of functions
7.1. List of algorithms
7.2. An example of P|rj|∑wjCj scheduling problem.
9.1. List of algorithms
10.1. List of algorithms
10.2. List of the toolbox options parameters
10.3. Type of constraints - ctype.
10.4. Type of constraints - ctype.
11.1. Information we need to organize the work
11.2. Material transport processing time.
11.3. Parameters of HSLA library.

List of Examples

7.1. List Scheduling - problem P|prec|Cmax.
7.2. Example of Scheduling Problem with Positive and Negative Time-Lags.
7.3. Cyclic Scheduling - Wave Digital Filter.
7.4. Hu's algorithm
7.5. Coffman and Graham algorithm
9.1. Graph Coloring example

Webmaster - Jan Dvořák (2004 - 2024)