Multi-product batch production on a single machine—A problem revisited

When several products are processed one at a time on a single machine, the conventional approach of computing the economic batch quantity for each product cannot apply. An example for six products is considered, where the total production capacity on regular time is inadequate, so that overtime has to be used at an extra cost. A simple method is described for solving this problem when each product is produced once during a production cycle, the objective being to minimize the total set-up and holding costs per day. Schedules which involve batch splitting can reduce these costs further, and a guideline is proposed for the construction of sub-cycles. The results compare favourably with lower bounds computed for the purpose.     

经济批量排产问题的一种排产方法

针对经济批量排产问题假定生产可以在库存降为0之前开始,并且提出新的算法求产品的生产顺序。结果表明,该排产方法成本要低于其他2种常用的经济批量排产问题的方法,并且给出了算法的时间复杂性。     

Notes and Communications REPLANNING FREQUENCIES FOR MASTER PRODUCTION SCHEDULES

Updating production plans typically is achieved by rolling the planning horizon forward one period at a time, each time including the latest information in order to determine the best course of action to pursue in the present period. Theoretical planning-horizon studies have identified the conditions by which the production decisions in the current and some specified number of future periods remain optimal given some set of future demands. Motivated by these findings, this study addresses the replanning frequency in a hierarchical production planning problem where no planning-horizon theorems are available. In this problem the aggregate production plan and the master production schedule are linked by a rolling-horizon practice. Empirical experimentation indicates that under certain cost and demand conditions the master production schedule need not be updated every period. If a schedule does not need to be updated for several periods, the schedule for these periods can be frozen to provide stability for planning components at lower levels in the bill of material of the products. The results of this study thus provide some reference for the determination of the frozen portion of the master production schedule.     

Solving the Economic Lot-Scheduling Problem Using the Method of Prime Subperiods

In recent years the reported successes of Japanese production systems, particularly the just-in-time approach to inventory control, has caused managers to focus more of their attention on efficient decision-making procedures for determining production schedules that minimize inventory costs. One such potential area of attention is the economic lot-scheduling problem (ELSP), which occurs in a variety of manufacturing environments where machining operations are prevalent. The economic lot-scheduling problem addresses the determination of lot sizes for N products with constant demand (and cycled through one machine with a given production rate) to minimize setup and inventory costs. The most successful solution approaches to the ELSP have been based on the concept of a basic period that is of sufficient length for the production of all items, even though each item might not be produced during each repetition of the basic period. This paper proposes a heuristic approach to the solution of the ELSP (referred to as the method of prime subperiods), which is an extension of the basic period approaches. The procedure is described and demonstrated via an example and then tested using a set of six example problems previously employed in the literature related to the ELSP. The results indicate as good or superior performance by the proposed method of prime subperiods.     

An Approximate Solution to Deterministic Kanban Systems

This paper presents a simple heuristic for computing the number of kanbans in a kanban system. The production systems under consideration have a multistage, uncapacitated, assembly tree structure, with every stage producing only one item at a time. The experimental results show that this method generates very good solutions. In more realistic problems where the master production schedule incorporates a smoothed demand, the solution found under the proposed method is identical to that of the linear programming approximation. This simple heuristic can be used in the real world to quickly determine the number of kanbans for daily just-in-time operations.     

Some structural properties for the just-in-time level schedule problem

Just-in-time (JIT) is a pull concept applied mainly in repetitive manufacturing systems, and it is characterized by a scenario where only the required units are produced in the required quantities at the required times. It particularly aims at eliminating wastes associated with inventories in the system. A level schedule is desirable for a JIT assembly system, as it serves as an approximation for all forms of smoothing. The min-sum formulation of the assembly line level schedule problem is one of those that has been mainly used in the literature. Using this formulation as a base, we develop some useful structural properties for the problem. Among other things, it is shown that a level schedule would tend to be more difficult to achieve for products (models) with comparatively fewer units in the products composition structure.     

Multi-echelon supply chain network design in agile manufacturing

