Equivalence classes of problem instances for a continuous-time lot sizing and scheduling problem

In the context of a single machine, multi-item, continuous-time lot sizing and scheduling problem with a production rate alternating between the two values zero and full production rate, this paper identifies classes of equivalent problem instances which differ from one another in the way in which demand is represented. Each class contains an instance with a continuous cumulated demand function, and may contain demand functions with very different shapes, including functions with discontinuities. When approaching the problem (in order to solve it numerically, or to prove analytical results etc.), it therefore becomes possible to select, from many different representations, the problem instance which best meets the requirements of the applied method.     

A scheduling policy for adjusting economic lot quantities to a feasible solution

A heuristic scheduling policy is introduced for a multi-item, single-machine production facility. The scheduling policy uses the presumed optimal order quantities derived from solving an Economic Lot Size Problem and checks that the quantities obtain a feasible production schedule according to current inventory levels and expected demand rates. If not, the scheduling policy modifies the order quantities to achieve a possible solution without shortages. The scheduling policy is inspired by modification of the similar heuristic Dynamic Cycle Lengths Policy by Leachman and Gascon from 1988, 1991. The main characteristics of this scheduling policy are successive batches of the same item are treated explicitly, due to that it is quite possible that one item be manufactured several times before one other item is manufactured once more; the batches are ordered in increasing run-out time; if the existing situation creates stock-outs with ordinary order quantities, then the order quantities are decreased with a common scaling factor to try to prevent inventory shortages; in case the decrease of the order quantities changes expected run-out times, the batches are reordered after new run-out times; no filling up to an explicit inventory level is done, the filling up is done by the desirable order quantity; to prevent possible excess inventory the policy suggests time periods where no production should be performed. The scheduling policy contains no economical evaluation; this is supposed to be done when the order quantities are calculated, the policy prevents shortages and excess inventory. A numerical example illustrates the suggested scheduling policy. Finally, it is discussed as to how the policy can also take into account stochastic behaviour of the demand rates and compensate the schedule by applying appropriate safety times.     

Solution approaches for the soft drink integrated production lot sizing and scheduling problem

In this paper we present a mixed integer programming model that integrates production lot sizing and scheduling decisions of beverage plants with sequence-dependent setup costs and times. The model considers that the industrial process produces soft drink bottles in different flavours and sizes, and it is carried out in two production stages: liquid preparation (stage I) and bottling (stage II). The model also takes into account that the production bottleneck may alternate between stages I and II, and a synchronisation of the production between these stages is required. A relaxation approach and several strategies of the relax-and-fix heuristic are proposed to solve the model. Computational tests with instances generated based on real data from a Brazilian soft drink plant are also presented. The results show that the solution approaches are capable of producing better solutions than those used by the company.     

Economic lot scheduling with deliberated and controlled coproduction

This paper presents an algorithm to define the optimal parameters for deliberated and controlled coproduction in an economic lot scheduling problem setting (DCCELSP). Coproduction is said to be deliberated and controlled because it is possible to decide whether or not to coproduce when all the parameters associated with the process are known. The aim is to determine how to produce two products most economically where deliberated coproduction is an option. For this purpose, a procedure for defining optimal lot periods is introduced. Two models are proposed for this procedure and a numerical illustration is provided to gain insight into their dynamics. The cost advantages of coproduction were found to depend on the relationship between setup and holding costs, production rates, and demand for products. The more similar these system parameters are and the higher the machine usage ratio is, the more favourable coproduction is. Additionally, if coproduction is not deliberated appropriately, costs soar.     

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

This paper presents a new and efficient heuristic to solve the multi-product, economic lot sizing and scheduling problem in flow shops. The problem addressed is that of making sequencing, lot sizing and scheduling decisions for a number of products so as to minimize the sum of setup costs, work-in-process inventory holding costs and final-products inventory holding costs while a given demand is fulfilled without backlogging. The proposed heuristic, called the two-group method (TG), assumes that the cycle time of each product is an integer multiple of a basic period and restricts these multiples to take either the value 1 or K where K is a positive integer. The products to be produced once each K basic period are then partitioned into K sub-groups and each sub-group is assigned to one and only one of the K basic periods of the global cycle. This method first determines a value for K and a feasible partition. Then, a production sequence is determined for each sub-group of products and a non-linear program is solved to determine lot sizes and a feasible schedule. We also show how to adapt our method to the case of batch streaming (transportation of sub-batches from one machine to the next). To evaluate its performance, the TG method was compared to both the common cycle method and a reinforced version of El-Najdawi’s job-splitting heuristic. Numerical results show that the TG method outperforms both of these methods.     

