Award Abstract #0132811
PECASE: Monotone Optimal Policies in Parallel Processing Networks

NSF Org:	CMMI Division of Civil, Mechanical, and Manufacturing Innovation
Initial Amendment Date:	January 31, 2002
Latest Amendment Date:	May 31, 2004
Award Number:	0132811
Award Instrument:	Continuing grant
Program Manager:	Suvrajeet Sen CMMI Division of Civil, Mechanical, and Manufacturing Innovation ENG Directorate for Engineering
Start Date:	September 1, 2002
Expires:	September 30, 2005 (Estimated)
Awarded Amount to Date:	$225000
Investigator(s):	Mark Lewis mel47@cornell.edu (Principal Investigator)
Sponsor:	University of Michigan Ann Arbor 3003 South State St. Ann Arbor, MI 48109 734/764-1817
NSF Program(s):	OPERATIONS RESEARCH
Field Application(s):	0107000 Operations Research
Program Reference Code(s):	MANU, 9147, 9102, 1187, 1076, 1045
Program Element Code(s):	5514

ABSTRACT



Proposal Title: PECASE: Monotone Optimal Policies in Parallel Processing Networks

Institution: University of Michigan Ann Arbor

This PECASE award will explore the application of Markov decision processes to three related problems in parallel queueing systems. In each scenario, as the number of parallel queues increases, the complexity of the decision-making process increases. Thus, finding the structure of the optimal policy in order to decrease the size of the search becomes crucial. The first problem considered is a question of routing in a multi-server queueing system that appears in several areas of industry. For example, in demand chain logistics a company receives a request for a particular part. This part may be manufactured at several different plants in the same general area. If the company has an integrated information source, a decision-maker can query the system about how much work is in process at each of the several plants, estimate the time (and cost) it will take each plant to complete the job at hand and place the order accordingly. We next take the same routing problem described above and consider scheduling in a particular manufacturing plant. If there are several stations capable of performing the same task, the applicability of the previous model remains. We complicate matters a bit, by noting that some of the machines may deteriorate. We then seek a joint, maintenance and routing policy. Finally, we consider an example of load balancing that is useful in parallel computing. Sup-pose that work orders can be broken up, partially served on any computer and, upon completion, reassembled. Since the computers are networked, and a decision-maker would like to utilize these resources wisely, it may be advantageous to re-route work that has been sitting in queue at a particular machine to a different machine. That is to say, that the decision-maker would like to keep the load balanced between machines. The decision where a job will actually be processed is thus reevaluated so that idleness is reduced.

The main thrust of the education plan in this proposal is to try to increase the number of successful Minority graduate students in industrial engineering and operations research. This will be facilitated by several activities, not the least of which is to attempt to increase the number of minority graduate students at the University of Michigan. Close ties to the undergraduates in the Industrial and Operations Engineering Department (IOE) at the university will be developed through mentoring and increased financial support for under-represented minority graduate students will reduce teaching requirements.

This project was originally funded as a CAREER award, and was converted to a Presidential Early Career Award for Engineers and Scientists (PECASE) award in May 2004.

Please report errors in award information by writing to: awardsearch@nsf.gov.