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.     

On the feasibility of sequence-dependent economic lot scheduling problem

Most of the literature dealing with the determination of cyclic part input sequences in a flexible flow system is restricted in that it only searches for input sequences that are permutations of the minimal part set (MPS). This study is unique in that it investigates input sequences generated by integer programming (IP) formulations that balance or unbalance machine workloads to help maximize overall machine utilization (Stecke 1992). Also, this study integrates the input sequence determination decision with the part mix ratio determination, within the overall framework of a flexible approach to FMS operation over time. A simulation model of a flexible flow system was designed to study the effects on overall machine utilizations caused by utilizing alternative part mix ratios to help determine input sequences. The procedures used to determine the part mix ratios include IP formulations and those that are generated randomly, including the MPS mix ratios. Three different experimental settings are used to test these effects as well as (I) the robustness of the part input sequences that can be derived from the IP generated mix ratios, and (2) the relative importance of the part mix ratio decision in relation to the part input sequence determination. A new FMS physical design that can also be easily modelled to capture look-ahead capability proved to be simple and effective. Several significant conclusions regarding part mix ratios, pan input sequences, and look-ahead capability are revealed. These include: (1) the determination of the part mix ratios proved to be more significant in improving FMS performance than the determination of part input sequences; (2) the robust nature of the IP formulations was demonstrated; and (3) look-ahead capability provides equally high overall machine utilizations at lower levels of work-in-process. Future research areas are presented that would help validate and extend the observations found in this study.     

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.     

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.     

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.     

Hybrid genetic algorithm for group technology economic lot scheduling problem

The concept of group technology has been successfully applied to many production systems, including flexible manufacturing systems. In this paper we apply group technology principles to the economic lot scheduling problem, which has been studied for over 40 years. We develop a heuristic algorithm and a hybrid genetic algorithm for the group technology economic lot scheduling problem. Numerical experiments show that the developed algorithms outperform the existing heuristics.     

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.     

Effective allocation of idle time in the group technology economic lot scheduling problem

The group technology economic lot scheduling problem (GT-ELSP) addresses the issue of scheduling the products, classified into groups, on a single facility. The objective is to develop a schedule that minimises the sum of average inventory holding and setup costs over the infinite planning horizon. Previous research on this class of problems has assumed the cycle idle time to be equally divided among various sequence positions and has varied the frequency of production of individual products. We propose a heuristic that maintains constant frequency of products and varies the idle time among the sequence positions. We address the feasibility issue of the GT-ELSP and show that our heuristic, based on the time varying lot size approach, yields low-cost quality solutions that aid practical implementation. We tested our heuristic on a large set of randomly generated problems to assess its efficacy over the solutions of earlier proposed heuristics.     

A genetic algorithm for solving the economic lot scheduling problem in flow shops

In this study, we propose a hybrid genetic algorithm (HGA) to solve the economic lot scheduling problem in flow shops. The proposed HGA utilizes a so-called Proc PLM heuristic that tests feasibility for the candidate solutions obtained in the evolutionary process of genetic algorithm. When a candidate solution is infeasible, we propose to use a binary search heuristic to ‘fix’ the candidate solution so as to obtain a feasible solution with the minimal objective value. To evaluate the performance of the proposed HGA, we randomly generate a total of 2100 instances from seven levels of utilization rate ranged from 0.45 to 0.80. We solve each of those 2100 instances by the proposed HGA and the other solution approaches in the literature. Our experiments show that the proposed HGA outperforms traditional methods for solving the economic lot scheduling problem in flow shops.     

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.     

Stochastic economic lot sizing and scheduling problem with pitch interval,reorder points and flexible sequence

This paper presents a solution for a class of the stochastic economic lot sizing scheduling problem that is typical of the replenishment pull system proposed by the lean manufacturing approach. In this class, lots of any product are produced in fixed intervals called pitch. The proposed solution uses flexible production sequences and reorder points that are compatible with the concepts of supermarket and level production. It adopts the queuing discipline obtained from a fluid model that approximates the stochastic process of arrival and production orders. Given the queuing discipline, an iterative algorithm returns a near-optimal solution for the system. The proposed approach allows us possible to differentiate inventory cost and service levels by product, and the stock required is lower than that required by the discipline ‘first stock out, first out’. The algorithm is fast and stable, allowing its frequent use in real-world instances.     

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.