A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines

This paper addresses the capacitated lot-sizing problem involving the production of multiple items on unrelated parallel machines. A production plan should be determined in order to meet the forecast demand for the items, without exceeding the capacity of the machines and minimize the sum of production, setup and inventory costs. A heuristic based on the Lagrangian relaxation of the capacity constraints and subgradient optimization is proposed. Initially, the heuristic is tested on instances of the single machine problem and results are compared with heuristics from the literature. For parallel machines and small problems the heuristic performance is tested against optimal solutions, and for larger problems it is compared with the lower bound provided by the Lagrangian relaxation.     

A holding cost bound for the economic lot-sizing problem with time-invariant cost parameters

We show that in an optimal solution of the economic lot-sizing problem the total holding cost in an order interval is bounded from above by a quantity proportional to the setup cost and the logarithm of the number of periods in the interval. We present two applications of this result.     

An MIP-based interval heuristic for the capacitated multi-level lot-sizing problem with setup times

This paper considers the capacitated multi-level lot-sizing problem with setup times, a class of difficult problems often faced in practical production planning settings. In the literature, relax-and-fix is a technique commonly applied to solve this problem due to the fact that setup decisions in later periods of the planning horizon are sensitive to setup decisions in the early periods but not vice versa. However, the weakness of this method is that setup decisions are optimized only on a small subset of periods in each iteration, and setup decisions fixed in early iterations might adversely affect setup decisions in later periods. In order to avoid these weaknesses, this paper proposes an extended relax-and-fix based heuristic that systematically uses domain knowledge derived from several strategies of relax-and-fix and a linear programming relaxation technique. Computational results show that the proposed heuristic is superior to other well-known approaches on solution qualities, in particular on hard test instances.     

A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times

This paper presents a hybrid of a general heuristic framework and a general purpose mixed-integer programming (MIP) solver. The framework is based on local search and an adaptive procedure which chooses between a set of large neighborhoods to be searched. A mixed integer programming solver and its built-in feasibility heuristics is used to search a neighborhood for improving solutions. The general reoptimization approach used for repairing solutions is specifically suited for combinatorial problems where it may be hard to otherwise design suitable repair neighborhoods. The hybrid heuristic framework is applied to the multi-item capacitated lot sizing problem with setup times, where experiments have been conducted on a series of instances from the literature and a newly generated extension of these. On average the presented heuristic outperforms the best heuristics from the literature, and the upper bounds found by the commercial MIP solver ILOG CPLEX using state-of-the-art MIP formulations. Furthermore, we improve the best known solutions on 60 out of 100 and improve the lower bound on all 100 instances from the literature.     

New heuristic for the dynamic layout problem

The dynamic layout problem addresses the situation where the traffic among the various units within a facility changes over time. Its objective is to determine a layout for each period in a planning horizon such that the total of the flow and the relocation costs is minimized. The problem is computationally very hard and has begun to receive attention only recently. In this paper, we present a new heuristic scheme, based on the idea of viable layouts, which is easy to operationalize. A limited computational study shows that, depending upon how it is implemented, this scheme can be reasonably fast and can yield results that are competitive with those from other available solution methods.     

Coordination of dynamic lot-sizing in supply chains

This paper presents a new scheme for the coordination of dynamic, uncapacitated lot-sizing problems in two-party supply chains where parties’ local data are private information and no external or central entity is involved. This coordination scheme includes the following actions: At first, the buyer generates a series of different supply proposals using an extension of her local lot-sizing problem. Then the supplier calculates his cost changes that would result from the implementation of the buyer’s proposals. Based on these information, parties can identify the best proposal generated. The scheme identifies the system-wide optimum in different settings—for instance in a two-stage supply chain where the supplier’s costs for holding a period’s demand in inventory exceed his setup costs.     

A dynamic programming heuristic for the P-median problem

