Lot-sizing two-echelon assembly systems with random yields and rigid demand

We consider a two-echelon assembly system producing a single final product for which the demand is known. The first echelon consists of several parallel stages, whereas the second echelon consists of a single assembly stage. We assume that the yield at each stage is random and that demand needs to be satisfied in its entirety; thus, several production runs may be required. A production policy should specify, for each possible configuration of intermediate inventories, on which stage to produce next and the lot size to be processed. The objective is to minimize the expected total of setup and variable production costs.We prove that the expected cost of any production policy can be calculated by solving a finite set of linear equations whose solution is unique. The result is general in that it applies to any yield distribution. We also develop efficient algorithms leading to heuristic solutions with high precision and, as an example, provide numerical results for binomial yields.     

A two-level hedging point policy for controlling a manufacturing system with time-delay,demand uncertainty and extra capacity

This paper focuses on the production control of a manufacturing system with time-delay, demand uncertainty and extra capacity. Time-delay is a typical feature of networked manufacturing systems (NMS), because an NMS is composed of many manufacturing systems with transportation channels among them and the transportation of materials needs time. Besides this, for a manufacturing system in an NMS, the uncertainty of the demand from its downstream manufacturing system is considered; and it is assumed that there exist two-levels of demand rates, i.e., the normal one and the higher one, and that the time between the switching of demand rates are exponentially distributed. To avoid the backlog of demands, it is also assumed that extra production capacity can be used when the work-in-process (WIP) cannot buffer the high-level demands rate. For such a manufacturing system with time-delay, demand uncertainty and extra capacity, the mathematical model for its production control problem is established, with the objective of minimizing the mean costs for WIP inventory and occupation of extra production capacity. To solve the problem, a two-level hedging point policy is proposed. By analyzing the probability distribution of system states, optimal values of the two hedging levels are obtained. Finally, numerical experiments are done to verify the effectiveness of the control policy and the optimality of the hedging levels.     

Group technology in a hybrid flowshop environment: A case study

This paper addresses the problem of products grouping in the tile industry. This production system can be classified as a three-stage hybrid flowshop with sequence dependent and separable setup times. Main objective has been to identify a set of families integrated by products with common features. This classification would help Production Managers to minimize changeover time, allowing them to further reduce production times. The basic concept of “exploiting similarities”, taken from the Group Technology (GT) philosophy, has been used to address the problem in a creative way. A new “coefficient of similarity” between each of the products, has been defined and used as a parameter, allowing products to be grouped through a heuristic method. This research has already been applied in the framework of a real case, getting quite positive results (actual reduction in both setup and production costs, easier long-horizon planning and short-horizon scheduling, more accurate set up time estimates for new products, etc.).     

Multi-plant production planning in capacitated self-configuring two-stage serial systems

This research deals with a capacitated master production planning and capacity allocation problem for a multi-plant manufacturing system with two serial stages in each plant. We consider both cases in which a decoupling buffer is allowed or not between the two stages. Peculiar to the system considered is the capability of dynamically self-configuring its layout when buffering is disallowed, in the sense that, for each production run, different parallel machines in the second stage are grouped together and serially connected to a machine in the first stage. Although setup times and costs are considered negligible in our model, yet binary setup variables are introduced in order to account for minimum lot-sizes. The resulting mixed {0,1} linear programming model is solved by means of LP-based heuristic algorithms. The proposed modeling and solution procedure has been applied to problem instances originating from a real-world application, showing good results in practice.     

Simple heuristics for push and pull remanufacturing policies

Inventory policies for joint remanufacturing and manufacturing have recently received much attention. Most efforts, though, were related to (optimal) policy structures and numerical optimization, rather than closed form expressions for calculating near optimal policy parameters. The focus of this paper is on the latter. We analyze an inventory system with unit product returns and demands where remanufacturing is the cheaper alternative for manufacturing. Manufacturing is also needed, however, since there are less returns than demands. The cost structure consists of setup costs, holding costs, and backorder costs. Manufacturing and remanufacturing orders have non-zero lead times. To control the system we use certain extensions of the familiar (s, Q) policy, called push and pull remanufacturing policies. For all policies we present simple, closed form formulae for approximating the optimal policy parameters under a cost minimization objective. In an extensive numerical study we show that the proposed formulae lead to near-optimal policy parameters.     

Transient and steady-state analysis of a manufacturing system with setup changes

