Applications of Graph and Scheduling Theory
for getting out of Ohio State

Project Information

Participants: Eugene Talagrand; Mauktik Gandhi; Jeffrey Mathew
Start Date: 2003 February 7
Project Status: Active (as of 2010 March 22)

Index:

Abstract
Project Scope and Directions
Calendar
Project Development
Findings and Contributions
Links and References

The focus of this project is to develop algorithms and techniques to solve scheduling problems with prerequisites. The goal is to schedule a certain amount of events in as short of a time possible, while considering the fact that some events must occur before others, some events cannot occur at the same time due to conflicts, and that at any given time there is a bounded number of events that can be happening simultaneously (due to limited resources).

Scheduling university courses towards a degree is one instance of such a problem, and will be the initial focus of our algorithm implementations. Other important applications of these ideas lie in industry, such as scheduling the flow of materials through a factory: parts must go through a fixed order of processing and machines, yet all machines cannot be run on all parts at once.

Project Scope and Directions

The scheduling-with-prerequistes problem is NP-Complete, and could be solved using existing alorithms in exponential time. This is unacceptable for large problems. One of the directions that this project has taken is to develop intelligent heuristics that will find approximate solutions to this problem in polynomial time. We are also working on making these heuristics progressive, meaning that the longer the timeframe they are allocated, the better the answer.

Calendar:

2003 February 7

Analysis of all project requirements and parameters. Developed basic framework to encapsulate the functionality. Exploration of possible future algorithms.

2003 Febrary

Tree model, analysis of graph algorithms. Running time: 10^55 operations - powers upon powers of ages of the Universe.
NP-Complete
Move working model to tape of cells - the quarters. The tree model is now reserved for prerequisite analysis.
Conflict resolution pouches, forward and backward sweeps to reduce size of the problem set.
Cascading conflict resolution - unfortunately, the method already needs part of a solution to be effective.
The fundamental conflicting goals of prerequisites versus time conflicts severely restricts the simplifications that can be made.
Generalizations such as simple boolean conflicts considered.
Elimination of special cases such as half-summer terms and the like to allow for simple reasoning. These can be considered through transformations performed on the input data.

2003 March

Further exploration of branch and bound techniques to dramatically reduce the size of the problem set - eliminating entire swathes of possibilities.
Attempt at correcting the 'edge' effect of beginning and ending quarters - starting from both ends, from the middle, backwards or all at once.
Autocorrection cascades, etc...
Jam on bread model.
Identification of bottlenecks - key objects that need to be scheduled first.
Any move away from branch and bound techniques brings us to the dilemma of optimization of two constraints, which we cannot solve as of yet.
More optimizations to the problem set would involve heuristics.

2003 April 1

Beginning work on heuristics, bags and overflow management.
Considerations into the use of graph centrality.
Heuristics reduce NP-completeness to small instances of the subset sum problem when applied to individual bags.
The 3 set problem can itself be calculated heuristically in polynomial time.

2003 April 9

Meeting with Dr. Mark Posner from the Industrial Systems Engineering department. Discovery of linear programming, binary programming, crew scheduling and the simplex method for solving this problem. As this is an NP-Complete problem, current deterministic algorithms operate in exponential time on the data. While this is not a severe limitation on the size of the sample problem considered (scheduling university classes), pursuing the heuristical route would allow approximations for problems of higher order magnitude.

2003 April 16

The problem has been layed out. Begin overview of an implementation framework. This would allow concretizing of current ideas, as well as further analysis into the inherent structures and patterns found in the input data.

2003 April 22

Cutsets?

2003 April 24

Recasting of the general flow of control between the different algorithms

2003 April 26

Coupling of the jam-on-bread heuristic with the branch-and-bound techniques at processing time to allow for the development of progressive heuristics that improve their results the longer the timeframe.
This jump-starts the lengthy deterministic algorithms by eliminating the edge effect.

2003 May

Developped an application framework and implementation for OSU scheduling. Longest-path in a graph algorithm implemented as a separate project

2003 May 19

Basic framework completed, advanced algorithms still need to be implemented

2003 May 20

Europa Presentation

The Future...

Different algorithms still remain for consideration ...

Advanced graph and matroid theoretical methods remain to be applied (cutsections, central nodes, eigenvalues, etc...)
As with the switch from tree model to tape model, other models might prove themselves more appropriate for the solution of the problem.
Applications of novel computational models such as neural networks - have each class attempt to schedule itself, etc...

Further generalizations into the model: move away from discrete duration blocks such as the quarter....