Title: 

The Design and Implementation of a Parallel Solution to the Cutting Stock 
Problem


Abstract:

Combinatorial optimization problems often exhibit degrees of
irregularity which make them challenging to solve on parallel
systems. The irregularities in these problems can typically be 
traced to the use of control structures, data representations
which are unstructured or become unbalanced, and communications 
requirements that are unknown or unpredicatable.
Our initial research towards developing parallel implementations of a
cutting stock optimization algorithm has demonstrated that efficient 
solutions on workstation clusters and multiprocessing systems
can be obtained by properly addressing the problem's irregularities.
The key factors in this implementation are a replicated data
structure, a token-based lazy consistency mechanism to maintain 
mutual exclusion and consistency, and the dynamic load balancing 
of a distributed work queue. 


Short Bio:

Dr. Pearl Wang is an Associate Professor of Computer Science and a Co-Director
of the Center for Parallel and Distributed Computation at George Mason 
University. She is also Associate Chair of the Computer Science Department. 
Dr. Wang's current research interests include parallel computational algebra, 
interconnection networks, and the development of parallel algorithms for 
solving discrete combinatorial optimization problems on workstation clusters. 
She has been a member of the IEEE Transactions on Parallel and Distributed 
Systems and the Journal of Parallel and Distributed Computing editorial boards,
and has served on the organizing committees of numerous parallel processing 
conferences and symposia. 


Etc:

Professor Pearl Y. Wang
Computer Science Department MSN 4A5
George Mason University
4400 University Drive
Fairfax VA  22030-4444

email: pwang@cs.gmu.edu

Phone numbers: 
  703-993-1527 (GMU office)
  703-993-1530 (CS dept)
  703-993-1710 (CS dept fax)