Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions

The capacitated lot sizing and loading problem (CLSLP) deals with the issue of determining the lot sizes of product families/end items and loading them on parallel facilities to satisfy dynamic demand over a given planning horizon. The capacity restrictions in the CLSLP are imposed by constraints specific to the production environment considered. When a lot size is positive in a specific period, it is loaded on a facility without exceeding the sum of the regular and overtime capacity limits. Each family may have a different process time on each facility and furthermore, it may be technologically feasible to load a family only on a subset of existing facilities. So, in the most general case, the loading problem may involve unrelated parallel facilities of different classes. Once loaded on a facility, a family may consume capacity during setup time. Inventory holding and overtime costs are minimized in the objective function. Setup costs can be included if setups incur costs other than lost production capacity. The CLSLP is relevant in many industrial applications and may be generalized to multi-stage production planning and loading models. The CLSLP is a synthesis of three different planning and loading problems, i.e., the capacitated lot sizing problem (CLSP) with overtime decisions and setup times, minimizing total tardiness on unrelated parallel processors, and, the class scheduling problem, each of which is NP in the feasibility and optimality problems. Consequently, we develop hybrid heuristics involving powerful search techniques such as simulated annealing (SA), tabu search (TS) and genetic algorithms (GA) to deal with the CLSLP. Results are compared with optimal solutions for 108 randomly generated small test problems. The procedures developed here are also compared against each other in 36 larger size problems.     

Statistical search methods for lotsizing problems

This paper reports on our experiments with statistical search methods for solving lotsizing problems in production planning. In lotsizing problems the main objective is to generate a minimum cost production and inventory schedule, such that (i) customer demand is satisfied, and (ii) capacity restrictions imposed on production resources are not violated. We discuss our experiences in solving these, in general NP-hard, lotsizing problems with popular statistical search techniques like simulated annealing and tabu search. The paper concludes with some critical remarks on the use of statistical search methods for solving lotsizing problems.     

MIP models for production lot sizing problems with distribution costs and cargo arrangement

This study presents mixed integer programming (MIP) models for production lot sizing problems with distribution costs using unit load devices such as pallets and containers. Problems that integrate production lot sizing decisions and loading of the products in vehicles (bins) are also modelled, in which constraints such as weight limits, volume restrictions or the value of the cargo loaded in the bins are considered. In general, these problems involve a trade-off between production, inventory and distribution costs. Lot sizing decisions should take into account production capacity and product demand constraints. Distribution decisions are related to the loading and transport of products in unit load devices. The MIP models are solved by the branch-and-cut method of an optimization package and the results show that these approaches have the potential to address different practical situations.     

Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem

The multi-stage capacitated lot sizing and loading problem (MCLSLP) deals with the issue of determining the lot sizes of product items in serially-arranged manufacturing stages and loading them on parallel facilities in each stage to satisfy dynamic demand over a given planning horizon. It is assumed that regular time capacity decisions have already been made in the tactical level and allocated to the stages, but it is still an important decision problem whether to augment regular time capacity by overtime capacity. Each item may be processed on a technologically feasible subset of existing facilities with different process and setup times on each facility. Since the solution of the MCLSLP requires the design of a powerful algorithm, simulated annealing (SA) and genetic algorithms (GA) are integrated to enhance their individual performances. Furthermore, these global optimisation methods are incorporated into a Lagrangean relaxation scheme, hence creating a hybrid solution methodology. Numerical results obtained using these methods confirm the mutual benefits of integrating different solution techniques.     

Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches

Proofs from complexity theory as well as computational experiments indicate that most lot sizing problems are hard to solve. Because these problems are so difficult, various solution techniques have been proposed to solve them. In the past decade, meta-heuristics such as tabu search, genetic algorithms and simulated annealing, have become popular and efficient tools for solving hard combinatorial optimization problems. We review the various meta-heuristics that have been specifically developed to solve lot sizing problems, discussing their main components such as representation, evaluation, neighborhood definition and genetic operators. Further, we briefly review other solution approaches, such as dynamic programming, cutting planes, Dantzig–Wolfe decomposition, Lagrange relaxation and dedicated heuristics. This allows us to compare these techniques. Understanding their respective advantages and disadvantages gives insight into how we can integrate elements from several solution approaches into more powerful hybrid algorithms. Finally, we discuss general guidelines for computational experiments and illustrate these with several examples.     

Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem

