D. Garg and Y. Narahari. An Optimal Mechanism for Sponsored Search Auctions and Comparison with other Mechanisms. In:   IEEE Transactions on Automation Science and Engineering , VOlume 6, Number 4, pp. 641-657, 2009.

The advertiser-supported web site is one of the successful business models in the web landscape. In this article, we first describe a framework to model the sponsored search auction on the web as a mechanism design problem. Using this framework, we describe two well known mechanisms for sponsored search auction - Generalized Second Price (GSP) and Vickrey-Clarke-Groves (VCG). We then derive a new mechanism for sponsored search auction which we call Optimal (OPT) mechanism. The OPT mechanism maximizes the search engine's expected revenue while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We then undertake a detailed comparative study of the mechanisms GSP, VCG, and OPT.

Raghav Kumar Gautam, N. Hemachandra, Y. Narahari, Hastagiri Praksh, Datta Kulkarni, and Jeffrey D. Tew. An Optimal Mechanism for Multi-unit Procurement with Volume Discount Bids. In:   International Journal of Operational Research. Special Issue on Game Theory Applications in Operations Research and Management Science. Volume 6, Number 1, 2009, pp. 70-91.

In this paper, we extend the classical Myerson auction to the the design of an optimal procurement mechanism which a firm can use while procuring multiple units of a single homogeneous item based on bids submitted by autonomous, rational, and intelligent suppliers. We propose elegant optimal procurement mechanisms for two different situations. In the first situation, each supplier specifies the maximum quantity that can be supplied as well as a per unit price. For this situation, we design an optimal mechanism S-OPT (Optimal with Simple bids). In the more general case, each supplier specifies discounts based on the volume of supply. In this case, we design an optimal mechanism VD-OPT (Optimal with Volume Discount bids). The VD-OPT mechanism uses the S-OPT mechanism as a building block. Both the proposed mechanisms minimize the cost to the buyer, satisfying at the same time, (a) Bayesian incentive compatibility and (b) interim individual rationality.

Y. Narahari, N. Hemachandra, Nikesh Kumar Srivastava, Datta Kulkarni, and Jeffrey D. Tew. A Bayesian Incentive Compatible Mechanism for Decentralized Supply Chain Formation. In:   International Journal of Operational Research. Special Issue on Game Theory Applications in Operations Research and Management Science. Volume 6, Number 1, 2009, pp. 27-53.

In this paper, we consider a decentralized supply chain formation problem for multi-echelon supply chains when the managers of the individual echelons are autonomous, rational, and intelligent. We develop a mechanism design framework for addressing this problem and propose a Bayesian incentive compatible mechanism for supply chain formation. Existing solutions in the literature, which are based on the classical Vickrey-Clarke-Groves mechanisms, require significant incentives to be paid to the echelon managers for achieving incentive compatibility. The proposed mechanism significantly reduces the cost of supply chain formation.

S. Kameshwaran and Y. Narahari. Efficient Algorithms for Nonconvex Piecewise Linear Knapsack Problems. In:   European Journal of Operational Research. Volume 192, Number 1, 2009, Pages: 56-68.

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially in the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two different mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes; (2) exact pseudo-polynomial time dynamic programming algorithms; (3) a 2-approximation algorithm; and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Computational experiments show that the proposed formulations and algorithms are faster than the existing techniques.

G. Radhanikanth and Y. Narahari. Reverse Combinatorial Auction Based Protocols for Resource Selection in Grids. In:   International Journal of Grid and Utility Computing, , Volume 1, Number 2, 2009 Pages:109 - 120

Grid computing provides an extremely promising distributed paradigm for executing large scale resource intensive applications. Given a distributed pool of resources, a grid user who wishes to execute a job comprising a large number of tasks on the grid, is faced with the problem of selecting an optimal set of resources. We call this problem the resource selection problem and our approach to modeling and solving this problem is through a reverse combinatorial auction. In the proposed auction, the grid user is the buyer and the resource owners are the sellers. The resource owners submit bids on combinations of resources or tasks in response to the grid user's request for a bundle of resources. The objective of the grid user is to minimize an appropriately defined cost function based on these bids. Two variants of the problem are considered: (1) resource selection with task level trading and (2) resource selection with resource level trading. In both the cases, the resource selection problem turns out to be an integer linear programming problem. To investigate the performance of the proposed resource selection protocols, NAS grid benchmarks are run using SimGrid and the performance is compared against that of a cost optimization protocol and a time optimization protocol which are part of the Nimrod-G resource broker. The protocols proposed exhibit superior overall performance in terms of turn around time and total cost.

