SchedMatch: An efficient algorithm to match schedules and other partial orders

Dennis Shasha
Courant Institute of Mathematical Sciences
Department of Computer Science
New York University
shasha@cs.nyu.edu
http://cs.nyu.edu/cs/faculty/shasha/index.html

Jason Wang
Department of Computer Science
New Jersey Institute of Technology
jason@cis.njit.edu

Kaizhong Zhang
Department of Computer Science
University of Western Ontario
kzhang@csd.uwo.ca




Motivation

Suppose you have two schedules S1 and S2. Each is represented by a set of dependency edges with redundant transitive edges removed. (Note however that if there are edges from task A to task B and from B to C, there may still be an edge from A to C if that edge presents a separate constraint from what is implied by the path through B.) The software assumes that each schedule by itself is acyclic (i.e. if there is a dependency from A to B either directly or transitively, then there is no dependency from B to A).

A schedule is a special case of a partial order. This software applies to all partial orders, but we continue to use the word schedule for the sake of concreteness. Other possible applications include ontology matching and in general hierarchy comparison.

The problem is to reconcile the two schedules. Our definition of reconcilation is to find as few edges as possible to remove from either S1 or S2 to render the two schedules consistent. Informally, consistency means that if one schedule insists on ordering task A before B then the other schedule does not insist on ordering B before A. Formally, consistency means that there is some total order of the tasks that both can agree on. An equivalent formal definition is that two schedules are consistent if combining them introduces no cycles.

This problem was inspired by listening to the presentation of "Behavioral matchmaking for service retrieval: application to conversation protocols," by Juan Carlos Corrales, Daniela Grigori, Mokrane Bouzeghoub and published in BDA 2006. The authors use a different matching criterion.

Whereas this software is a form of graph matching, it makes strong use of transitivity. If you are interested in graph comparison without that assumption, please see our package for graph comparison.

You can also find a software package (GraphGrep) to search for a query graph in a database of graphs here.


Installation

The approximate schedule matcher runs in a high performance interpreted environment called K.