The vehicle routing problem (VRP) under capacity and distance restrictions involves the design of a set of minimum cost delivery routes, originating and terminating at a central depot, which services a set of customers. Each customer must be supplied exactly once by one vehicle route. The total demand of any vehicle must not exceed the vehicle capacity. The total length of any route must not exceed a pre-specified bound. Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated. A special data structure for the tabu search algorithm is implemented which has reduced notably the computational time by more than 50%. An estimate for the tabu list size is statistically derived. Computational results are reported on a sample of seventeen bench-mark test problems from the literature and nine randomly generated problems. The new methods improve significantly both the number of vehicles used and the total distances travelled on all results reported in the literature.     

Part type selection problem in flexible manufacturing systems: tabu search algorithms

Production planning in flexible manufacturing systems is concerned with the organization of production in order to satisfy a given master production schedule. The planning problem typically gives rise to several hierarchical subproblems which are then solved sequentially or simultaneously. In this paper, we address one of the subproblems: the part type selection problem. The problem is to determine a subset of part types having production requirements for immediate and simultaneous processing over the upcoming period of the planning horizon, subject to the tool magazine and processing time limitation. Several versions of tabu search (TS) algorithm are proposed for solving the problem. A systematic computational test is conducted to test the performance of the TS algorithms. The best TS algorithm developed is compared to a simulated annealing algorithm.     

Simulated annealing and tabu search approaches to unidirectional flowpath design for Automated Guided Vehicle Systems

In this paper, we address the flowpath design issue of Automated Guided Vehicle Systems (AGVSs). In particular, we concentrate on the design of unidirectional flowpaths (i.e. vehicles are restricted to travel only in one direction along a given segment of the flowpath). We have developed intelligent heuristics — simulated annealing and tabu search algorithms for the design of unidirectional AGVSs. Different versions of simulated annealing and tabu search algorithms are implemented. Our extensive computational results indicate that both simulated annealing and tabu search yield solutions of adequate quality for all practical purposes. A tabu search implementation with the use of a frequency-based memory structure dominates all tested heuristics in terms of solution quality (i.e. percent deviation from optimality), with an impressive average performance over 45 test problems of less than 0.85% deviation from optimality.     

Search Heuristics for Resource Constrained Project Scheduling

We develop a search procedure for project scheduling problems with multiple resource constraints as well as precedence constraints. The procedure is applied to three popular search heuristics, simulated annealing, tabu search and genetic algorithms. In the heuristics, a solution is represented with a string of numbers each of which denotes priority of each activity. The priorities are used to select an activity for scheduling among competing ones. The search heuristics with this encoding method can always generate feasible neighbourhood solutions for a given solution. Moreover, this encoding method is very flexible in that problems with objective functions of a general functional form (such as a nonlinear function) and complex constraints can be considered without much difficulty. Results of computational tests on the performance of the search heuristics showed that the search heuristics, especially the simulated annealing and tabu search algorithms worked better than existing heuristics.     

Incorporating demand uncertainty and forecast error in supply chain planning models