Capacitated lot sizing and scheduling with parallel machines and shared buffers: A case study in a packaging company

The aim of this work is to propose a solution approach for a capacitated lot sizing and scheduling real problem with parallel machines and shared buffers, arising in a packaging company producing yoghurt. The problem has been formulated as a hybrid Continuous Set-up and Capacitated Lot Sizing Problem (CSLP–CLSP). A new effective two stage optimisation heuristic based on the decomposition of the problem into a lot sizing problem and a scheduling problem has been developed. An assignment of mixture to buffers is made in the first stage, and therefore the corresponding orders are scheduled on the production lines by performing a local search. Computational tests have been performed on the real data provided by the company. The heuristic exhibits near-optimal solutions, all obtained in a very short computational time.     

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests.     

Polynomial cases of the economic lot sizing problem with cost discounts

In this paper we study the economic lot sizing problem with cost discounts. In the economic lot sizing problem a facility faces known demands over a discrete finite horizon. At each period, the ordering cost function and the holding cost function are given and they can be different from period to period. There are no constraints on the quantity ordered in each period and backlogging is not allowed. The objective is to decide when and how much to order so as to minimize the total ordering and holding costs over the finite horizon without any shortages. We study two different cost discount functions. The modified all-unit discount cost function alternates increasing and flat sections, starting with a flat section that indicates a minimum charge for small quantities. While in general the economic lot sizing problem with modified all-unit discount cost function is known to be NP-hard, we assume that the cost functions do not vary from period to period and identify a polynomial case. Then we study the incremental discount cost function which is an increasing piecewise linear function with no flat sections. The efficiency of the solution algorithms follows from properties of the optimal solution. We computationally test the polynomial algorithms against the use of CPLEX.     

Solving a concrete sleepers production scheduling by genetic algorithms

PRECON S.A. is a manufacturing company devoted to produce prefabricated concrete parts for several industries as railway transportation and agricultural industries. Recently, PRECON S.A. signed a contract with RENFE, the Spanish National Railway Company, to manufacture pre-stressed concrete sleepers for the sidings of the new railways of the high speed train (AVE). The scheduling problem associated with the manufacturing process of the sleepers is very complex, since this involves several constraints and objectives. These constraints are related to production capacity, the quantity of available moulds, demand satisfaction and other operational constraints. The two main objectives are related to the way to maximize the utilization of manufacturing resources and minimize mould movements. We developed a deterministic crowding genetic algorithm for this multiobjective problem. The algorithm has proved to be a powerful and flexible tool to solve large-scale instances of this real and complex scheduling problem.     

Pricing,relaxing and fixing under lot sizing and scheduling

We present a novel mathematical model and a mathematical programming based approach to deliver superior quality solutions for the single machine capacitated lot sizing and scheduling problem with sequence-dependent setup times and costs. The formulation explores the idea of scheduling products based on the selection of known production sequences. The model is the basis of a matheuristic, which embeds pricing principles within construction and improvement MIP-based heuristics. A partial exploration of distinct neighborhood structures avoids local entrapment and is conducted on a rule-based neighbor selection principle. We compare the performance of this approach to other heuristics proposed in the literature. The computational study carried out on different sets of benchmark instances shows the ability of the matheuristic to cope with several model extensions while maintaining a very effective search. Although the techniques described were developed in the context of the problem studied, the method is applicable to other lot sizing problems or even to problems outside this domain.     

The stochastic economic lot scheduling problem: A survey

The present literature survey focuses on the stochastic economic lot scheduling problem (SELSP). The SELSP deals with the make-to-stock production of multiple standardized products on a single machine with limited capacity under random demands, possibly random setup times and possibly random production times. The main task of a production manager in this setting is the construction of a production plan for the machine. Based on the critical elements of such a production plan, we present a classification and extensive overview of the research on the SELSP together with an indication of open research areas. By doing so, we intend to stimulate the discussion on the important problems concerning the SELSP both from a theoretical and a practical point of view.     

Economic lot sizing: The capacity reservation model

Capacity reservation contracts allow a consumer to purchase up to a certain capacity at a unit price lower than that of the spot market, while the consumer’s excess orders are realized at the spot price. In this paper, we consider a lot sizing problem where the consumer places orders following a capacity reservation contract. In particular, we study the general problem and the polynomial time solvable special cases of the problem and propose corresponding algorithms for them.     

