The economic lot and delivery scheduling problem: common cycle, rework, and variable production rate

The economic lot and delivery scheduling problem is to simultaneously determine the production sequence of several assembly components at a supplier and the delivery interval of those components to the customer. The customer, an assembly facility, is assumed to use the components at a constant rate. The objective is to find the production sequence and delivery interval that minimize the holding, setup, and transportation cost for the supply chain. Previous solutions to the problem assume a constant production rate for each component and that all components are of acceptable quality. These assumptions ignore volume flexibility and quality cost. Volume flexibility permits a system to adjust the production rate upwards or downwards within wide limits. Also, component quality may deteriorate with larger lot sizes and decreased unit production times. In this paper, we develop an algorithm for solving the economic lot and delivery scheduling problem for a supplier using a volume flexible production system where component quality depends on both lot sizes and unit production times. We test the performance of the algorithm and illustrate the models with numerical examples.     

The economic lot and delivery scheduling problem: models for nested schedules

We investigate the problem of simultaneously determining schedules for the production of several assembly components at a captive supplier and delivery of those components to the customer. We consider situations in which production economies of scale in the form of setup costs and/or setup times make it desirable for the supplier to produce in batches that are larger than the desired order quantity of the customer. The objective is to minimize the average cost per unit time of transportation, inventory at both the customer and the supplier, and, where applicable, setup costs.

We develop a heuristic solution procedure and a lower bounding approach for this problem. We also report experimental results that indicate that the heuristic provides solutions close to the lower bound in most instances. Our results provide a means to answer the often-asked question of whether just-in-time suppliers are (or should be) asked to hold inventory for their customers, and the question of how much setup costs and setup times need to be reduced so that the suppliers no longer need to hold that inventory.     

The economic lot scheduling problem: a survey

This paper aims to present a literature review and an analysis of research works in the field of economic lot scheduling problem (ELSP) based on the related articles published since 1958. Because of ELSP complexity, there are a noticeable number of studies that use algorithms based on different approaches in order to deliver a feasible solution. Therefore, the contribution of this paper is to introduce a taxonomic classification based on scheduling policies and solving methodologies proposed by authors. Also, a simple data analysis is carried out to understand the evolution of ELSP and to identify potential research areas for further studies. The results show that there is an increasing trend in this topic but there are still much needs from industrial manufacturing systems. This study is expected to provide a comprehensive list of references for other researchers, who are interested in ELSP research.     

The economic lot scheduling problem: a content analysis

The paper at hand addresses the Economic Lot Scheduling Problem (ELSP), which is concerned with finding a feasible and cost-minimal production schedule for multiple items produced in lots on a single machine. The ELSP started to attract the attention of researchers in the 1950s, where the focus was primarily on the development of simple heuristics for solving the problem. Over the subsequent decades, this topic has frequently been addressed in the literature, with the subject of research being the development of new scheduling policies or solution procedures or extensions of the scope of the original model. To date, a large number of journal articles has been published on the ELSP and its model variants. To identify key research themes, publication patterns and opportunities for future research, the paper at hand applies a content analysis to a sample of 242 papers published on the Economic Lot Scheduling Problem. The results of the content analysis indicate that prior research on this topic had a strong focus on the development of solution methodologies, and that several aspects that are directly connected to lot sizing and scheduling have not attracted much attention in research on the ELSP yet, such as, for example, energy cost and sustainability.     

A time-varying lot sizes approach for the economic lot scheduling problem with returns

We consider the economic lot scheduling problem with returns by assuming that each item is returned by a constant rate of demand. The goal is to find production frequencies, production sequences, production times, as well as idle times for several items subject to returns at a single facility. We propose a heu ristic algorithm based on a time-varying (TV) lot sizes approach. The problem is decomposed into two distinct portions: in the first, we find a combinatorial part (production frequencies and sequences) and in the second, we determine a continuous part (production and idle times) in a specific production sequence. We report computational results that show that, in many cases, the proposed TV lot sizes approach with consideration of returns yields a relatively minor error.     