This paper develops a framework for examining the effect of demand uncertainty and forecast error on unit costs and customer service levels in the supply chain, including Material Requirements Planning (MRP) type manufacturing systems. The aim is to overcome the methodological limitations and confusion that has arisen in much earlier research. To illustrate the issues, the problem of estimating the value of improving forecasting accuracy for a manufacturer was simulated. The topic is of practical importance because manufacturers spend large sums of money in purchasing and staffing forecasting support systems to achieve more accurate forecasts. In order to estimate the value a two-level MRP system with lot sizing where the product is manufactured for stock was simulated. Final product demand was generated by two commonly occurring stochastic processes and with different variances. Different levels of forecasting error were then introduced to arrive at corresponding values for improving forecasting accuracy. The quantitative estimates of improved accuracy were found to depend on both the demand generating process and the forecasting method. Within this more complete framework, the substantive results confirm earlier research that the best lot sizing rules for the deterministic situation are the worst whenever there is uncertainty in demand. However, size matters, both in the demand uncertainty and forecasting errors. The quantitative differences depend on service level and also the form of demand uncertainty. Unit costs for a given service level increase exponentially as the uncertainty in the demand data increases. The paper also estimates the effects of mis-specification of different sizes of forecast error in addition to demand uncertainty. In those manufacturing problems with high demand uncertainty and high forecast error, improved forecast accuracy should lead to substantial percentage improvements in unit costs. Methodologically, the results demonstrate the need to simulate demand uncertainty and the forecasting process separately.     

Heuristic Search Algorithms for the Minimum Volume Ellipsoid

Abstract

A method of robust estimation of multivariate location and shape that has attracted a lot of attention recently is Rousseeuw's minimum volume ellipsoid estimator (MVE). This estimator has a high breakdown point but is difficult to compute successfully. In this article, we apply methods of heuristic search to this problem, including simulated annealing, genetic algorithms, and tabu search, and compare the results to the undirected random search algorithm that is often cited. Heuristic search provides several effective algorithms that are far more computationally efficient than random search. Furthermore, random search, as currently implemented, is shown to be ineffective for larger problems.     

Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem

This paper describes serial and parallel implementations of two different search techniques applied to the traveling salesman problem. A novel approach has been taken to parallelize simulated annealing and the results are compared with the traditional annealing algorithm. This approach uses abbreviated cooling schedule and achieves a superlinear speedup. Also a new search technique, called tabu search, has been adapted to execute in a parallel computing environment. Comparison between simulated annealing and tabu search indicate that tabu search consistently outperforms simulated annealing with respect to computation time while giving comparable solutions. Examples include 25, 33, 42, 50, 57, 75 and 100 city problems.     

Production planning via scenario modelling

Several Linear Programming (LP) and Mixed Integer Programming (MIP) models for the production and capacity planning problems with uncertainty in demand are proposed. In contrast to traditional mathematical programming approaches, we use scenarios to characterize the uncertainty in demand. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield a nonanticipative or implementable policy. Such an approach makes it possible to model nonstationarity in demand as well as a variety of recourse decision types. Two scenario-based models for formalizing implementable policies are presented. The first model is a LP model for multi-product, multi-period, single-level production planning to determine the production volume and product inventory for each period, such that the expected cost of holding inventory and lost demand is minimized. The second model is a MIP model for multi-product, multi-period, single-level production planning to help in sourcing decisions for raw materials supply. Although these formulations lead to very large scale mathematical programming problems, our computational experience with LP models for real-life instances is very encouraging.     

Good solutions to discrete noxious location problems via metaheuristics

An implementation of simulated annealing and tabu search is described for discrete versions of two noxious facility location problems —p-dispersion andp-defense-sum. A series of computational experiments leading to good choices of the parameters that drive simulated annealing and tabu search are presented for a 33-node data set. Using these parameter settings, the performance of simulated annealing and tabu search are compared to a semi-greedy heuristic for thirty randomly generated 25-node data sets.     

The impact of controllable production rates on the performance of inventory systems: A systematic review of the literature