S. Kameshwaran and Y. Narahari. A Benders Based Winner Determination Algorithm for Volume Discount Procurement Auctions. In:   International Journal of Logistics and Supply Chain Managemen Special Issue on Procurement Strategies: Past-Present and the Future, Volume 5, Number 1/2, 2009, Pages: 1-20.

This paper considers an industrial procurement problem of a large volume of a single good. The procurement is implemented using volume discount auctions, where the suppliers submit nonconvex piecewise linear cost functions as bids. Such bids enable the suppliers to effectively express their economies of scale and transportation constraints. The winner determination problem faced by the buyer is an NP-hard nonlinear knapsack problem. We propose a mixed integer linear formulation for the problem which has the following exploitable primal structure: if the integer variables are fixed at some feasible values, then solving the remaining linear variables is a continuous knapsack problem. Using this feature, Benders' decomposition algorithm is developed and various techniques are proposed to accelerate the convergence of the algorithm. Experimental results with different randomly generated test data for the proposed algorithms show the efficacy of the algorithms.

N. Rama Suri and Y. Narahari. Design of an Optimal Bayesian Incentive Compatible Broadcast Protocol for Ad-hoc Wireless Networks with Rational Nodes. In:   IEEE Journal on Selected Areas in Communications, Special Issue on Game Theory in Communications Systems, , Volume 26, Number 7, September 2008, pp. 1138--1148.

This special issue is edited by J. Huang, D.P. Palomar, N. Mandayam, J. Walrand, S.B. Wicker, and T. Basar and has a foreword by Nobel Laureate John Nash. The paper introduces a paradigm shift from using the classical Vickrey-Clarke-Groves mechanisms towards using Bayesian incentive compatible mechanism, leading to substantial reduction in incentive payments and costs. Nodes in an ad hoc wireless network incur certain costs for forwarding packets since packet forwarding consumes the resources of the nodes. If the nodes are rational, free packet forwarding by the nodes cannot be taken for granted and incentive based protocols are required to stimulate cooperation among the nodes. Existing incentive based approaches are based on the VCG (Vickrey-Clarke-Groves) mechanism which leads to high levels of incentive budgets and restricted applicability to only certain topologies of networks. Moreover, the existing approaches have only focused on unicast and multicast. Motivated by this, we have proposed in this paper an incentive based broadcast protocol that satisfies Bayesian incentive compatibility and minimizes the incentive budgets required by the individual nodes. The proposed protocol, which we call BIC-B (Bayesian incentive compatible broadcast) protocol, also satisfies budget balance. We also derive a necessary and sufficient condition for the ex-post individual rationality of the BIC-B protocol.

D. Garg and Y. Narahari. Mechanism Design for Single Stackelberg Problems and Application to Procurement Auction Design. In:   IEEE Transactions on Automation Science and Engineering, Volume 5, Number 3, July 2008, Pages: 377-393. (Recipient of the 2008 Best Application Paper Award of the IEEE Transactions on Automation Science and Engineering).

Hierarchical decision making problems arise naturally in many fields including electronic commerce, supply chain management, distributed computing, transportation networks, manufacturing systems, and multi-agent systems. These problems involve interacting decision-making agents with a predefined sequence according to which decisions are taken. If the agents are rational and intelligent, these problems induce a Stackelberg game and for this reason, these problems could be called Stackelberg problems. In this paper, we look at a prominent special class of these problems called Single Leader Rest Follower (SLRF) problems. There are many emerging examples of SLRF problems: auctions with reserve prices, Internet routing, supply chain formation, resource allocation in computational grids, routing in transportation networks, scheduling in manufacturing systems, etc. The main contribution of this paper is to extend classical mechanism design to the class of SLRF problems. Classical mechanism design uses the framework of Bayesian games whereas mechanism design applied to SLRF problems has to deal with the more general Bayesian Stackelberg games. This motivates the theoretical contribution of this paper, which is to extend mechanism design to the setting of SLRF problems. The paper also offers a significant application: designing incentive compatible procurement auctions with reserve prices. Mechanism design or protocol design in the context of all the emerging applications mentioned above will be a rich avenue for applying this theory.

