The x,T -rule

By examing the optinial policy closely in some examples, we observed the following two properties. Firstly, the decision whether a production takes place or not, depends almost exclusively on the number of orders for the first period (rO and not on the required deliveries for later periods. Secondly, for a given demand distribution, the number of periods for which the orders are produced is nearly always the same. An example may illustrate these properties. 

Consider a situation with a maximum lead time of 4 periods, penalty costs p=3, holding costs h =, set-up costs s=6.5 and a binary demand per period d,i = l-dio=0.5 for i=l,2,3,4. The number of possible order states is limited in this example and therefore we can determine the optimal policy. The resulting optimal policy has the following features  

2) The optimal action if r i S2 is always a =2, produce the required deliveries for the first two periods, except for the order states (2,3,0,0), (2,3,0,1), (2,3,1,0) and (2,3,1,1). In these four states we do not produce. The probability of finding the demand in one of these states is quite small. 

Also in other examples, we observed the same two properties. These two elements seem to be very important if we want to look for a production rule which is simple, but close to optimal. Therefore, we shall propose the following approach, ff the number of orders required for the first period or one of the earlier periods, ri is smaller than a decision variable x, then we do not produce during that period. If ri is equal to or larger than x, then we will produce during that period and we produce all orders with a residual lead time of T periods or less, where T is also a decision variable. Decisions on the production are made at the end of every period, so production may take place less than T periods after the previous one. This rule will be called the (x,T)-nile. 

In the unconstrained capacity situation it is rather easy to determine the average costs for given values of x and T. The optimal values for x and T can be found by computing the average costs per period for several values of x and T. First we will show how this calculation is done. Afterwards two properties will be given, which can help us determine the optimal values of x and T. 

---

The (x,T)-rule however, offers a very simple decision rule with known average costs. Especially if we want to analyse or change a situation, the (x,T)-nile must be preferred. As a basis for a production rule in a more complex situation the SM-rule and (x,7)-rule can both be useful, as we will see later on. The use of the WW-rule in more complex situations will be restricted to an extended version of the WW(l)-rule. In Dellaert (1987) some examples of the use of the (x,r)-rule for making agreements with clients are given. In that paper we also present simple rules for the uncapacitated situation to improve the (x,7)-rule until it is nearly optimal and a method to estimate the average costs of the SM-rule. 

The new state vector r does not provide the necessary information for a good use of the optimal policy and for the Wagner-Whitin approach. For these rules it is indeed necessary to know the order state vector for each of the different priorities separately. The (x,T)-rule and the Silver-Meal approach can be used straightforwardly in this situation. Of course the fixed cycle production rule n (cf. (4.2.10)) can also be used without any complications. The use of these rules is now exactly the same as described in 4.2.4.2. and 4.2.4.4. 

In Property 4.2 we want to give limits for the optimal T-value for a given value of x. Let qij(K) be the -value based on the (x,AT)-rule and let Pij(K) be the probability that between two production periods the state (j,y) is visited, if we do not limit the state space in the n mc-direction. For these Pij(K) we thus allow i. Let cx is the average cost in the K-th period after the last production period, if we use the (x,AT+l)-rule and if we do not produce during that period. 

Suppose is an arbitrary upper bound for minimal average costs of the optimal ( t,7>-nile, for instance the average costs of the (x,7>-rule for another pair. If 4.2.26 holds, we have that... 

In order to determine the best actions in every situation we will consider the two heuristics we preferred in Section 4.2. the Silver-Meal-like production rale and the (x,T)-rale. The use of the optimal policy becomes much more complicated than in the previous section, because of the introduction of a more complicated state which has to include the population size and therefore more complicated transition probabilities, all together leading to a production rule which can hardly be of practical use. In the heuristics, the penalty costs again are a basic element. The penalty costs are now defined as the expected volume of missed revenues as a result of departed customers if an order is delivered one period too late. If the revenues and the stochastic processes which govern the decrease and increase of the population size are known, the penalty costs can be estimated in a simple way and the heuristics can be used in the same way as in Section 4.2. We will explain this by stud3dng an example. 

In Table 4.3. we will also give the simulation results for the (x,7)-rule and the Silver-Meal approach, once with the decisions based on the real population size and once with the decisions based on the average population size. The simulation of the production rules with the decisions based on the average population size will be denoted by inc. (x,T) simulation and inc. SM simulation respectively. We will also perform a simulation with the cyclic strategy it, in which we produce evoy T periods. 

Next to the cyclic production rule, the (x,T)-nile has proven to be such a simple and fast rule in the uncapacitated situation. The (x,7)-rule in the form in which it has been described in 4.2.4., should be adapted a bit to the extra problems of a restricted capacity and the variety of types competing for the same capacity on one machine. We will deal with these problems in a simple way and the resulting production rule will be called the extended (x,7>-rule. In order to judge the performance of this extended (x,7>-rule, we want to compare it with a more complex production rule which contains several elements of well-known production mles. 

One production rule that allows an almost exact calculation of the performance is the rule in which we produce every product type according to a separate (x THule, independent of the production of other types. If the capacity restrictions are tight ot if the costs for working overtime are not very small, this production rule will not yield cry satisfying results. Therefore we will add some of the ideas from Chapter S to this rule, in order to make it more sensible. We will call the resulting production rule the multi (x,T)-rule. 

The analysis of this production rale will be done in much the same way as the analysis of the uncapacitated (x,T)-rule. For every type of product we consider a Markov chain in which the state is given by the number of penalty points. The interaction between the different states is found in the transition probabilities. We will consider the situation in which there are orders with different priorities. Every order has a fixed... 

In the situation with no capacity restrictions we have considered a number of production rules inspired by two well-known heuristics, the Silver-Meal heuristic and the Wagner-Whitin heuristic, and we have introduced a new, simple rule the (x,7>-rule. In this 0t,7>-rule we do not produce if the number of late orders will be less than X. Otherwise we produce all orders that have to be delivered, according to their due date, within T periods. The x value and the T value are decision variables. If costs... 

There is a number of algorithms to solve equations (1) and (2) that differ appreciably in their properties which are beyond the scope of the present article. In the discussion below we use the velocity Verlet algorithm. However, better approaches can be employed [2-5]. We define a rule - F X t), At) that modifies X t) to X t + At) and repeat the application of this rule as desired. For example the velocity Verlet algorithm ( rule ) is ... 

---