1

there

I am a bit confused about forming the transition matrix for this inventory problem. Suppose that $X(n)$ is amount of the item in the inventory at the end of the each period (day).

One thing that is quite straightforward is to consider $S=\{..,-3,-2,-1,0,1,2,3,4,5\}$.

However, it could be the case that we should distinguish state $2$, $3$ and $4$ during which we have no production rate (Machine is off).

What is the best way to form the transition matrix?

Tnx

Problem:

Consider a machine that produces two items per day. The probability that an item is nondefective is $0.8$. Quality of successive items are independent. Defective items are thrown away instantly. The demand is one item per day and any demand that cannot be satisfied immediately is lost. Suppose the following operating policy is adopted. The machine is turned off as soon as the inventory at the end of a day reaches $5$ items. It remains off until the inventory at the end of a day reduces to $1$ item, at which point the machine is tuned on again.

Majid Biazaran
  • 85

1 Answers1

1

The number of states is more than simply the end-of-day inventory count {0,1,2,3,4,5} because we must include the machine's On/Off state as well. We will adopt the notations On(k) and Off(k) for the corresponding machine state + inventory count.

There is no disaster if we include states that cannot be attained (by valid transitions). In some cases we may include them in a model as states that might exist at initialization but never after.

That said, if we want to be parsimonious, we will formulate the minimum number of states needed for the problem. Although the comments add a new element, "find the cost of unsatisfied demand," I will not attempt to address that on top of the original Question, forming the transition matrix, except with the following two remarks:

It seems plausible that the state On(0) might be not only an initial state but one that is reachable afterward. E.g. the inventory reaches 1 at the end of a day and the machine turns on. However the next day's two items produced are defective and immediately discarded. The result, after satisfying a demand for the one item in inventory, is On(0) at the end of the next day. Since demand is limited to one item per day, the only way for unsatisfied demand to occur with the machine on is in the state On(0).

A state Off(0) is more problematic. A literal reading of the problem does not provide any means for turning the machine from off to on unless the end-of-day inventory is 1. Any demand occurring in the Off(0) would go unsatisfied, and the machine would never get turned back on, making this an absorbing state (if the problem is read literally). However it also appears that Off(0) is not reachable from another state, for the following reason.

When the machine is off, the state transitions are deterministic. There is always a decrement of the end-of-day inventory count, unless for the sake of completeness an Off(0) state is included. But assuming the machine is off because it reached an end-of-day inventory count of 5, the state transitions will go Off(5) -> Off(4) -> Off(3) -> Off(2) with probability 1, followed necessarily by On(1).

With a bit of cleverness we see that the off states can be omitted, at least with regard to any treatment of unsatisfied demand, because while there are uncertainties when the machine is on as to defectiveness of the two-per-day items produced, there is no uncertainty about transitions when the machine is off.

A truly minimum set of sets to model is then {On(0),On(1),On(2),On(3),On(4)}.

Going from an end-of-day state On(k), the rules generally allow for various transitions at next end-of-day to On(k-1), On(k), and On(k+1), except that (a) from On(0) no further reduction in end-of-day inventory count is allowed, and (b) from On(4), instead of possible further increase in inventory we may (over five days) make transition to On(1).

The transition matrix entries are not difficult to work out; the chances of 0,1,2 nondefective items being produced in a day is a standard calculation.

hardmath
  • 37,015
  • Thank you very much, @hardmath, for your great detailed description and critical remarks you made. – Majid Biazaran Dec 05 '13 at 17:23
  • Bear in mind I did not have "state 5" but I make a similar observation about On(4) going to On(1). – hardmath Dec 05 '13 at 21:20
  • In other part of question, it is required to calculate the long-run fraction of time that the machine is off. I think if we consider state 3 as an absorbing state and rearrange the matrix, the desired value would be the entry corresponding to state 4 and 1 in $inv(I-Q)$. Am I right, since the value would be 0.64, exactly the transition probability of going to state 1, given we are in state 4. Could it be rational? – Majid Biazaran Dec 06 '13 at 12:13
  • You also ask (in a comment on the Question itself) about the "cost of unsatisfied demand". Both can be addressed by first finding the long-run "equilibrium" distribution of states, which I think you are familiar with. However I follow what it means to "consider state 3 as an absorbing state". None of my states are absorbing. – hardmath Dec 06 '13 at 12:32
  • In the literature, it is called "Steady-state" distribution. I found it actually which is 0.2 for each state, through solving balance equations. This is my Transition Matrix: P=[0.36,0.64,0,0,0;0.04,0.32,0.64,0,0;0,0.04,0.32,0.64,0;0,0,0.04,0.32,0.64;0,0.64,0,0.04,0.32] How do you interpret the fraction of time that machine is off in terms of states and transition? – Majid Biazaran Dec 06 '13 at 12:52
  • What I meant by absorbing state, is since there is a probability to go to other state rather than 1, given we are in state 4, we have to make state 3 an absorption and find the expected occupancy time of state 1, given we start from state 4. – Majid Biazaran Dec 06 '13 at 12:58
  • I'm inclined to rollback your revisions. As a community policy matter we want Questions not to grow extra issues, but to instead open new Questions (that should of course link back to any early Question, so Readers can benefit from the information there). Is it agreeable to frame a new Question about those cost aspects? – hardmath Dec 06 '13 at 13:50
  • Job's done, sir. I intended to exhibit complete scope of the problem, since the transition matrix should be formed with respect to required values. – Majid Biazaran Dec 06 '13 at 14:39
  • @MajidBiazaran: If you need help formatting the new Question, rough it out and I can help with the Markdown/MathJax details! – hardmath Dec 07 '13 at 11:19