D. Garg, Y. Narahari, and S. Gujar. Foundations of Mechanism Design: A Tutorial. Part 1: Key Concepts and Classical Results. In:   Sadhana, Indian Academy Proceedings in Engineering Sciences, Volume 33, Number 2, April 2008, pp. 83-130.

Mechanism design, an important tool in microeconomics, has found widespread applications in modeling and solving decentralized design problems in many branches of engineering, notably computer science, electronic commerce, and network economics. The objective of this two part paper is to provide a tutorial introduction to the foundations and key results in mechanism design theory. Part 1 focuses on basic concepts and classical results which form the foundation of mechanism design theory.

D. Garg, Y. Narahari, and S. Gujar. Foundations of Mechanism Design: A Tutorial. Part 2 : Advanced Concepts and Results. In:   Sadhana, Indian Academy Proceedings in Engineering Sciences, Volume 33, Number 2, April 2008, pp. 131-174.

This is the second part of the tutorial on mechanism design. This part presents key advanced concepts and results in mechanism design.

Pankaj Dayama, and Y. Narahari. Design of Multi-Unit Electronic Exchanges through Decomposition. In:   IEEE Transactions on Automation Science and Engineering, Volume 4, Number 1, January 2007, pp. 67-74.

In this paper we exploit the idea of decomposition to match buyers and sellers in an electronic exchange for trading large volumes of homogeneous goods, where the buyers and sellers specify marginal-decreasing piecewise constant price curves to capture volume discounts. Such exchanges are relevant for automated trading in many e-business applications. The problem of determining winners and Vickrey prices in such exchanges is known to have a worst case complexity equal to that of as many as (1+m+n) NP-hard problems, where m is the number of buyers and n is the number of sellers. Our method proposes the overall exchange problem to be solved as two separate and simpler problems: (1) forward auction and (2) reverse auction, which turn out to be generalized knapsack problems. In the proposed approach, we first determine the quantity of units to be traded between the sellers and the buyers using fast heuristics developed by us. Next, we solve a forward auction and a reverse auction using fully polynomial time approximation schemes. The proposed approach has worst case polynomial time complexity and our experimentation shows that the approach produces good quality solutions to the problem.

T.S. Chandrashekar, Y. Narahari, Charles H. Rosa, Devadatta Kulkarni, Pankaj Dayama, and Jeffrey D. Tew. Auction Based Mechanisms for Electronic Procurement. In:   IEEE Transactions on Automation Science and Engineering, Volume 4, Number 3, July 2007, pp. 297-321.

Since the burst of the dot com bubble, many procurement professionals and purchasing managers have begun to question the ability of the Internet to redefine procurement processes within their firms. In this article we set out to show that this would be a misplaced sense of deja vu because the Internet along with a milieu of decision technologies based on Game Theory and Optimization is proving to be a significant tool in the hands of procurement professionals. Sans all the hype, the dot com phenomena has left behind useful ideas including that of e-platforms for on-line auctions. Building upon this core conceptual construct familiar to most procurement professionals, we set out to survey the exciting field of research this has opened up with a vast potential for immediate and gainful applications. We review the existing state-of-the-art in this field, track its recent developments and classify the models available for different procurement scenarios. We also provide pointers to areas that require further fundamental as well as applied research which calls for the attention of not just academic researchers but also practicing professionals. In our review, we present the mathematical formulations under each of the above categories, bring out the game theoretic and computational issues involved in solving the problems, and summarize the current art. We also present a significant case study of auction based e-procurement at General Motors.

C.V.L. Raju, Y. Narahari, and K. Ravi Kumar. Learning dynamic prices in multi-seller electronic markets with with price sensitive customers, stochastic demands, and inventory replenishments. In:   IEEE Transactions on Systems, Man, and Cybernetics, Part C. Special Issue on Game-theoretic Analysis and Stochastic Simulation of Negotiation Agents, Special Issue on Game-theoretic Analysis and Stochastic Simulation of Negotiation Agents, Volume 36, Number 1, January 2006, pp. 92-106.

