An Efficient Solver for Scheduling Problems on a Class of Discrete Event Systems Using CELL/B.E. Processor

This research implements an efficient solver for scheduling problems in a class of repetitive discrete event systems using a CELL/B.E. (cell broadband engine). The essence of this involves efficiently computing the transition matrix of a system whose precedence constraints regarding the execution sequence of jobs can be described by a weighted DAG (directed acyclic graph). This means solving the longest path problem efficiently for all pairs of source and destination nodes. For the first step towards a high-speed computation, we utilize SIMD (single instruction multiple data) functions.