This paper deals with the optimal scheduling of a one-machine two-product manufacturing system with setup, operating in a continuous time dynamic environment. The machine is reliable. A known constant setup time is incurred when switching over from a part to the other. Each part has specified constant processing time and constant demand rate, as well as an infinite supply of raw material. The problem is formulated as a production flow control problem. The objective is to minimize the sum of the backlog and inventory costs incurred over a finite planning horizon. The global optimal solution, expressed as an optimal feedback control law, provides the optimal production rate and setup switching epochs as a function of the state of the system (backlog and inventory levels). For the steady-state, the optimal cyclic schedule (Limit Cycle) is determined. This is equivalent to solving a one-machine two-product Lot Scheduling Problem. To solve the transient case, the system's state space is partitioned into mutually exclusive regions such that with each region is associated an optimal control policy. A novel algorithm (Direction Sweeping Algorithm) is developed to obtain the optimal state trajectory (optimal policy that minimizes the sum of inventory and backlog costs) for this last case.     

Optimal production control of a dynamic two-product manufacturing system with setup costs and setup times

This paper deals with the optimal control of a one-machine two-product manufacturing system with setup changes, operating in a continuous time dynamic environment. The system is deterministic. When production is switched from one product to the other, a known constant setup time and a setup cost are incurred. Each product has specified constant processing time and constant demand rate, as well as an infinite supply of raw material. The problem is formulated as a feedback control problem. The objective is to minimize the total backlog, inventory and setup costs incurred over a finite horizon. The optimal solution provides the optimal production rate and setup switching epochs as a function of the state of the system (backlog and inventory levels). For the steady state, the optimal cyclic schedule is determined. To solve the transient case, the system's state space is partitioned into mutually exclusive regions such that with each region, the optimal control policy is determined analytically.     

Control Policy for a Manufacturing System with Random Yield and Rework

We develop a production policy that controls work-in-process (WIP) levels and satisfies demand in a multistage manufacturing system with significant uncertainty in yield, rework, and demand. The problem addressed in this paper is more general than those in the literature in three aspects: (i) multiple products are processed at multiple workstations, and the capacity of each workstation is limited and shared by multiple operations; (ii) the behavior of a production policy is investigated over an infinite-time horizon, and thus the system stability can be evaluated; (iii) the representation of yield and rework uncertainty is generalized. Generalizing both the system structure and the nature of uncertainty requires a new mathematical development in the theory of infinite-horizon stochastic dynamic programming. The theoretical contributions of this paper are the existence proofs of the optimal stationary control for a stochastic dynamic programming problem and the finite covariances of WIP and production levels under the general expression of uncertainty. We develop a simple and explicit sufficient condition that guarantees the existence of both the optimal stationary control and the system stability. We describe how a production policy can be constructed for the manufacturing system based on the propositions derived.     

Marketing-production decisions under independent and integrated channel structure

The topic of channel structure has recently attracted much attention among researchers in the marketing and economics area. However, in a majority of the existing literature the cost considerations are extremely simplified with the major focus being pricing policy. What happens when cost incurring decisions are strongly connected with pricing policies? This is the theme we wish to explore in the present paper. The non-trivial costs considered are production, inventory, and retailer effort rate, i.e. we seek to explore the marketing-production channel. We have used the methodology of differential games. The open-loop Stackelberg solution concept has been used to solve the manufacturer and retailer's problem. The Pareto solution concept has been used to solve the problem of the vertically integrated firm. The production, pricing, and effort rate policies thus derived have been compared to obtain insights into the impact of channel structure on these policies. Also, to examine the relation between channel structure and the retailing operation requiring effort, we derive the Stackelberg and Pareto solutions with and without effort rate as a decision variable. We show that once the production rate becomes positive, it does not become zero again. This implies production smoothing. However, none of the gains of production smoothing are passed on to the retailer. The optimal production rate and the inventory policy are a linear combination of the nominal demand rate, the peak demand factor, the salvage value, and the initial inventory. Also, as opposed to some of the existing literature, the optimal policies need not necessarily be concave in nature. In the scenario where the relating operation does not require effort, the pricing policies of the manufacturer and the retailer, and the production policy of the manufacturer have a synergistic effect. However, in the scenario where the retailing operation does benefit from effort, the retailer's pricing policy need not necessarily be synergistic with other policies. With regard to channel structures, it seems that production smoothing will be done more efficiently in the integrated setup. Also, we show that the price paid by the consumer need not necessarily be lower in the integrated setup. But despite higher prices, the channel profits are higher in the integrated setup. This implies a conflict between the interests of the consumers and the firm. Also, this contradicts the results of some of the earlier papers that have used simple static models.     

A bi-objective coordination setup problem in a two-stage production system