The lot sizing problem has attracted the attention of researchers for more than a century, and it still belongs to the most relevant decision problems in many manufacturing companies. During the evolution of research on lot sizing, the seminal economic order quantity (EOQ) model proposed by Harris [1913. How many parts to make at once. Factory, the Magazine of Management, 10 (2), 135-136.] has remained the most popular model, despite its limitations. To support lot sizing decisions in practice, researchers have frequently extended Harris’ basic EOQ model to better reflect the characteristics of real production processes. One of these extensions is the consideration of controllable (variable) production rates, which gives production planners more flexibility in managing the build-up and depletion of inventory and in controlling costs.The aim of this paper is to provide a comprehensive and systematic overview of EPQ-type lot sizing models that consider controllable production rates. First, the paper proposes a conceptual framework that captures the characteristics of controllable production rates including the planning horizon (short vs. long term), the number of potential interventions per production run (one vs. multiple), the effect of controllable production rates on the performance of the inventory system (e.g., unit production costs, energy consumption, product quality), and the type of lot sizing model considered (e.g., two-stage models, multi-stage models, multi-item models). Secondly, the paper presents the results of a systematic literature review and evaluates the state-of-research of lot sizing models with controllable production rates. Based on the analysis of the literature, key trends are summarized and promising research opportunities are discussed.     

A mathematical programming model for integrating production and procurement transport decisions

In this paper, we propose a new mathematical programming model for integrating production and procurement transport planning decisions in manufacturing systems in a unique optimization model. This problem was introduced conceptually and dubbed as MRP IV by Díaz-Madroñero et al. (2012) to extend the current MRP (material requirement planning) systems. This proposal simultaneously considers material, production resources capacities and procurement transport planning decisions with different shipping modes (such as full-truckload, less-than-truckload and milk-run) in the supply chain to avoid suboptimal results, which are usually generated due to sequential and independent plans. We considered an industrial automobile company to validate the proposed model using real world data. The results obtained by the MRP IV proposed model, in terms of total planning costs and transport efficiency indicators, are better than those obtained in the current heuristic procedures followed in the company under study.     

A comparison of local search methods for flow shop scheduling

Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing.     

Bayesian variable selection in generalized linear models using a combination of stochastic optimization methods

In this paper the usage of a stochastic optimization algorithm as a model search tool is proposed for the Bayesian variable selection problem in generalized linear models. Combining aspects of three well known stochastic optimization algorithms, namely, simulated annealing, genetic algorithm and tabu search, a powerful model search algorithm is produced. After choosing suitable priors, the posterior model probability is used as a criterion function for the algorithm; in cases when it is not analytically tractable Laplace approximation is used. The proposed algorithm is illustrated on normal linear and logistic regression models, for simulated and real-life examples, and it is shown that, with a very low computational cost, it achieves improved performance when compared with popular MCMC algorithms, such as the MCMC model composition, as well as with “vanilla” versions of simulated annealing, genetic algorithm and tabu search.     

Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data

We address an integrated logistic system where decisions on location of depot, vehicle routing and assignment of routes to vehicles are considered simultaneously. Total cost and workload balance are common criteria influencing decision-making. Literature on location-routing problems addressed the location and vehicle routing decisions with a common assumption of assigning one route to one vehicle. However, the cost of acquiring vehicles (and crew) is often more significant than the routing cost. This notion of assigning several routes to a vehicle during the routing procedure is explored in our integrated model. We apply metaheuristics of tabu search and simulated annealing on real data and simulated data, to compare their performances under two versions: simultaneous or sequential routes assignment to vehicles. A new statistical procedure is proposed to compare two algorithms on the strength of their multi-objective solutions. Results show that the simultaneous versions have advantage over the sequential versions in problems where routes are capacity-constrained, but not in the time dimension. The simultaneous versions are also more effective in generating non-dominated solutions than the sequential versions.     

Local Search Methods for the Optimal Winner Determination Problem in Combinatorial Auctions

In this paper, both stochastic local search (SLS) and tabu search (TS) are studied for the optimal winner determination problem (WDP) in combinatorial auctions. The proposed methods are evaluated on various benchmark problems, and compared with the hybrid simulated annealing (SAGII), the memetic algorithms (MA) and Casanova. The computational experiments show that the SLS provides competitive results and finds solutions of a higher quality than TS and Casanova methods.