The effect of the stabilization period on the economic lot scheduling problem

The Economic Lot Scheduling Problem (ELSP) is the problem of scheduling production of several items in a single facility, so that demands are met without stockouts or backorders, and the long run average inventory carrying and setup costs are minimized. One of the general assumptions in the ELSP is that the yield rates of a given manufacturing process are constant, or 100%, after setup. However, this assumption may not be true for certain manufacturing processes, in which the yield rates are quite low just after setup, and then increase over time. This period is called a stabilization period and yield rates gradually increase during this period until they reach the target rates, which are set empirically or strategically. The purpose of this paper is to clarify the effect of the stabilization period by applying the stabilization period concept to the ELSP, which has been widely applied to many production systems. In this paper, the problem is tackled in three stages: Firstly, we formulate a model and develop an algorithm, which provides a lower bound for a minimum cost. Secondly, we develop a heuristic procedure using the time-varying lot size approach. Finally, we solve a special case of the ELSP to find an upper bound using the common cycle approach.     

An artificial bee colony algorithm for the economic lot scheduling problem

In this study, we present an artificial bee colony (ABC) algorithm for the economic lot scheduling problem modelled through the extended basic period (EBP) approach. We allow both power-of-two (PoT) and non-power-of-two multipliers in the solution representation. We develop mutation strategies to generate neighbouring food sources for the ABC algorithm and these strategies are also used to develop two different variable neighbourhood search algorithms to further enhance the solution quality. Our algorithm maintains both feasible and infeasible solutions in the population through the use of some sophisticated constraint handling methods. Experimental results show that the proposed algorithm succeeds to find the all the best-known EBP solutions for the high utilisation 10-item benchmark problems and improves the best known solutions for two of the six low utilisation 10-item benchmark problems. In addition, we develop a new problem instance with 50 items and run it at different utilisation levels ranging from 50 to 99% to see the effectiveness of the proposed algorithm on large instances. We show that the proposed ABC algorithm with mixed solution representation outperforms the ABC that is restricted only to PoT multipliers at almost all utilisation levels of the large instance.     

A Stepwise partial enumeration algorithm for the economic lot scheduling problem

This paper presents a stepwise partial enumeration algorithm for determining the economic lot schedule of a multiproduct single facility system on a repetitive basis. The algorithm is based on a simple “sufficient feasibility” test. The algorithm starts from a feasible schedule determined from the common cycle solution and continues stepwise partial enumerations to improve the schedule until no appreciable improvement occurs. Performance of the algorithm is demonstrated by solving six problems recently solved by Haessler. The algorithm gives better or equal solutions to the problems.     

A practical heuristic for the group technology economic lot scheduling problem

Automated Guided Vehicle (AGV) systems are complex to design and to implement. Inefficiencies become difficult to avoid or even to control. This paper presents the theory behind a novel agent based AGV controller that aims to control the flow of AGVs in an effective manner and, therefore, overcome the inefficiencies that can be found in complex designs. Agents are simple entities that interact with other agents to produce an emergent behaviour that is not explicitly programmed into them. The AGV controller presented uses agents as traffic managers to allow access to points and segments in the guide path. Each agent has a rule base that it uses to assess the enquiries that it receives from an AGV. Each enquiry is evaluated only at the smallest possible part of the guide path rather than the entire guide path. AGVs are then able to allocate segments and points on their paths depending on the result of each enquiry. Simulation experiments were used to test the controller and an overview is presented.     

Effect of learning and forgetting on economic lot size scheduling problem

The paper determines the sequence of set-ups and quantity to produce in each setup if two products are to be produced on a single facility, considering the effects of learning and forgetting. The cost expression which is to be minimized, consists of three factors: set-up cost, carrying cost and the cost of idle facility. A solution procedure is developed and the analysis is extended for the n-product system.     