This paper addresses a problem arising in the coordination between two consecutive departments of a production system, where parts are processed in batches, and each batch is characterized by two distinct attributes. Due to the lack of interstage buffering between the two stages, these departments have to follow the same batch sequence. In the first department, a setup occurs every time the first attribute of a new batch is different from the one of the previous batch. In the downstream department, there is a setup when the second attribute changes in two consecutive batches. The problem consists in finding a batch sequence optimizing the number of setups paid by each department. This case results in a particular bi-objective combinatorial optimization problem. We present a geometrical characterization for the feasible solution set of the problem, and we propose three effective heuristics, as shown by an extensive experimental campaign. The proposed approach can be also used to solve a class of single-objective problems, in which setup costs in the two departments are general increasing functions of the number of setups.     

Dual subgradient algorithms for large-scale nonsmooth learning problems

“Classical” First Order (FO) algorithms of convex optimization, such as Mirror Descent algorithm or Nesterov’s optimal algorithm of smooth convex optimization, are well known to have optimal (theoretical) complexity estimates which do not depend on the problem dimension. However, to attain the optimality, the domain of the problem should admit a “good proximal setup”. The latter essentially means that (1) the problem domain should satisfy certain geometric conditions of “favorable geometry”, and (2) the practical use of these methods is conditioned by our ability to compute at a moderate cost proximal transformation at each iteration. More often than not these two conditions are satisfied in optimization problems arising in computational learning, what explains why proximal type FO methods recently became methods of choice when solving various learning problems. Yet, they meet their limits in several important problems such as multi-task learning with large number of tasks, where the problem domain does not exhibit favorable geometry, and learning and matrix completion problems with nuclear norm constraint, when the numerical cost of computing proximal transformation becomes prohibitive in large-scale problems. We propose a novel approach to solving nonsmooth optimization problems arising in learning applications where Fenchel-type representation of the objective function is available. The approach is based on applying FO algorithms to the dual problem and using the accuracy certificates supplied by the method to recover the primal solution. While suboptimal in terms of accuracy guaranties, the proposed approach does not rely upon “good proximal setup” for the primal problem but requires the problem domain to admit a Linear Optimization oracle—the ability to efficiently maximize a linear form on the domain of the primal problem.     

The multi-item capacitated lot-sizing problem with setup times and shortage costs

We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem is NP-hard. A mixed integer mathematical formulation is presented. Our approach in this paper is to propose some classes of valid inequalities based on a generalization of Miller et al. [A.J. Miller, G.L. Nemhauser, M.W.P. Savelsbergh, On the polyhedral structure of a multi-item production planning model with setup times, Mathematical Programming 94 (2003) 375–405] and Marchand and Wolsey [H. Marchand, L.A. Wolsey, The 0–1 knapsack problem with a single continuous variable, Mathematical Programming 85 (1999) 15–33] results. We also describe fast combinatorial separation algorithms for these new inequalities. We use them in a branch-and-cut framework to solve the problem. Some experimental results showing the effectiveness of the approach are reported.     

Optimal Production and Setup Scheduling: A One-Machine, Two-Product System

This paper studies the scheduling problem for two products on a single production facility. The objective is to specify a production and setup policy that minimizes the average inventory, backlog, and setup costs. Assuming that the production rate can be adjusted during the production runs, we provide a close form for an optimal production and setup schedule. Dynamic programming and Hamilton–Jacobi–Bellman equation is used to verify the optimality of the obtained policy.     

Solving the capacitated lot-sizing problem with backorder consideration

In this research, we formulate and solve a type of the capacitated lot-sizing problem. We present a general model for the lot-sizing problem with backorder options, that can take into consideration various types of production capacities such as regular time, overtime and subcontracting. The objective is to determine lot sizes that will minimize the sum of setup costs, holding cost, backorder cost, regular time production costs, and overtime production costs, subject to resource constraints. Most existing formulations for the problem consider the special case of the problem where a single source of production capacity is considered. However, allowing for the use of alternate capacities such as overtime is quite common in many manufacturing settings. Hence, we provide a formulation that includes consideration of multiple sources of production capacity. We develop a heuristic based on the special structure of fixed charge transportation problem. The performance of our algorithm is evaluated by comparing the heuristic solution value to lower bound value. Extensive computational results are presented.     

Control of arrivals in a finite buffered queue with setup costs

We consider finite buffered queues where the arrival process is controlled by shutting down and restarting the arrival stream. In the absence of holding costs for items in the queue, the optimal (s,?S) policy can be characterised by relating the arrival control problem to a corresponding service control problem. With the inclusion of holding costs however, this characterisation is not valid and efficient numerical computation of the queue length probability distribution is necessary. We perform this computation by using a duality property which relates queue lengths in the controlled arrival system to a controlled service system. Numerical results which analyse the effect of setup and holding costs and the variability of the arrival process on the performance of the system are included.     

Metaheuristic algorithms for balancing robotic assembly lines with sequence-dependent robot setup times