In this paper, we use reinforcement learning (RL) as a tool to study price dynamics in an electronic retail market consisting of two competing sellers and price sensitive and lead time sensitive customers. Sellers, offering identical products, compete on price to satisfy stochastically arriving demands (customers) and follow standard inventory control and replenishment policies to manage their inventories. In such a generalized setting, RL techniques have not been applied before. We consider two representative cases: (1) no information case, where none of the sellers has any information about customer queue levels, inventory levels, or prices at the competitors; and (2) partial information case, where every seller has information about the customer queue levels and inventory levels of the competitors. Sellers employ automated pricing agents or pricebots, which use RL-based pricing algorithms to reset the prices at random intervals based on factors such as number of back orders, inventory levels, and replenishment lead times, with the objective of maximizing discounted cumulative profit. In the no information case, we show that a seller who uses Q-learning outperforms a seller who uses derivative following (DF). In the partial information case, we model the problem as a Markovian game and use actor-critic based RL to learn dynamic prices. We believe our approach to solving these problems is a new promising way of setting dynamic prices in multi-seller environments with stochastic demands, price sensitive customers, and inventory replenishments.

D.Garg, Y. Narahari, N. Viswanadham. Achieving sharp deliveries in supply chains through variance pool allocation. In:   European Journal of Operational Research, Volume 171, 2006, pp. 227-254.

Variability reduction and business process synchronization are acknowledged as key to achieving sharp and timely deliveries in supply chain networks. In this paper, we develop an approach that facilitates variability reduction and business process synchronization for supply chains in a cost effective way. The approach developed is founded on an analogy between mechanical design tolerancing and supply chain lead time compression. We first present a motivating example to describe this analogy. Next, we define, using process capability indices, a new index of delivery performance called delivery sharpness which, when used with the classical performance index delivery probability, measures the accuracy as well as the precision with which products are delivered to the customers. Following this, we solve the following specific problem: how do we compute the allowable variability in lead time for individual stages of the supply chain so that specified levels of delivery sharpness and delivery probability are achieved in a cost-effective way? We call this the variance pool allocation (VPA) problem. We suggest an efficient heuristic approach for solving the VPA problem and also show that a variety of important supply chain design problems can be posed as instances of the VPA problem. One such problem, which is addressed in this paper, is the supply chain partner selection problem. We formulate and solve the VPA problem for a plastics industry supply chain and demonstrate how the solution can be used to choose the best mix of supply chain partners.

S. Kameshwaran, Y. Narahari, C. H. Rosa, D. M. Kulkarni, and J. D. Tew. Multiattribute Electronic Procurement using Goal Programming. In:   European Journal of Operational Research, Volume 179, 2006, pp. 518-536.

One of the key challenges of current day electronic procurement systems is to enable procurement decisions transcend beyond a single attribute such as cost. Consequently, multiattribute procurement has emerged as an important research direction. In this paper, motivated by a realistic industrial procurement problem, we develop a multiattribute e-procurement system for procuring a large volume of a single item. Our system is motivated by an industrial procurement scenario for procuring raw material in automotive industries. The procurement scenario demands multiattribute bids, volume discount cost functions, inclusion of business constraints, and consideration of multiple criteria in bid evaluation. We develop a generic framework for an e-procurement system that meets the above requirements. The bid evaluation problem is formulated as a mixed linear integer multiple criteria optimization problem and goal programming is used as the solution technique. We present a numerical study for which we illustrate the proposed approach and a heuristic is proposed to handle the computational complexity arising out of the cost functions used in the bids.

