Markov Chains: Models, Algorithms and Applications (eBook)

Wai-Ki Ching, Michael K. Ng (Autoren)

eBook Download: PDF

2006
XIV, 208 Seiten
Springer US (Verlag)
978-0-387-29337-0 (ISBN)

Infos

Markov chains are a particularly powerful and widely used tool for analyzing a variety of stochastic (probabilistic) systems over time. This monograph will present a series of Markov models, starting from the basic models and then building up to higher-order models. Included in the higher-order discussions are multivariate models, higher-order multivariate models, and higher-order hidden models. In each case, the focus is on the important kinds of applications that can be made with the class of models being considered in the current chapter. Special attention is given to numerical algorithms that can efficiently solve the models.

Therefore, Markov Chains: Models, Algorithms and Applications outlines recent developments of Markov chain models for modeling queueing sequences, Internet, re-manufacturing systems, reverse logistics, inventory systems, bio-informatics, DNA sequences, genetic networks, data mining, and many other practical systems.

Inhalt

Contents 7
Preface 13
1 Introduction 15
1.1 Markov Chains 15
1.2 Continuous Time Markov Chain Process 30
1.3 Iterative Methods for Solving Linear Systems 33
1.4 Hidden Markov Models 46
1.5 Markov Decison Process 47
2 Queueing Systems and the Web 50
2.1 Markovian Queueing Systems 50
2.2 Search Engines 60
2.3 Summary 71
3 Re-manufacturing Systems 73
3.1 Introduction 73
3.2 An Inventory Model for Returns 74
3.3 The Lateral Transshipment Model 78
3.4 The Hybrid Re-manufacturing Systems 80
3.5 Summary 87
4 Hidden Markov Model for Customers Classification 88
4.1 Introduction 88
4.2 Parameter Estimation 89
4.3 Extension of the Method 90
4.4 Special Case Analysis 91
4.5 Application to Classi.cation of Customers 93
4.6 Summary 96
5 Markov Decision Process for Customer Lifetime Value 97
5.1 Introduction 97
5.2 Markov Chain Models for Customers’ Behavior 99
5.3 Stochastic Dynamic Programming Models 102
5.4 Higher-order Markov decision process 112
5.5 Summary 116
6 Higher-order Markov Chains 120
6.1 Introduction 120
6.2 Higher-order Markov Chains 121
6.3 Some Applications 130
6.4 Extension of the Model 138
6.5 Newboy’s Problems 143
6.6 Summary 148
7 Multivariate Markov Chains 149
7.1 Introduction 149
7.2 Construction of Multivariate Markov Chain Models 149
7.3 Applications to Multi-product Demand Estimation 156
7.4 Applications to Credit Rating 158
7.5 Applications to DNA Sequences Modeling 161
7.6 Applications to Genetic Networks 164
7.7 Extension to Higher-order Multivariate Markov Chain 175
7.8 Summary 177
8 Hidden Markov Chains 178
8.1 Introduction 178
8.2 Higher-order HMMs 178
8.3 The Interactive Hidden Markov Model 190
8.4 The Double Higher-order Hidden Markov Model 194
8.5 Summary 196
References 197
Index 208

Textauszug

3 Re-manufacturing Systems (p. 61-62)

3.1 Introduction

In this chapter, the inventory controls of demands and returns of single-item inventory systems is discussed. In fact, there are many research papers on inventory control of repairable items and returns, most of them describe the system as a closed-loop queueing network with constant number of items inside [78, 158, 201]. Disposal of returns [127, 200] is allowed in the models presented here. The justi.cation for disposal is that accepting all returns will lead to extremely high inventory level and hence very high inventory cost. Sometimes transshipment of returns is allowed among the inventory systems to reduce the rejection rate of returns. Other re-manufacturing models can be found in [117, 200, 196] and good reviews and current advances of the related topics can be found in [23, 84, 92, 132, 157].

As a modern marketing strategy to encourage the customers to buy products, the customers are allowed to return the bought product with full refund within a period of one week. As a result, many customers may take advantage of this policy and the manufacturers have to handle a lot of such returns. Very often, the returns are still in good condition, and can be put back to the market after checking and packaging. The .rst model we introduce here attempt to model this situation. The model is a single-item inventory system for handling returns is captured by using a queueing network. In this model, the demands and the returns are assumed to follow two independent Poisson processes. The returns are tested and repaired with the standard requirements. Repaired returns will be put into the serviceable inventory and non-repairable returns will be disposed. The repairing time is assumed to be negligible. A similar inventory model with returns has been discussed in [110]. However, the model in [110] includes neither the replenishment costs nor the transshipment of returns. In this model, the inventory system is controlled by a popular (r,Q) continuous review policy. The inventory level of the serviceable product is modelled as an irreducible continuous time Markov chain.

The generator matrix for the model is given and a closed form solution for the system steady state probability distribution is also derived. Next, two independent identical inventory systems are considered and transshipment of returns from one inventory system to another is allowed. The joint inventory levels of the serviceable product is modelled as a twodimensional irreducible continuous time Markov chain. The generator matrix for this advanced model is given and a closed form approximation of the solution of the system steady state probability distribution is derived. Analysis of the average running cost of the joint inventory system can be carried out by using the approximated probability distribution. The focus is on the inventory cost and the replenishment cost of the system because the replenishment lead time is assumed to be zero and there is no backlog or loss of demands. It is shown that in the transshipment model, the rejection rate of the returns is extremely small and decreases signi.cantly when the re-order size (Q + 1) is large. The model is then extended to multiple inventory/return systems with a single depot. This kind of model is of particular interest when the remanufacturer has several re-cycling locations. Since the locations can be easily connected by an information network, excessive returns can be forwarded to the nearby locations or to the main depot directly. This will greatly cut down the disposal rate. The handling of used machines in IBM (a big recovery network) serves as a good example for the application of this model [92]. More examples and related models can be found in [92, pp. 106-131].

Finally, a hybrid system consists of a re-manufacturing process and a manufacturing process is discussed. The hybrid system captures the remanufacturing process and the system can produce serviceable product when the return rate is zero.

The remainder of this chapter is organized as follows. In Section 3.2, a single-item inventory model for handling returns is presented. In Section 3.3, the model is extended to the case that lateral transshipment of returns is allowed among the inventory systems. In Section 3.4, we discuss a hybrid remanufacturing system. Finally, concluding remarks are given in Section 3.5.

Produkt-Details

• Erscheint lt. Verlag: 5.6.2006
• Reihe/Serie: International Series in Operations Research & Management Science
• Reihe/Serie: International Series in Operations Research & Management Science
• Zusatzinfo: XIV, 208 p. 18 illus.
• Verlagsort: New York
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Statistik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
• Themenwelt: Technik
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Logistik / Produktion
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Planung / Organisation
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Unternehmensführung / Management
• Schlagworte: algorithms • Business and management applications • Markov Chain • markov chains • Markov decision process • Markov model • Optimization models • Stochastic Networks
• ISBN-10: 0-387-29337-X / 038729337X
• ISBN-13: 978-0-387-29337-0 / 9780387293370