A new heuristic algorithm is proposed for the P-median problem. The heuristic restricts the size of the state space of a dynamic programming algorithm. The approach may be viewed as an extension of the myopic or greedy adding algorithm for the P-median model. The approach allows planners to identify a large number of solutions all of which perform well with respect to the P-median objective of minimizing the demand weighted average distance between customer locations and the nearest of the P selected facilities. In addition, the results indicate regions in which it is desirable to locate facilities. Computational results from three test problems are discussed.     

Optimal solutions for the economic lot-sizing problem with multiple suppliers and cost structures

This paper considers a multi-supplier economic lot-sizing problem in which the retailer replenishes his inventory from several suppliers. Each supplier is characterized by one of three types of order cost structures: incremental quantity discount cost structure, multiple set-ups cost structure and all-unit quantity discount cost structure. The problem is challenging due to the mix of different cost structures. For all cases of the problem where each supplier is characterized by one of the first two cost structures, some optimality properties are proposed and optimal algorithms based on dynamic programming are designed. For the case where all suppliers are characterized by all-unit quantity discount cost structures, it is hard to design a polynomial time algorithm by the analyzed optimal properties. However, it is proved that one of its special cases can be solved in polynomial time.     

An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure

We present a fully polynomial time approximation scheme (FPTAS) for a capacitated economic lot-sizing problem with a monotone cost structure. An FPTAS delivers a solution with a given relative error ɛ in time polynomial in the problem size and in 1/ɛ. Such a scheme was developed by van Hoesel and Wagelmans [8] for a capacitated economic lot-sizing problem with monotone concave (convex) production and backlogging cost functions. We omit concavity and convexity restrictions. Furthermore, we take advantage of a straightforward dynamic programming algorithm applied to a rounded problem.     

Heuristic approach on dynamic lot-sizing model for durable products with end-of-use constraints

A version of the dynamic lot-sizing (DLS) problem involving durable products with end-of-use constraints is analyzed in this paper. First, we mathematically formulate this problem, then certain properties are derived to construct the structure of the optimal solution. Next, based on these properties, a recursive optimization algorithm is proposed for a single-item problem. Moreover, an approximate algorithm is designed on the basis of the optimization algorithm, with linear computational complexity. A heuristic approach is proposed for solving the two-item DLS problem. The difficulty in solving this problem lies in its decomposition into item-level subproblems while ensuring the feasibility of the solution. The proposed technique aims to resolve this issue by combining the capabilities of Lagrangian relaxation to decompose the problem into smaller subproblems, and a genetic algorithm (GA) is used to update the Lagrangian multipliers. Further, the computational results obtained using the proposed approach are enumerated to demonstrate its effectiveness. Finally, the conclusion and remarks are given to discuss the possible future works.     

A dynamic programming based heuristic for the assembly line balancing problem

The simple assembly line balancing problem is the simplification of a real problem associated to the assignment of the elementary tasks required for assembly of a product in an assembly line. This problem has been extensively studied in the literature for more than half a century. The present work proposes a new procedure to solve the problem we call Bounded Dynamic Programming. This use of the term Bounded is associated not only with the use of bounds to reduce the state space but also to the reduction of such space based on heuristics. This procedure is capable of obtaining an optimal solution rate of 267 out of 269 instances, which have been used in previous works, thus obtaining the best-known performance for the problem. These results are an improvement from any previous procedure found in the literature even when using smaller computing times.     

A heuristic procedure for solving the dynamic probabilistic project expediting problem

Because of activity duration uncertainties, large-scale projects can often be modeled most realistically as probabilistic activity networks. The complex interactions among activities with uncertain durations virtually assures a low probability that these projects will be completed before predetermined due dates. As a result, it is often necessary to expedite individual activities in these projects to improve due date performance. This research introduces a dynamically applied matrix simulation approach for selecting expediting options in order to control the probability of successful project completion before predefined due dates. Experiments are conducted to demonstrate the ability of this new approach to generate quality alternatives and efficiently evaluate large-scale projects.     

An efficient computational method for a stochastic dynamic lot-sizing problem under service-level constraints