Y. Narahari and Pankaj Dayama. Combinatorial Auctions for Electronic Business. In:   Sadhana (Special Issue on Electronic Commerce and Electronic Business, Volume 30, Parts 2 and 3, April/June 2005, pp. 179-212.

Combinatorial auctions have recently generated significant interest as an automated mechanism for buying and selling bundles of goods. They are proving to be extremely useful in numerous e-business applications such as e-selling, e-procurement, e-logistics, and B2B exchanges. In this article, we introduce combinatorial auctions and bring out important issues in the design of combinatorial auctions. We also highlight important contributions in current research in this area. This survey emphasizes combinatorial auctions as applied to electronic business situations.

Y. Narahari, C.V.L. Raju, K. Ravikumar, and Sourabh Shah. Dynamic Pricing Models for Electronic Business.   Sadhana (Special Issue on Electronic Commerce and Electronic Business), Volume 30, Parts 2 and 3, April/June 2005, pp. 231-255.

Dynamic pricing is the dynamic adjustment of prices to consumers depending upon the value these customers attribute to a product or service. Today's digital economy is ready for dynamic pricing, however recent research has shown that the prices will have to be adjusted in fairly sophisticated ways, based on sound mathematical models, to derive the benefits of dynamic pricing. This article attempts to survey different models that have been used in dynamic pricing. We first motivate dynamic pricing and presents underlying concepts, with several examples, and explain conditions under which dynamic pricing is likely to succeed. We then bring out the role of models in computing dynamic prices. The models surveyed include inventory based models, data driven models, auctions, and machine learning. We present a detailed example of an e-business market to show the use of reinforcement learning in dynamic pricing.

C.V.L. Raju, Y. Narahari, and K. Ravi Kumar. Learning Dynamic Prices in Electronic Markets with Customer Segmentation. In:   Annals of Operations Research, Springer, Volume 143, Number 1, March 2006, pp. 59-75.

In this paper, we use reinforcement learning (RL) techniques to determine dynamic prices in an electronic monopolistic retail market. The market that we consider consists of two natural segments of customers, captives and shoppers. Captives are mature, loyal buyers whereas the shoppers are more price sensitive and are attracted by sales promotions and volume discounts. The seller is the learning agent in the system and uses RL to learn from the environment. Under (reasonable) assumptions about the arrival process of customers, inventory replenishment policy, and replenishment lead time distribution, the system becomes a Markov decision process thus enabling the use of a wide spectrum of learning algorithms. In this paper, we use the Q-learning algorithm for RL to arrive at optimal dynamic prices that optimize the seller's performance metric (either long term discounted profit or long run average profit per unit time). Our model and methodology can also be used to compute optimal reorder quantity and optimal reorder point for the inventory policy followed by the seller and to compute the optimal volume discounts to be offered to the shoppers.

S. Biswas and Y. Narahari. Iterative Combinatorial Dutch Auctions.   Annals of Mathematics and Artificial Intelligence, Springer, Volume 44, Number 3, July 2005, pp. 185-205.

The combinatorial auction problem can be modeled as a weighted set packing problem. Similarly the reverse combinatorial auction can be modeled as a weighted set covering problem. We use the set packing and set covering formulations to suggest novel iterative Dutch auction algorithms for combinatorial auction problems. We use generalized Vickrey auctions (GVA) with reserve prices in each iteration. We prove the convergence of the algorithms and show that the solutions obtained using the algorithms lie within provable worst case bounds. We conduct numerical experiments to show that in general the solutions obtained using these algorithms are much better than the theoretical bounds.

D.Garg, Y. Narahari, N. Viswanadham. Design of Six Sigma Supply Chains.   IEEE Transactions on Automation Science and Engineering (Inaugural issue), Volume 1, Number 1, July 2004, pp. 38-57. (Recipient of the 2004 Best Application Paper Award of the IEEE Transactions on Automation Science and Engineering).

This paper builds a quite intriguing conceptual bridge between statistical design tolerancing and supply chain lead time compression. In particular, we introduce a new notion, "six sigma supply chains" to describe and quantify supply chains with sharp and timely deliveries, and develop an innovative approach for designing such networks. Informally, a six sigma supply chain is that which delivers finished products within a customer specified delivery window, with at most 3.4 missed deliveries per million. We show that the design of six sigma supply chains can be formulated as a mathematical programming problem, opening up a rich, new framework for studying supply chain design optimization problems. The proposed methodology is illustrated with the case study of a four stage, make-to-order supply chain for liquid petroleum gas.

S. Aithal, Y. Narahari, and E.S. Manjunath, Modeling, Analysis, and Acceleration of a Printed Circuit Board Fabrication Process. Sadhana, Indian Academy of Sciences Proceedings in Engineering Sciences, Volume 26, Part 5, October 2001, pp. 447-463.

A simple application of plain queueing network modeling to a practically significant problem. We looked into a PCB fabrication company at Bangalore and studied minute flow details of the process, leading to (what else) a queueing network model. After the usual analysis was done, we had some unusual findings having implications for cycle time reduction.

S. Biswas and Y. Narahari, Object Oriented Modeling and Decision Support for Supply Chain. European Journal of Operational Research, 2002, Volume 153, pp. 704-726.

This article was the 12th most downloaded paper from the Elsevier Journals website during 2002-04 with 1342 downloads in 2004. This paper describes the conceptualization and implementation of DESSCOM, a decision support system for decision making in supply chain networks, that uses object modeling as the foundation. DESSCOM has two major components: 1. A modeling infrastructure comprising a library of carefully designed generic objects for modeling supply chain elements and dynamic interactions among these elements; 2. A decision workbench that can potentially include powerful algorithmic and simulation-based solution methods for supply chain decision-making. Through the modeling infrastructure, high fidelity models of given supply chain systems can be created rapidly at any desired level of abstraction. Given a supply chain decision problem to be solved, the object oriented models created at the right level of detail can be directly transformed into problem formulations that can then be solved using an appropriate strategy from the workbench. DESSCOM has been used in modeling several benchmark supply chain systems.

This is a fascinating application of applying multiclass queueing network models to suggest lead time compression strategies in new drug discovery and development process. We use probabilistic re-entrant lines as the model and show that such a model can capture the project dynamics in drug development organizations that involve multiple, concurrent projects with contention for human/technical resources. We explore how drug development lead times can be reduced using efficient scheduling and critical mass-based resource management. The model captures important facets of any typical drug development organization, such as: concurrent execution of multiple projects, contention for resources, feedback and reworking of project tasks, variability of new project initiations and task execution times, and important scheduling issues.

A two part popular overview of the Petri net formalism and its applications. The first part provides an overview of Petri nets and presents important conceptual underpinnings of Petri net modeling. The second part describes how important system properties are modeled by Petri nets and then looks into the applications of Petri net models.

This paper originates an integrated approach for "design for quality" of industrial products using statistical and stochastic quality tools such as the Motorola Six-Sigma approach, the Xerox Holistic Probabilistic Design methodology, the Taguchi methods, and Monte-Carlo simulation. The objective of the research is to build in quality into product designs during early stages of design. This research will lead to the design of the next generation concurrent engineering platform and has generated widespread interest in the community. This paper was among eight papers short-listed for the award of the Best Paper Prize of IEEE Transactions in Robotics and Automation for the year 1999.

New product design and development constitute an important business process in any company and reducing the lead time to market is a major concern. This paper models a product design and development organization at a fairly high level of abstraction using probabilistic re-entrant lines. It is shown how lead time reduction strategies such as input control, load balancing, efficient scheduling, and variability reduction can be put to work using the queueing network model. A highlight of the paper is to argue the usefulness of "fluctuation smoothing scheduling policies" in the context of real-world product development organizations. The approach has been successfully demonstrated on a PCB design organization at Bangalore.

This paper analyzed multi-class manufacturing plants using a queueing model with a Markov modulated arrival process. The innovativeness of the paper lies in arriving at linear programs, fractional linear programs, and simple non-linear programs to optimize the system performance, starting from such a queueing model.

Asymptotic loss of a closed queueing network under a specified scheduling policy is the limiting gap between the best performance achievable by the policy and the best performance achievable by any policy. Computation of asymptotic loss can often be quite challenging. In this paper, asymptotic loss of closed re-entrant lines is studied from a computational angle and several insights are revealed that are consistent with conjectures.

This is an extension of a well-known result by Hofri and Ross who in 1987 proved the optimality of certain scheduling policies in single-server multiclass queues with setup times (under certain technical conditions). The extension applies to single-server multiclass queueing systems with setup times, where individual queues are fed by correlated interrupted Poisson streams generated in the state of a stationary modulating Markov chain. The proof uses an interesting stochastic coupling argument but is based on a technical assumption that is quite challenging to verify.

This looked into manufacturing systems where the presence of multiple part types and priority scheduling causes unpredictable effects which are best captured by transients. Uniformization was used the approach to carry out transient analysis.

Hot lots are high priority wafers in a semiconductor plant. Their presence in the plant upsets original schedules and delays scheduled work in unpredictable ways. To quantify exactly the effect of hot lots on the cycle times of regular lots is an important issue in real-time operation of wafer fabrication plants. Re-entrant lines with priority scheduling were used as the model and the classical mean value analysis technique was extended to yield a highly efficient performance prediction tool.

This paper proposes an extension to the classical re-entrant lines (proposed by P.R. Kumar) by introducing probabilistic routing in addition to re-entrancy. The extended model is tailor-made for modeling manufacturing systems with inspection stations.

Widia is a best practice machine tools company in Bangalore where a completely automated, flexible manufacturing cell was designed and commissioned in 1994. The scheduling of parts on this cell is an intricate problem, solved hitherto only by thumb-rules and experience. We looked into the data of the scheduling problem and mapped it into a standard integer programming problem, for solving which the application of Lagrangian relaxation was but natural. The insights that were gained from the problem formulation and solution structure led to practical suggestions for scheduling work in the cell.

This paper proposed efficient computational methods based on mean value analysis for analyzing the performance of intricate scheduling policies in semiconductor wafer fabrication plants. The Ph D thesis of the second author was awarded a gold medal at the Indian Institute of Science for this work.

This is a computational-oriented paper which provides an algorithmic methodology to compute first two moments of performability for fork-join queueing systems.

An engineering, yet fairly rigorous overview of dynamic scheduling of queueing networks in heavy traffic, using the Brownian approximation. A must-read for any graduate student interested in a first level exposure to this area.

This paper articulates in a comprehensive manner the importance of transient performance analysis using Markovian models of manufacturing systems. It was a trend-setter because most performance studies of manufacturing systems until then were based on steady-state analysis.

One more effective application of the PFQN-GSPN hybrid approach to performance modeling. The motivation was provided by the need to model variance of level of parallelism in parallel computing applications.

This is an up-to-date (up to 1991) overview of stochastic modeling approach to manufacturing systems performance evaluation.

Markov chains with absorbing states are a natural model for FMSs with deadlocks. Performance analysis of this class of FMSs entails first passage time distributions to be computed. This is the main idea of this paper.

Product form queueing networks are highly tractable but entail certain restrictive assumptions to be made while modeling (for example, no priorities, no passive resources, only FCFS scheduling, only certain special probability distributions, etc.). Stochastic Petri nets, on the other hand, can capture all of these features but can lead to the curse of dimensionality. Combining these two approaches (product form QNs and SPNs) using a decomposition setting enables to make the best of both the worlds. This paper explores this idea in the context of FMS performance modeling.

This paper articulated for the first time effective strategies for deadlock handling in highly automated manufacturing plants. Deadlocks represent a highly undesirable phenomenon in distributed, concurrent systems. The paper originates systematic and effective ways of preventing and avoiding deadlocks in complex manufacturing plants through a Petri net modeling approach. The paper's unique contribution was to establish a conceptual bridge between deadlock research in computer operating systems and deadlock research in automated manufacturing systems. The techniques were applied on a real-world factory of General Electric in Pennsylvania. The paper has an impressive citation record of more than 20 citations in International Journals.

This is a survey article that provides a unifying overview of three approaches to performance modeling of flexible manufacturing systems: Markov models; product form and non-product form queueing network models; and stochastic Petri net models.

Until 1986, Petri net modeling of manufacturing systems emphasized qualitative modeling (boundedness, liveness, fairness, reversibility, etc.). This paper was one of the first efforts in looking at quantitative performance analysis using using the GSPN (Generalized Stochastic Petri Nets) formalism of Azmone Marsan, Balbo, and Conti.

FTMP (Fault-Tolerant MultiProcessor) was a research effort at NASA in the early eighties. In this paper, we showed that stochastic Petri nets could be used to capture several non-product form features that arise in the modeling of the performance of this architecture. The result is it leads to exact, accurate, and credible estimation of performance of this interesting fault-tolerant architecture.

Y. Narahari and N. Viswanadham, A Petri net approach to the modeling and analysis of flexible manufacturing systems. Annals of Operations Research, Vol. 3, 1985, pp. 449--472.

This was my first paper and also one of the most cited papers in the area. The paper proposes a Petri net approach to modeling large scale manufacturing systems using an elegant bottom up approach. The approach is founded on a very simple result that we proved for computing the place invariants of a union of individual Petri net models in terms of the place invariants of the individual nets.