In this paper, we consider a supply chain network design problem in an agile manufacturing scenario with multiple echelons and multiple periods under a situation where multiple customers have heavy demands. Decisions in our supply chain design problem include selection of one or more companies in each echelon, production, inventory, and transportation. We formulate the problem integrating all decisions to minimize the total operational costs including fixed alliance costs between two companies, production, raw material holding, finished products holding, and transportation costs under production and transportation capacity limits. A Lagrangian heuristic is proposed in this paper. Optimizing a Lagrangian relaxation problem provides a lower bound, while a feasible solution is generated by adjustment techniques based on the solution of subproblems at each iteration. Computational results indicate the high quality solutions with less than 5% optimality gap are provided quickly by the approach in this paper. Further, compared to initiative managerial alternatives, an improvement of 15% to 25% is not unusual in certain cases for the proposed approach.     

A Model for Resource Constrained Production and Inventory Management

We present a general model for multi-item production and inventory management problems that include a resource restriction. The decision variables in the model can take on a variety of interpretations, but will typically represent cycle times, production batch sizes, number of production runs, or order quantities for each item. We consider environments where item demand rates are approximately constant and performing an activity such as producing a batch of a product or placing an order results in the consumption of a scarceresource that is shared among the items. Some examples of shared resources include limited machine capacity, a restriction on the amount of money that can be tied up in stock, orlimited storage capacity. We focus on the case where the decision variables must be integer valued or selected from a discrete set of choices, such as when an integer number of production runs is desired for each item, or in order quantity problems where the items come in pack sizes containing more than one unit and, therefore, the order quantities must be an integer multiple of the pack sizes. We develop a heuristic and a branch and bound algorithm for solving the problem. The branch and bound algorithm includes reoptimization procedures and the heuristic to improve its performance. Computational testing indicates that the algorithms are effective for solving the general model.     

Multi-echelon supply chain network design in agile manufacturing

In this paper, we consider a supply chain network design problem in an agile manufacturing scenario with multiple echelons and multiple periods under a situation where multiple customers have heavy demands. Decisions in our supply chain design problem include selection of one or more companies in each echelon, production, inventory, and transportation. We formulate the problem integrating all decisions to minimize the total operational costs including fixed alliance costs between two companies, production, raw material holding, finished products holding, and transportation costs under production and transportation capacity limits. A Lagrangian heuristic is proposed in this paper. Optimizing a Lagrangian relaxation problem provides a lower bound, while a feasible solution is generated by adjustment techniques based on the solution of subproblems at each iteration. Computational results indicate the high quality solutions with less than 5% optimality gap are provided quickly by the approach in this paper. Further, compared to initiative managerial alternatives, an improvement of 15% to 25% is not unusual in certain cases for the proposed approach.     

Inventory Control and Scheduling of Multiple Products in a Common Facility*

Consider a set of chemical products to be produced in a single facility. Each product has its own unique reaction time (which is assumed to be independent of its batch size), as well as other cost and demand values. In this paper, we address the problem of determining the optimal number of batches, batch sizes, and an accompanying production schedule for these products in the single facility that will minimize the total cost. Two different algorithms have been developed for this problem, the performances of which are contrasted with classical cyclic production schedules. Finally, some guidelines for the application of these methods to real-life problems are outlined.     

PRODUCTION SCHEDULING OF CONTINUOUS FLOW LINES: MULTIPLE PRODUCTS WITH SETUP TIMES AND COSTS

The problem of production planning and setup scheduling of multiple products on a single facility is studied in this paper. The facility can only produce one product at a time. A setup is required when the production switches from one type of product to another. Both setup times and setup costs are considered. The objective is to determine the setup schedule and production rate for each product that minimize the average total costs, which include the inventory, backlog, and setup costs. Under the assumption of a constant production rate, we obtain the optimal cyclic rotation schedule for the multiple products system. Besides the decision variables studied in the classical economic lot scheduling problem (ELSP), the production rate is also a decision variable in our model. We prove that our solutions improve the results of the classical ELSP.     

Design of Stockless Production Systems