A comparison of solution approaches for the fixed-sequence economic lot scheduling problem

The economic lot scheduling problem (ELSP) has received much attention recently. The general version of the problem has a non-convex objective function, so it is difficult to find truly optimal solutions. We examine the three most popular heuristic approaches to the fixed-sequence ELSP. Each approach imposes one or both of these simplifying constraints: the zero-switch constraint (production of a part is started only when its inventory is depleted) and the equal-lot constraint (the lot size of a given part is constant through time). We provide a formulation that clarifies the relationships between the general problem and the three constrained versions, and compare their performances in a computational study.     

Economic lot and supply scheduling problem: a time-varying lot sizes approach

We study the economic lot and supply scheduling problem (ELSSP) that arises in the distribution and manufacturing industries. The ELSSP involves the simultaneous scheduling of end-item production and inbound transportation of input materials over an infinite time horizon to minimise the average costs of inventory, production set-up and transportation. We present a new methodology based on a time-varying lot sizes approach for the ELSSP. We also provide computational experiments showing that the developed algorithm outperforms the existing heuristic for improved integrated scheduling.     

A basic period approach to the economic lot scheduling problem with shelf life considerations

Almost all the research on the economic lot scheduling problem (ELSP) considering limited shelf life of products has assumed a common cycle approach and an unrealistic assumption of possibility of deliberately reducing the production rate. In many cases, like in food processing industry where limited shelf life for products is common, changing the production rates is not allowed at all because it may result in products with poor quality. In this paper, we allow products to be produced more than once in a cycle and do not allow reducing production rates. We present a modification to the Haessler's basic period procedure to account for the shelf life. Proposed ‘branch-and-bound like’ procedure exploits these extra constraints to efficiently achieve a feasible solution. Numerical examples are presented to show that our approach outperforms common cycle approach with shelf life considerations.     

Heuristics for the N-product,M-stage,economic lot sizing and scheduling problem with dynamic demand

This paper presents a new composite heuristics approach for solving the N-product, M-stage lot sizing and scheduling problem with dynamic demands and limited production capacity. The first phase of these composite heuristics aims at finding a feasible solution. This solution is such that for each period and for each product, the lot size equals the net demand of the considered period plus the demand of a number of upcoming periods. If capacity does not satisfy all demands of a given period, we try to find earlier periods where we can produce the missing units. The second phase is an improvement procedure which recursively attempts to move back each lot, provided that it is both more economical to do so and capacity feasible. We also provide two variants of this heuristic to handle the case where production capacity can be increased by using overtime. Overtime is a usual practice in real life which, in many cases, allows a reduction of the overall cost. The first variant constructs the initial solution without recourse to overtime and introduces overtime only during the solution improvement phase. The second one considers overtime during both the first and second phases. The performance of the proposed heuristics is numerically assessed and the most efficient ones are identified.     

Time-variant lot sizing models for the warehouse scheduling problem

We consider the problem of scheduling the delivery of n products into a warehouse with limited space under the assumptions of continuous demands at constant rates, infinite horizon, and no backorders. The delivery schedule is described by a cyclic schedule with time-varying lot sizes. The order frequencies and the order sequence are assumed to be given. We formulate a linear program that determines delivery times relative to the cycle length to minimize the relative maximum space used and show that the optimal solution is characterized by filling the warehouse at each order. We bound the optimal solution by using a worst-case analysis and give conditions under which the linear program has the same optimal solution as a quadratic program that minimizes the holding cost. Under general conditions, we derive a bound on the cost penalty that results when using the optimal solution of the linear program as a solution to the quadratic program. Finally, we complete a solution to the nonlinear lot-sizing model by determining the best cycle length corresponding to the solution to the linear program and present a bound on a quality of this solution.     

A note on “The general lot sizing and scheduling problem”

