Accelerating the Value Iteration Algorithm on the Stochastic Economic Lot Scheduling Problem for Continuous Multi-Grade Production

In this master thesis production scheduling is researched and specifically a variant of the Stochastic Economic Lot Scheduling Problem (SELSP) is addressed (Liberopoulos et al.) (2009) [11]. The SELSP is used to model a single machine with restricted productiveness, used to produce different products under random stationary demands. The products are stored in a warehouse with limited storage capacity. It is assumed that spillover, lost sales and switchover costs and times occur. SELSP together with the Stochastic Capacitated Lot Sizing Problem (SCLSP) constitute the two variants of the Stochastic Lot Scheduling Problem (SLSP) (Sox et al.) (1999) [12]. While SELSP is more suitable to model the continuous multi-product production of process industries where the different grades of a product are produced ceaselessly, SCLSP is suitable for the rest of the industries where the production takes place in a clearly discrete manner. The SELSP variant under consideration in this thesis, is modeled as a Markov Decision Process (MDP). Hatzikonstantinou (2009) [3] finds optimal policies for the SELSP via the Standard Value Iteration Algorithm (SVIA). The outcome is satisfying in terms of the optimal policy’s quality, but not encouraging in terms of the computational time needed to find such a policy, especially when the state space grows bigger. This master thesis focuses in algorithms, heuristic procedures and techniques that efficiently find optimal and -optimal policies, improving on the same time the SVIA’s number of iterations and the needed computational CPU time. The algorithms that are adopted to reduce the computational effort are the Minimum Difference Criterion Value Iteration Algorithm (MDCVIA) which uses a Dynamic Relaxation Factor (DRF) to accelerate the procedure and the K-step MDCVIA which enhances with K-value oriented steps per iteration the MDCVIA. A heuristic procedure is developed which performs Graphical Action Elimination (GAE), based on the obtained policy. The aforementioned MDCVIA and its version enhanced with GAE are compared against SVIA on realistic experiments, to conclude that they confront more effectively - when compared to SVIA - the well known curse of dimensionality. In Chapter 2 the difference between process and discrete manufacturing is described along with the definition of the SELSP for continuous multi-grade production. Chapter 3 contains a literature review on the SELSP. In Chapter 4, after the presenting MDPs and SVIA, the effort focuses on the algorithmic theory used to enhance the SVIA’s effectiveness on solving large-scale MDPs. Chapter 5 describes the SELSP formulation as a discrete time MDP. Chapter 6 follows with the description of a heuristic based on Action Elimination (AE). In Chapter 7 numerical experiments, comparisons and results are presented and conclusions are drawn. Finally, in Chapter 8 a short discussion on directions for further research is included.