We provide an efficient computational approach to solve the mixed integer programming (MIP) model developed by Tarim and Kingsman [8] for solving a stochastic lot-sizing problem with service level constraints under the static-dynamic uncertainty strategy. The effectiveness of the proposed method hinges on three novelties: (i) the proposed relaxation is computationally efficient and provides an optimal solution most of the time, (ii) if the relaxation produces an infeasible solution, then this solution yields a tight lower bound for the optimal cost, and (iii) it can be modified easily to obtain a feasible solution, which yields an upper bound. In case of infeasibility, the relaxation approach is implemented at each node of the search tree in a branch-and-bound procedure to efficiently search for an optimal solution. Extensive numerical tests show that our method dominates the MIP solution approach and can handle real-life size problems in trivial time.     

A tabu search heuristic for the dynamic transportation of patients between care units

The problem studied in this paper stems from a real application to the transportation of patients in the Hospital Complex of Tours (France). The ambulance central station of the Hospital Complex has to plan the transportation demands between care units which require a vehicle. Some demands are known in advance and the others arise dynamically. Each demand requires a specific type of vehicle and a vehicle can transport only one person at a time. The demands can be subcontracted to a private company which implies high cost. Moreover, transportations are subject to particular constraints, among them priority of urgent demands, disinfection of a vehicle after the transportation of a patient with contagious disease and respect of the type of vehicle needed. These characteristics involve a distinction between the vehicles and the crews during the modeling phase. We propose a modeling for solving this difficult problem and a tabu search algorithm inspired by Gendreau et al. (1999). This method supports an adaptive memory and a tabu search procedure. Computational experiments on a real-life instance and on randomly generated instances show that the method can provide high-quality solutions for this dynamic problem with a short computation time.     

An algorithm for single-item economic lot-sizing problem with general inventory cost, non-decreasing capacity, and non-increasing setup and production cost

This paper considers an economic lot-sizing model with non-decreasing capacity constraint, non-increasing setup cost and production cost, and a general inventory cost. We prove that when periodic starting inventory is not less than a certain critical value, it is optimal to produce nothing; this critical value can be computed easily which results in a new effective algorithm.     

An application of least cost acceptance sampling schemes

Summary A technique is described for determining most economical single sample inspection schemes in the situation where costs associated with inspection and failure to detect defective items can be estimated. A computational procedure is outlined, and a comparison made between the schemes determined by this method, and those previously in use. A least-cost decision rule is also derived for sequential sampling schemes.

---

Zusammenfassung Ein Verfahren zum Aufstellen wirtschaftlichster einfacher Stichprobenverfahren wird für den Fall beschrieben, in dem die Kosten für das Überprüfen und das Nichtentdecken fehlerhafter Stücke geschätzt werden können. Es wird ein numerisches Verfahren aufgezeigt und ein Vergleich zwischen dem hier beschriebenen Verfahren und den früher verwendeten durchgeführt. Eine Entscheidungsregel für geringste Kosten wird ebenso für sequentielle Stichprobenpläne hergeleitet.

---

---

Now with the Operations Research Section of B.O.A.C., Comet House, London Airport, Hounslow, Middx., England.

---

Vorgel. v.:M. Sasieni     

A heuristic for single-warehouse multiretailer supply chains with all-unit transportation cost discounts

In supply chain management research, transportation costs, if explicitly considered at all, are frequently assumed to be linear. These costs often have a more complex form, such as an all-unit discount structure – this piecewise cost function adds significant complexity when included in supply chain management problems and is therefore often ignored due to solution time or tractability concerns. We present and evaluate a new heuristic procedure which provides good solutions to problems involving all-unit discount cost functions while significantly reducing solution times. The general nature of this procedure does not require assumptions about the supply chain structure or policies, and is therefore applicable in a wide range of settings.     

Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags

This paper shows that the single machine scheduling problem with multiple operations per job separated by minimum specified time-lags is NP-hard in the strong sense. Seven simple and polynomially bounded heuristic algorithms are developed for its solution when each job requires only two operations. Empirical evaluation shows that the percentage deviation of the heuristic solutions from their lower bounds is quite low and the effectiveness of these heuristic algorithms in finding optimal schedules increases with an increase in the number of jobs.