Optimal solution for a two-product dynamic scheduling problem in a just-in-time environment

This paper deals with a new dynamic scheduling problem which occurs in just-in-time environments. A production system must perform products in order to deliver them without any delay. A production order arrives in constant interval time and the corresponding product must be delivered a fixed number of time units later. The probability of appearance for each product is known. An inventory is available to store finished products. The objective is to schedule the orders in order to minimize the mean number of production type changeovers. The Markov decision process theory guarantees that an optimal scheduling policy exists and can be computed. Unfortunately, this approach is not efficient when the number of product types is large (resp. the storage level, resp. the delivery delay). We propose an optimal method when the number of product types is two and we show that this method becomes inefficient when the number of product types is strictly greater.