The Workshop is centered around four main speakers, with one speaker for each of four areas of decision process applications. The speakers and topics for the Workshop are the following.
Professor P. R. Kumar (Department of Electrical and Computer Engineering and Coordinated Science Laboratory, University of Illinois at Urbana) will speak on New Directions in Scheduling Manufacturing Systems: Performance Analysis and Design.
Professor Stanley R. Pliska (Department of Finance, University of Illinois at Chicago) will speak on mathematical finance.
Professor David O. Siegmund (Department of Statistics, Stanford University) will speak on Change-point Problems and Applications.
Professor William D. Sudderth (School of Statistics, University of Minnesota at Minneapolis) will speak on gambling and stochastic games.
The speaker for each area is being asked to give two one-hour talks, with the two hours containing some background, having some breadth, mentioning some important recent results and techniques in the area, and giving some good open problems in the area. Although much of the talks should not require too much background, each of the speakers has prepared a reading list with both some general and specific readings in the area related to their talk, for those who may wish to preview the areas of application before the talks. Here are the reading lists prepared by the speakers.
(Requests for further information may be addressed to Bob Kertz, preferably by email (kertz@math.gatech.edu), by telephone (404-894-2700), or by regular mail (School of Mathematics). More information about this workshop can be found from our World Wide Web page at http://nanjing.isye.gatech.edu/cap/96-workshop/workshop.html).
Many manufacturing and other systems, e.g., communication networks and
computer systems, are modeled as queueing networks. Frequently one
wants to control such systems by an appropriate choice of a scheduling
policy.
On the descriptive side, in the 1950s, Jackson obtained the explicit formulas for the steady-state distribution of certain queueing networks. This class was expanded in the 1970s through the work of Baskett, Chandy, Muntz and Palacios, and Kelly, and others. However, most queueing networks do not satisfy the stringent and fragile assumptions of this theory.
Recently, we have developed new methods for addressing questions related to the performance of such networks. Instead of seeking exact explicit answers, the goal of this new approach is to reduce issues related to performance analysis to the well developed computational approach of solving linear programs.
This approach allows one to obtain bounds on the steady-state or transient performance of key quantities such as mean delay or throughput, establish the stability or efficiency of systems, address issues related to heavy traffic performance such as asymptotic loss or pole multiplicity, and obtain dominating functional expansions.
On the prescriptive side, over the past few years we have developed new approaches whose philosophy is to introduce feedback, stability and dynamics into the modeling, analysis and synthesis of manufacturing systems. By this approach one seeks to avoid static formulations which often lead to intractable combinatorial optimization problems over a finite time horizon. By studying the dynamics of systems, one hopes to design distributed policies which can be implemented in real-time and which yield good performance. Such an approach has led to the design of scheduling policies for systems with set-up times, due-dates, etc., and to new results concerning some commonly mentioned dispatching rules. It has also led to new approaches for scheduling large scale plants.
The two talks will attempt to address these new approaches.
An excellent reference for the classical work on performance evaluation for queueing networks is,
F. P. Kelly, Reversibility and Stochastic Networks. New York, NY: John Wiley and Sons, 1979.
Early accounts of sequencing and scheduling can be found in the following two books,
K. Baker, Introduction to Sequencing and Scheduling. New York, NY: John Wiley and Sons, 1974,
and
R. W. Conway, W. L. Maxwell, and L. W. Miller, Theory
of Scheduling.
Reading, MA: Addison--Wesley, 1967.
An up to date account of the above approach to scheduling is given in the excellent survey,
E. L.Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, ``Sequencing and Scheduling: Algorithms and Complexity,'' in S. C. Graves et al., Eds., Handbooks in OR and MS, vol. 4, pp. 445--522, Elsevier Science Publishers, Amsterdam, 1993.
Now we turn to the topics addressed in these talks. These are mostly taken from the following articles, many of which are available at the following WWW location:
http://black.csl.uiuc.edu/prkumar
If you need hard copies, please send a message to:
Kumar, P. R. (1994). Scheduling Manufacturing Systems of Re-Entrant Lines, pages 325--360, in Stochastic Modeling and Analysis of Manufacturing Systems, Springer-Verlag, New York, NY, David D. Yao (ed.).
Kumar, P. R. (1994). "Scheduling queueing networks: Stability, performance analysis and design." Technical report, Coordinated Science Laboratory, University of Illinois, Urbana, IL. To appear in Stochastic Networks, IMA Volumes in Mathematics and its Applications, Frank Kelly and Ruth Williams, Editors, Springer-Verlag.
Kumar, P. R. (1995). "A tutorial on some new methods for performance evaluation of queueing networks." IEEE Journal on Selected Areas in Communications: Special Issue on -- Advances in the Fundamentals of Networking -- Part I: Bridging Fundamental Theory and Networking 13 (6), 970--980.
Bielecki, T. and Kumar, P. R. (1988). "Optimality of zero-inventory policies for unreliable manufacturing systems." Operations Research 36, (4), 532--541.
Perkins, J. R. and Kumar, P. R. (1989). "Stable distributed real-time scheduling of flexible manufacturing/assembly/disassembly systems." IEEE Transactions on Automatic Control AC-34 (2), 139--148.
Kumar, P. R. and Seidman, T. I. (1990). "Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems." IEEE Transactions on Automatic Control AC-35 (3), 289--298.
Perkins, J. R. , Humes, Jr., C. and Kumar, P. R. (1994). "Distributed scheduling of flexible manufacturing systems: Stability and performance." IEEE Transactions on Robotics and Automation: Special Section on Computer Integrated Manufacturing 10 (2), 133--141.
Lu, S. H. and Kumar, P. R. (1991). "Distributed scheduling based on due dates and buffer priorities". IEEE Transactions on Automatic Control AC-36 (12), 1406--1416.
Winograd, G. I. and Kumar, P. R. (1994). "Stable network topologies, bounds on traffic burstiness and delay, and control by regulators." To appear in Mathematical and Computer Modelling: Special Issue on Recent Advances in Discrete Event Systems.
Perkins, J. R. and Kumar, P. R. (1995). "Optimal control of pull manufacturing systems." Technical report, University of Illinois, Urbana, IL. submitted to the 1994 ACC.
D. Bertsimas, I. C. Paschalidis, and J. N. Tsitsiklis, ``Optimization of multiclass queueing networks: Polyhedral and nonlinear characterizations of achievable performance,'' Annals of Applied Probability, vol. 4, pp. 43--75, 1994.
Kumar, S. and Kumar, P. R. (1994). "Performance bounds for queueing networks and scheduling policies." IEEE Transactions on Automatic Control AC-39, 1600--1611.
Kumar, P. R. and Meyn, S. P. (1995). "Stability of queueing networks and scheduling policies." IEEE Transactions on Automatic Control 40 (2), 251--260.
Kumar, P. R. and Meyn, S. P. (1993). "Duality and linear programs for stability and performance analysis of queueing networks and scheduling policies." Technical report, C. S. L., University of Illinois. To appear in IEEE Transactions on Automatic Control.
Jin, H., Ou, J. and Kumar, P. R. (1994). "The throughput of closed queueing networks--functional bounds, asymptotic loss, efficiency, and the Harrison-Wein conjectures." Submitted to Mathematics of Operations Research.
Humes, Jr., C., Ou, J. and Kumar, P. R. (1995). Delay and throughput bounds for open and closed queueing networks: Uniform functional expansions, heavy traffic pole multiplicities, stability and efficiency. Coordinated Science Laboratory, University of Illinois.
It is easy to pinpoint the birth of mathematical finance: the thesis "Theory of Speculation," presented to the Faculty of Sciences of the Academy of Paris on March 29, 1900, by Louis Bachelier for the degree Docteur es Sciences Mathematiques. Bachelier not only made a brilliant application of mathematics to the problem of evaluating the price of a call option, but he invented what came to be called Brownian motion for the purpose of modeling the price of the underlying stock. Unfortunately, Bachelier's fantastic work was ignored and forgotten for half a century. It is unclear why he did not receive more credit for inventing Brownian motion, but perhaps he received little attention for his option pricing model because Brownian motions become negative, whereas stock prices do not. In any event, an English translation of Bachelier's thesis is found in Cootner (1964), a collection of various papers, most of which deal with statistical aspects of stock market prices.
During the 1950s and 1960s, financial research primarily addressed statistical and economic problems, but one problem that challenged many was the same as Bachelier's: what is the correct price of a call option? Researchers soon agreed that geometric Brownian motion is a good model for the price of a stock, but they could not agree on much else until 1971, when Black and Scholes provided the critical insight. They argued that if the value of a portfolio of traded securities coincided almost surely with the payoff of the call option, then the earlier value of the call option must coincide with the earlier value of the portfolio. They showed how a portfolio involving the underlying stock coupled with borrowing and lending at a constant interest rate could replicate the call option's payoff, they derived a partial differential equation whose solution is the value of the option, and they solved this equation to obtain their now famous ``Black and Scholes formula." Not only did they invent a formula that is commonly used by speculators around the world, but they kicked off ``arbitrage pricing theory" and they triggered research in what is now called mathematical finance.
During the 1970s, much of the research in mathematical finance had a partial differential equation orientation, with geometric Brownian motion models of the security prices lurking in the background. For example, Merton made some significant applications of the pde technology to portfolio management problems (most of his papers are collected in his 1990 book). There were some successful attempts to combine arbitrage pricing theory with other models of security prices (notably the discrete time, binomial option pricing model treated in the book by Cox and Rubinstein), but advancements seemed to be held back by the lack of general theory. A major breakthrough was provided by Harrison and Kreps (1979), who recognized that for a securities market model to be sensible from the economic standpoint, the discounted security prices must be martingales after a change of probability measure. Moreover, they recognized that the gain or loss of a portfolio should be modeled as a stochastic integral of the trading strategy with respect to the price process, leading to very general risk neutral valuation principles for determining the price of a derivative. Their work was quickly fleshed out and elucidated by Harrison and Pliska (1981), who also developed important linkages with the powerful techniques of modern stochastic calculus. The foundations were then in place for the analysis of very general derivatives in conjunction with very general models of security prices.
Hence during the 1980s, mathematical finance turned away (somewhat) from partial differential equation toward a probabilistic approach. By the end of the decade there was a good understanding of the basic theory, as evidenced, for example, by the excellent 1989 survey by Karatzas, who confines his attentions to price process models having continuous sample paths. Recent research can be classified into several main categories, such as attempts to obtain improvements of the Black and Scholes formula by considering more realistic models of the underlying security or by considering the impact of transaction costs. Considerable attention was also given to the valuation of exotic options and other derivatives. But perhaps the main theme in recent years has been the development of term structure models of interest rates, used for the valuation of interest rate based derivatives. Some key papers here are by Vasicek (1977), Cox, Ingersoll, and Ross (1985), and Heath, Jarrow, and Morton (1992).
Cootner, P. (1964).The Random Character of Stock Market Prices. The M.I.T. Press, Cambridge, MA
Cox, J. Ingersoll, J. and Ross, S. (1985). "A theory of the term structure of interest rates." Econometrica 53 385-408.
Cox, J. and Rubinstein, M. (1985).Options Markets. Prentice Hall, Englewood Cliffs, New Jersey.
Harrison, J. and Kreps, D. (1979). "Martingales and arbitrage in multiperiod securities markets." J. Economic Theory 20 381-408.
Harrison, J. and Pliska, S. (1981). "Martingales and stochastic integrals in the theory of continuous trading." Stochastic Processes and Their Applications 11 215--260.
Heath, D. Jarrow, R. and Morton, A. (1992). "Bond pricing and the term structure of interest rates: a new methodology for contingent claims valuation." Econometrica 60 77--105.
Karatzas, I. (1989). "Optimization problems in the theory of continuous trading." SIAM J. Control and Optimization 27 1221--1259.
Merton, R. (1990). Continuous-Time Finance. Basil Blackwell, Cambridge, MA.
Vasicek, O. (1977). "An equilibrium characterization of the term structure." J. Fin. Econ. 5 177--188.
Duffie, D. (1988). Security Markets -- Stochastic Models. Academic Press, New York.
Duffie, D. (1992). Dynamic Asset Pricing Theory. Princeton University Press, Princeton, NJ.
Ingersoll, J. (1987). Theory of Financial Decision Making. Rowman and Littlefield, Totowa, NJ.
The list of references for the talks on "Change Point Problems and Applications" are given below. Some are overview articles, and some are quite technical. My suggestions for preliminary study are Worsley (1986), Feingold (1993), and Siegmund (1986, 1989).
Siegmund (1988) and Siegmund and Venkatraman (1995) are in my opinion the most interesting mathematically, but they get quite technical. Similar material is presented in Siegmund (1992) with slightly more streamlined proofs.
Although I have not yet made a final decision about content, I expect the first talk to be general and the second to emphasize applications to genetics. I can easily explain the minimal genetics background. The papers by Risch and by Lander and Botstein (in addition to Feingold (1993)) would be useful to someone who wanted more than the minimal background. I suspect it would make sense to read them afterwards, if one wants to know more about the application, rather than in advance.
Feingold, E. (1993). "Markov processes for modeling and analyzing a new genetic mapping method." Jour. of Appl. Probab. 30, 766--779.
Feingold, E., Brown, P. O., Siegmund, D. (1993). "Gaussian models for genetic linkage analysis using complete high resolution maps of identity-by-descent." Am. J. Hum. Genetics 53, 234--251.
James, B., James, K. L., and Siegmund, D. (1987). "Tests for a change-point." Biometrika 74, 71--83.
Lander, E. S. and Botstein, D. (1989). "Mapping Mendelian factors underlying quantitative traits using RFLP linkage maps." Genetics 121, 185--199.
Risch, N. (1990a, b). "Linkage strategies for genetically complex traits I, II: The power of affected relative pairs." Am. J. Hum. Genetics 46, 222--228, 229--241.
Siegmund, D. (1986). "Boundary crossing probabilities and statistical applications." Ann. Statist. 14, 361--404.
Siegmund, D. (1988). "Tail approximations for the maxima of some random fields." Ann. Probab. 16, 487--501.
Siegmund, D. (1989). "Confidence sets in change-point problems." International Statistical Review 56, 31--48.
Siegmund, D. (1992). "Tail approximations for maxima of random fields," in Probability Theory: Proceedings of the 1989 Singapore Probability Conference, edited by L. H. Y. Chen, K. P. Choi, Kaiyuan Yu, Jiann-Hua Lou, de Gruyter, Berlin.
Siegmund, D. and Venkatraman, E. S. (1995). "Using the generalized likelihood ratio statistic for sequential detection of a change-point." Ann. Statist. 23, 255--271.
Worsley, K. (1986). "Confidence regions and tests for a change-point in a sequence of exponential family random variables." Biometrika 73, 91--104.
Worsley, K. J., Evans, A. C., Marrett, S. and Neelin, P. (1992). "A three dimensional statistical analysis for CBF activation studies in human brain." J. of Cerebral Blood Flow and Metabolism 12, 900--918.
Worsley, K. and Siegmund, D. (1995). "Testing for a signal with unknown location and scale in a stationary Gaussian random field". Ann. Statist. 23, 608--639.
The now classic work How to Gamble If You Must: Inequalities for Stochastic Processes by Dubins and Savage (1965) uses gambling terminology and examples to develop and motivate an elegant, deep, and quite general theory of discrete-time stochastic control. A gambler ``controls" the stochastic process of his or her successive fortunes by choosing which games to play and what bets to make.
The first lecture will introduce the ideas of Dubins and Savage as well as some more recent developments in gambling theory. The second lecture will apply gambling techniques to two-person, zero-sum stochastic games. These are games in which two players control a stochastic process jointly but have opposing goals.
Dubins, L., Maitra, A., Purves, R. and Sudderth, W. (1989). "Measurable, nonleavable gambling problems" Israel J. Math. 67 257--271.
Maitra, A. and Sudderth, W. (1995). "Stochastic games and operators," in Topics in Contemporary Probability and its Applications, J. L. Snell, editor, CRC Press, New York.
Maitra, A. and Sudderth, W. (1992). "An operator solution of stochastic games." Israel J. Math. 78 33--49.
Milnor, J. and Shapley, L. S. (1957). "On games of survival." Contributions to the Theory of Games III, edited by M. Dresher, A. W. Tucker, and P. Wolfe, Princeton University Press.
Raghavan, T. E. S., Ferguson, T., Parthasarathy, T., and Vrieze, O. J. (1991). Stochastic Games and Related Topics in Honor of Professor L. S. Shapley. Kluwer Academic Publishers, Boston.
Maitra, A. and Sudderth, w. (to appear). Discrete Gambling and Stochastic Games, Springer-Verlag, New York.
Last updated: January 11, 1996 by J. Shear ( joannas@isye.gatech.edu)