In make‐to‐stock production systems finished goods are produced in anticipation of demand. By contrast, in stockless production systems finished goods are not produced until demand is observed. In this study we investigate the problem of designing a multi‐item manufacturing system, where there is both demand‐ and production‐related uncertainty, so that stockless operation will be optimal for all items. For the problem of interest, we focus on gaining an understanding of the effect of two design variables: (i) manufacturing speed—measured by the average manufacturing rate or, equivalently, the average unit manufacturing time, and (ii) manufacturing consistency—measured by the variation in unit manufacturing times. We establish conditions on these two variables that decision makers can use to design stockless production systems. Managerial implications of the conditions are also discussed.     

Lot sizing with storage losses under demand uncertainty

We address a variant of the single item lot sizing problem affected by proportional storage (or inventory) losses and uncertainty in the product demand. The problem has applications in, among others, the energy sector, where storage losses (or storage deteriorations) are often unavoidable and, due to the need for planning ahead, the demands can be largely uncertain. We first propose a two-stage robust optimization approach with second-stage storage variables, showing how the arising robust problem can be solved as an instance of the deterministic one. We then consider a two-stage approach where not only the storage but also the production variables are determined in the second stage. After showing that, in the general case, solutions to this problem can suffer from acausality (or anticipativity), we introduce a flexible affine rule approach which, albeit restricting the solution set, allows for causal production plans. A hybrid robust-stochastic approach where the objective function is optimized in expectation, as opposed to in the worst-case, while retaining robust optimization guarantees of feasibility in the worst-case, is also discussed. We conclude with an application to heat production, in the context of which we compare the different approaches via computational experiments on real-world data.     

Economic Lot Scheduling Problem with Returns

Motivated by a case study of a company that produces car parts, we study the multi‐product economic lot scheduling problem for a hybrid production line with manufacturing of new products and remanufacturing of returned products. For this economic lot scheduling problem with returns (ELSPR), we consider policies with a common cycle time for all products, and with one manufacturing lot and one remanufacturing lot for each product during a cycle. For a given cycle time, the problem is formulated as a mixed integer linear programming (MIP) problem, which provides the basis for an exact solution. The application of this model for one of the core products of the case study company indicates a 16% reduction in cost compared to the current lot scheduling policy.     

Supply Chain Scheduling: Distribution Systems

We study conflict and cooperation issues arising in a supply chain where a manufacturer makes products which are shipped to customers by a distributor. The manufacturer and the distributor each has an ideal schedule, determined by cost and capacity considerations. However, these two schedules are in general not well coordinated, which leads to poor overall performance. In this context, we study two practical problems. In both problems, the manufacturer focuses on minimizing unproductive time. The distributor minimizes customer cost measures in the first problem and minimizes inventory holding cost in the second problem. We first evaluate each party's conflict, which is the relative increase in cost that results from using the other party's optimal schedule. Since this conflict is often significant, we consider several practical scenarios about the level of cooperation between the manufacturer and the distributor. These scenarios define various scheduling problems for the manufacturer, the distributor, and the overall system. For each of these scheduling problems, we provide an algorithm. We demonstrate that the cost saving provided by cooperation between the decision makers is usually significant. Finally, we discuss the implications of our work for how manufacturers and distributors negotiate, coordinate, and implement their supply chain schedules in practice.     

MANAGING CYCLIC INVENTORIES

Cyclic inventory is the buffer following a machine that cycles over a set of products, each of which is subsequently consumed in a continuous manner. Scheduling such a machine is interesting when the changeover times from one product to another are non‐trivial—which is generally the case. This problem has a substantial literature, but the common practices of “lot‐splitting” and “maximization of utilization” suggest that many practitioners still do not fully understand the principles of cyclic inventory. This paper is a tutorial that demonstrates those principles. We show that cyclic inventory is directly proportional to cycle length, which in turn is directly proportional to total changeover time, and inversely proportional to machine utilization. We demonstrate the virtue of “maximum changeover policies” in minimizing cyclic inventory—and the difficulty in making the transition to an increased level of demand. In so doing, we explicate the different roles of cyclic inventory, transitional inventory, and safety stock. We demonstrate the interdependence of the products in the cycle—the lot‐size for one product cannot be set independently of the remaining products. We also give necessary conditions for consideration of improper schedules (i.e., where a product can appear more than once in the cycle), and demonstrate that both lot‐splitting and maximization of utilization are devastatingly counter‐productive when changeover time is non‐trivial.     