Planning for demand failure: A dynamic lot size model for clinical trial supply chains

This paper examines the optimal production lot size decisions for clinical trial supply chains. One unique aspect of clinical trial supply chains is the risk of failure, meaning that the investigational drug is proven unsafe or ineffective during human testing and the trial is halted. Upon failure, any unused inventory is essentially wasted and needs to be destroyed. To avoid waste, manufacturers could produce small lot sizes. However, high production setup costs lead manufacturers to opt for large lot sizes and few setups. To optimally balance this tradeoff of waste and destruction versus production inefficiency, this paper generalizes the Wagner-Whitin model (W-W model) to incorporate the risk of failure. We show that this stochastic model, referred to as the failure-risk model, is equivalent to the deterministic W-W model if one adjusts the cost parameters properly to reflect failure and destruction costs. We find that increasing failure rates lead to reduced lot sizes and that properly incorporating the risk of failure into clinical trial drug production can lead to substantial cost savings as compared to the W-W model without the properly adjusted parameters.     

Solving the knapsack problem with imprecise weight coefficients using genetic algorithms

This paper investigates solving the knapsack problem with imprecise weight coefficients using genetic algorithms. This work is based on the assumption that each weight coefficient is imprecise due to decimal truncation or coefficient rough estimation by the decision-maker. To deal with this kind of imprecise data, fuzzy sets provide a powerful tool to model and solve this problem. We investigate the possibility of using genetic algorithms in solving the fuzzy knapsack problem without defining membership functions for each imprecise weight coefficient. The proposed approach simulates a fuzzy number by distributing it into some partition points. We use genetic algorithms to evolve the values in each partition point so that the final values represent the membership grade of a fuzzy number. The empirical results show that the proposed approach can obtain very good solutions within the given bound of each imprecise weight coefficient than the fuzzy knapsack approach. The fuzzy genetic algorithm concept approach is different, but gives better results than the traditional fuzzy approach.     

A genetic algorithms simulation approach for the multi-attribute combinatorial dispatching decision problem

This paper presents a genetic algorithms (GA) simulation approach in solving a multi-attribute combinatorial dispatching (MACD) decision problem in a flow shop with multiple processors (FSMP) environment. The simulation is capable of modeling a non-linear and stochastic problem. GA are one of the commonly used metaheuristics and are a proven tool for solving complex optimization problems. The proposed GA simulation approach addresses a complex MACD problem. Its solution quality is illustrated by a case study from a multi-layer ceramic capacitor (MLCC) manufacturing plant. Because GA search results are often sensitive to the search parameters, this research optimized the GA parameters by using regression analysis. Empirical results showed that the GA simulation approach outperformed several commonly used dispatching rules. The improvements are ranging from 33% to 61%. On the other hand, the increased shop-floor-control complexity may hinder the implementation of the system. Finally, future research directions are discussed.     

Lower bounds for the economic lot scheduling problem using aggregation

The problem considered in this paper is to choose cyclical production patterns for several products which are produced on a common production facility. By aggregating data, dynamic programming can be used to obtain lower bounds which, in general, are much stronger than those obtained when the capacity constraint is not recognized.Lower bounds are of interest when generating possible solutions and also in connection with branch-and-bound methods.     

A search heuristic for the sequence-dependent economic lot scheduling problem

Almost all of the research on the economic lot scheduling problem (ELSP) has assumed that setup times are sequence-independent even though sequence-dependent problems are common in practice. Furthermore, most of the solution approaches that have been developed solve for a single optimal schedule when in practice it is more important to provide managers with a range of schedules of different length and complexity. In this paper, we develop a heuristic procedure to solve the ELSP problem with sequence-dependent setups. The heuristic provides a range of solutions from which a manager can choose, which should prove useful in an actual stochastic production environment. We show that our heuristic can outperform Dobson's heuristic when the utilization is high and the sequence-dependent setup times and costs are significant.     

A profit-maximizing economic lot scheduling problem with price optimization

The economic lot scheduling problem (ELSP) is a well known problem that focuses on scheduling the production of multiple items on a single machine such that inventory and setup costs are minimized. In this paper, we extend the ELSP to include price optimization with the objective to maximize profits. A solution approach based on column generation is provided and shown to produce very close to optimal results with short solution times on a set of test problems. The results are discussed and recommendations for further research are provided.