	SSP Project Summary:

[EPCC home] [SSP home] [2001 projects] [2000 projects] [1999 projects] [1998 projects] [1997 projects] [1996 projects] [1995 projects] [1994 projects] [1993 projects]

Applications of Parallel Processing in Management Science and Operational Research

In October 1996 a new MSc in Operational Research (OR) and Management Science (MS) will be run within the departments of Business Studies and Mathematics & Statistics. An integral part of this course will be the application of high performance computing to practical problems in OR/MS. One aspect of this will involve the construction of a set of sample parallel programs for a few practical problems, so that students can explore how the success of parallel implementations is affected by the problem characteristics (eg sparsity, size) and the solution approach (eg direct, iterative or decomposition methods).

In the past a number of Computer Science and Management Science students have considered the implementation of OR/MS algorithms in their honours year projects. There are also several staff members in the host departments with expertise in the application of parallel processing to OR/MS problems. Whilst this provides a base from which to start, it does not yield a comprehensive view of the types of problems that parallel processing might be applied to in OR/MS.

The aims of this project are to:

explore the range of possible solution approaches within the areas of OR and MS that could benefit from parallel processing;
identify one or two practical problems that can be solved by each solution approach considered in 1;
implement some of the solution approaches or problems on a network of workstations using FORTRAN and MPI with the aim of demonstrating as many different aspects of parallel processing as possible (eg task farm, domain decomposition, load balance);
identify any factors that are common to the different implementations.

Proposed Workplan

Week 1: Training course
Week 2-3: Steps 1 and 2. Would involve liaising with members of the host departments and reviewing recent literature.
Week 4-5: Implementation of a serial version of a single solution approach/problem combination.
Week 6-9: Production of a parallel version and benchmarking
Week 10: Report

Problem Statement

A typical OR/MS problem is the Inventory Control. This type of problem is faced by a number of industries involved with manufacturing and production. The aim is to balance the cost of manufacturing, storage against the failure to satisfy customer requirements. It is assumed in this project that more than one type of item is stored. For this reason the dimensionality can be extremely large. Frequently the optimal solution is found by complete enumeration using discrete optimisation. This is therefore a very large problem which would be ideally suited for parallel programming.

The formulation of the problem we feel most appropriate is via dynamic programming, though, of course, it would be possible for the student to explore alternative approaches. Guidance could be given over a range of alternative methodologies to tackle the problem.

A possible formulation as a simple recurrence relationship would be as follows for the inventory control problem:

(Hard maths omitted - see paper copy!)

In a parallel implementation one could consider partitioning the state space at period n-1 (the range of i), the action space at period n-1 (the range of k) and/or the state space at stage n (the range of j).

The data required by the problem would be the parameters of the probability distribution and the cost data which are all assumed to be stationary. (Greater complexity would evolve if this assumption was not taken.)

The level of complexity could be varied as required by considering multiple items and multiple depots. We have real data for a large scale inventory problem that could be made available to the student.

Depending on the success of this, one or two more combinations can then be addressed. As this problem shares certain characteristics with some problems in reservoir management and portfolio analysis, these areas might be suitable at this stage.

The outcome of the project would be Fortrn code which the MSc students would be able to explore on UNIX workstations in Mathematics and Statistics with Fortran and MPI.

Experise Required

Fortran programming

Resources Required

Workstation network, FORTRAN90(or 77) and MPI.

Resources Supplied

Serial version of the code?
Input data; this would depend on the specific size of problem addressed. Items would require costs of manaufacture, storage and costs of lost trade. There would also be parameters of distributions for demand for each item.
References to problem statement and background reading Principles of Operational Research for Management FS Budnick, R Mojena, TE Vollmann, Irwin Inc, 1977.

Dennis Lee worked on this project.

Compressed PostScript of the project's final report is available here (65 kbytes) .

Webpage maintained by mario@epcc.ed.ac.uk