Fleischmann and Meyr (1997) develop a model for the lot sizing problem with sequence dependent setup costs. In this note we show that this model is limited to the case where production state between two consecutive periods is conserved only if the available capacity of the preceding period exceeds the minimum batch quantity. We generalize the model by modification.This complete issue was revised and published online in November 2004. The previous version contained a false date. Correspondence to: Haldun Süral     

Accounting for idle capacity cost in the scheduling of economic lot sizes

This paper considers the issue of idle capacity cost in determining economic lot sizes. Two mathematical models are developed for the economic lot scheduling problem (ELSP). In Model I, the ELSP with fixed production rates is formulated under both the common cycle and time-varying lot sizes approaches. The associated constrained optimization problem in the time-varying lot sizes approach is reduced to solving a parametric quadratic programming problem. In Model II, the modified ELSP (or MELSP) is treated with variable production rates and unit production cost of each item as a function of its production rate. An upper bound and a lower bound on the MELSP are derived. Lot-sizing decisions of the proposed models are obtained and their dependencies on the idle capacity cost are examined with numerical examples.     

Intelligent dynamic control of stochastic economic lot scheduling by agent-based reinforcement learning

This paper addresses a stochastic economic lot scheduling problem (SELSP) for a single machine make-to-stock production system in which the demands and the processing times for N types of products are random. The sequence-independent setup times and costs are explicitly considered and may have different values for various types of products. The SELSP is to decide when, what, and how much (the lot size) to produce so that the long-run average total cost, including setup, holding and backorder costs, is minimised. We develop a mathematical model and propose two reinforcement learning (RL) algorithms for real-time decision-making, in which a decision agent is assigned to the machine and improves the accuracy of its action-selection decisions via a ‘learning’ process. Specifically, one is a Q-learning algorithm for a semi-Markov decision process (QLS) and another is a Q-learning algorithm with a learning-improvement heuristic (QLIH) to further improve the performance of QLS. We compare the performance of QLS and QLIH with a benchmarking Brownian policy and the first-come-first-served policy. The numerical results show that QLIH outperforms QLS and both benchmarking policies.     

The G-group heuristic to solve the multi-product,sequencing, lot sizing and scheduling problem in flow shops

This paper presents a new heuristic to solve the problem of making sequencing, lot sizing and scheduling decisions for a number of products manufactured in a flow shop environment, so as to minimize the sum of setup and inventory holding costs while a given demand is fulfilled without backlogging. The proposed solution method first determines sequencing decisions then lot sizing and scheduling decisions are simultaneously determined. This heuristic, called the G-group method, divides the set of products into G groups and requires that products belonging to the same group have the same cycle time. Also, the cycle time of each group is restricted to be an integer multiple of a basic period. For each basic period of the global cycle, the products to be produced during this period and the production sequence to be used are chosen. Then, a non-linear program is solved to determine lot sizes and to construct a feasible production schedule. To evaluate its performance, the G-group method was compared to four other methods. Numerical results show that the proposed heuristic outperforms all these methods.     

The G-group heuristic for single machine lot scheduling

This paper develops a heuristic procedure for generating feasible solutions for the single-machine, multi-product, infinite-horizon, lot scheduling problem. This problem occurs in several practical situations, for example, in metal stamping factories, on appliance assembly lines, in the beverage blending and bottling industries, in paint production and on motor car assembly lines. The proposed heuristic divides the N products into G groups and the products belonging to the same group are produced in the same cyclical pattern. Thus the problem of scheduling N independent products is reduced to that of scheduling G groups of products. Since G is much less than N, the problem is made simpler. The proposed heuristics has two main advantages: implementation facility and effectiveness. Computer codes are available for several mini and micro computers. The effectiveness is demonstrated by two tests. First, we solved the six problems originally solved by Elmaghraby (1978 a). Obviously, the results based on only six problems, cannot be generalized. Second, the G-group heuristic, as well as five other heuristics, was applied to 270 random computer-generated problems. The results show that it performed better.