A Model for Master Production Scheduling in Uncertain Environments

In uncertain environments, the master production schedule (MPS) is usually developed using a rolling schedule. When utilizing a rolling schedule, the MPS is replanned periodically and a portion of the MPS is frozen in each planning cycle. The cost performance of a rolling schedule depends on three decisions: the choice of the replanning interval (R), which determines how often the MPS should be replanned; the choice of the frozen interval (F), which determines how many periods the MPS should be frozen in each planning cycle; and the choice of the forecast window (T), which is the time interval over which the MPS is determined using newly updated forecast data. This paper uses an analytical approach to study the master production scheduling process in uncertain environments without capacity constraints, where the MPS is developed using a rolling schedule. It focuses on the choices of F, R, and T for the MPS. A conceptual framework that includes all important MPS time intervals is described. The effects of F, R, and T on system costs, which include the forecast error, MPS change, setup, and inventory holding costs, are also explored. Finally, a mathematical model for the MPS is presented. This model approximates the average system cost as a function of F, R, T, and several environmental factors. It can be used to estimate the associated system costs for any combination of F, R, and T.     

Exact algorithms for scheduling programs with shared tasks

We study a scheduling problem where the jobs we have to perform are composed of one or more tasks. If two jobs sharing a non-empty subset of tasks are scheduled on the same machine, then these shared tasks have to be performed only once. This kind of problem is known in the literature under the names of VM-PACKING or PAGINATION. Our objective is to schedule a set of these objects on two parallel identical machines, with the aim of minimizing the makespan. This problem is NP-complete as an extension of the PARTITION problem. In this paper we present three exact algorithms with worst-case time-complexity guarantees, by exploring different branching techniques. Our first algorithm focuses on the relation between jobs sharing one or more symbols in common, whereas the two other algorithms branches on the shared symbols.

     

Hierarchical production planning for multi-product lines in the beverage industry¶

Multi-commodity production and distribution scheduling is one of the most complex and crucial problems facing many manufacturing companies. For a major European manufacturer specialising in bottling juices and drinks, we have designed and developed a hierarchical decomposition approach to the solution of the multi-commodity production planning problem. In this paper we focus our attention on the coarsest decomposition level, called multi-commodity aggregate production planning (MCAP). It concerns the choice of the best feasible production plan for a set of products (commodities) over an extended time horizon so as to meet forecast aggregate demands throughout the horizon. At this level, the problem constraints include hard constraints (such as production lines having a maximum capacity and products having short life-times), and soft constraints (budgetary concerns.) The objective is to determine the production plan that covers each period's demands as best as possible, while minimizing all relevant costs. Our method for solving MCAP produces optimal plans in negligible times in commodity PC workstations.     

Discrete parallel machine makespan ScheLoc problem

Scheduling–Location (ScheLoc) problems integrate the separate fields of scheduling and location problems. In ScheLoc problems the objective is to find locations for the machines and a schedule for each machine subject to some production and location constraints such that some scheduling objective is minimized. In this paper we consider the discrete parallel machine makespan ScheLoc problem where the set of possible machine locations is discrete and a set of n jobs has to be taken to the machines and processed such that the makespan is minimized. Since the separate location and scheduling problem are both \(\mathcal {NP}\)-hard, so is the corresponding ScheLoc problem. Therefore, we propose an integer programming formulation and different versions of clustering heuristics, where jobs are split into clusters and each cluster is assigned to one of the possible machine locations. Since the IP formulation can only be solved for small scale instances we propose several lower bounds to measure the quality of the clustering heuristics. Extensive computational tests show the efficiency of the heuristics.