Industries are incorporating robots into assembly lines due to their greater flexibility and reduced costs. Most of the reported studies did not consider scheduling of tasks or the sequence-dependent setup times in an assembly line, which cannot be neglected in a real-world scenario. This paper presents a study on robotic assembly line balancing, with the aim of minimizing cycle time by considering sequence-dependent setup times. A mathematical model for the problem is formulated and CPLEX solver is utilized to solve small-sized problems. A recently developed metaheuristic Migrating Birds Optimization (MBO) algorithm and set of metaheuristics have been implemented to solve the problem. Three different scenarios are tested (with no setup time, and low and high setup times). The comparative experimental study demonstrates that the performance of the MBO algorithm is superior for the tested datasets. The outcomes of this study can help production managers improve their production system in order to perform the assembly tasks with high levels of efficiency and quality.     

Production-inventory control policy under warm/cold state-dependent fixed costs and stochastic demand: partial characterization and heuristics

The motivation for our study comes from some production and inventory systems in which ordering/producing quantities that exceed certain thresholds in a given period might eliminate some setup activities in the next period. Many examples of such systems have been discussed in prior research but the analysis has been limited to production settings under deterministic demand. In this paper, we consider a periodic-review production-inventory model under stochastic demand and incorporate the following fixed-cost structure into our analysis. When the order quantity in a given period exceeds a specified threshold value, the system is assumed to be in a “warm” state and no fixed cost is incurred in the next period regardless of the order quantity; otherwise the system state is considered “cold” and a positive fixed cost is required to place an order. Assuming that the unsatisfied demand is lost, we develop a dynamic programming formulation of the problem and utilize the concepts of quasi-K-convexity and non-K-decreasing to show some structural results on the optimal cost-to-go functions. This analysis enables us to derive a partial characterization of the optimal policy under the assumption that the demands follow a Pólya or uniform distribution. The optimal policy is defined over multiple decision regions for each system state. We develop heuristic policies that are aimed to address the partially characterized decisions, simplify the ordering policy, and save computational efforts in implementation. The numerical experiments conducted on a large set of test instances including uniform, normal and Poisson demand distributions show that a heuristic policy that is inspired by the optimal policy is able to find the optimal solution in almost all instances, and that a so-called generalized base-stock policy provides quite satisfactory results under reasonable computational efforts. We use our numerical examples to generate insights on the impact of problem parameters. Finally, we extend our analysis into the infinite horizon setting and show that the structure of the optimal policy remains similar.     

Exact and heuristic solution approaches for the mixed integer setup knapsack problem

We consider a class of knapsack problems that include setup costs for families of items. An individual item can be loaded into the knapsack only if a setup cost is incurred for the family to which it belongs. A mixed integer programming formulation for the problem is provided along with exact and heuristic solution methods. The exact algorithm uses cross decomposition. The proposed heuristic gives fast and tight bounds. In addition, a Benders decomposition algorithm is presented to solve the continuous relaxation of the problem. This method for solving the continuous relaxation can be used to improve the performance of a branch and bound algorithm for solving the integer problem. Computational performance of the algorithms are reported and compared to CPLEX.     

Computing a Stationary Base-Stock Policy for a Finite Horizon Stochastic Inventory Problem with Non-linear Shortage Costs

Abstract

We consider a periodic-review stochastic inventory problem in which demands for a single product in each of a finite number of periods are independent and identically distributed random variables. We analyze the case where shortages (stockouts) are penalized via fixed and proportional costs simultaneously. For this problem, due to the finiteness of the planning horizon and non-linearity of the shortage costs, computing the optimal inventory policy requires a substantial effort as noted in the previous literature. Hence, our paper is aimed at reducing this computational burden. As a resolution, we propose to compute “the best stationary policy.” To this end, we restrict our attention to the class of stationary base-stock policies, and show that the multi-period, stochastic, dynamic problem at hand can be reduced to a deterministic, static equivalent. Using this important result, we introduce a model for computing an optimal stationary base-stock policy for the finite horizon problem under consideration. Fundamental analytic conclusions, some numerical examples, and related research findings are also discussed.     

Optimal investment in setup reduction in manufacturing systems with WIP inventories

A number of models have been proposed to predict optimal setup times, or optimal investment in setup reduction, in manufacturing cells. These have been based on the economic order quantity (EOQ) or economic production quantity (EPQ) model formulation, and have a common limitation in that they neglect work-in-process (WIP) inventories, which can be substantial in manufacturing systems. In this paper a new model is developed that predicts optimal production batch sizes and investments in setup reduction. This model is based on queuing theory, which permits it to estimate WIP levels as a function of the decisions variables, batch size and setup time. Optimal values for batch size and setup time are found analytically, even though the total cost model was shown to be strictly non-convex.