Heuristics with guaranteed performance bounds for a manufacturing system with product recovery

We consider a manufacturing system with product recovery. The system manufactures a new product as well as remanufactures the product from old, returned items. The items remanufactured with the returned products are as good as new and satisfy the same demand as the new item. The demand rate for the new item and the return rate for the old item are deterministic and constant. The relevant costs are the holding costs for the new item and the returned item, and the fixed setup costs for both manufacturing and remanufacturing. The objective is to determine the lot sizes and production schedule for manufacturing and remanufacturing so as to minimize the long-run average cost per unit time. We first develop a lower bound among all classes of policies for the problem. We then show that the optimal integer ratio policy for the problem obtains a solution whose cost is at most 1.5% more than the lower bound.     

Batch scheduling of deteriorating reworkables

The problem of scheduling the production of new and recoverable defective items of the same product manufactured on the same facility is studied. Items are processed in batches. Each batch comprises two sub-batches processed consecutively. In the first sub-batch, all the items are newly manufactured. Some of them are of the required good quality and some are defective. The defective items are remanufactured in the second sub-batch. They deteriorate while waiting for rework. This results in increased time and cost for their remanufacturing. All the items in the same sub-batch complete at the same time, which is the completion time of the last item in the sub-batch. Each remanufactured defective item is of the required good quality. It is assumed that the percentage of defective items in each batch is the same. A setup time is required to start batch processing and to switch from manufacturing to remanufacturing. The demands for good quality items over time are given. The objective is to find batch sizes such that the total setup and inventory holding cost is minimized and all the demands are satisfied. Dynamic programming algorithms are presented for the general problem and some important special cases.     

考虑外包的单产品再制造批量决策

在已有动态批量决策问题的基础上,考虑了再制造与外包这两个因素建立了单产品的再制造批量决策模型。对考虑外包的单产品再制造批量决策问题最优解的性质进行了讨论,在此基础上利用动态规划的思想给出了时间复杂性为O(T4)的算法,并用C++实现了本算法,实验表明本算法是有效的。     

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.     

Algorithms for Capacitated,Multi-Item Lot-Sizing without Set-Ups

The multi-item lot-sizing problem considered here is concerned with finding the lot sizes over a horizon of discrete time periods to meet known future demand without incurring backlogs, such that the total cost of production and inventory holding is minimized. The capacity constraints arise because the production of each item consumes capacitated production resources at a given rate. Production is assumed to occur without set-ups. The problem is formulated as a capacitated trans-shipment problem. Use of modern, minimum-cost network flow algorithms, coupled with appropriate starting procedures, allows realistically large problem instances to be solved efficiently; thus obviating the need for specialized algorithms based on restrictive assumptions regarding cost structures.     

Complexity of flow shop scheduling problems with transportation constraints

In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as Automated Guided Vehicles, robots and conveyors, and finished jobs are delivered to warehouses or customers by vehicles such as trucks.This paper investigates two-machine flow shop scheduling problems taking transportation into account. The finished jobs are transferred from the processing facility and delivered to customers by truck. Both transportation capacity and transportation times are explicitly taken into account in these models. We study the class of flow shop problems by analysing their complexity. For the makespan objective function, we prove that this problem is strongly NP-hard when the capacity of a truck is limited to two or three parts with an unlimited buffer at the output of the each machine. This problem with additional constraints, such as blocking, is also proven to be strongly NP-hard.     

Random fuzzy EOQ model with imperfect quality items

This paper investigates an economic order quantity (EOQ) problem with imperfect quality items, where the percentage of imperfect quality items in each lot is characterized as a random fuzzy variable while the setup cost per lot, the holding cost of each unit item per day, and the inspection cost of each unit item are characterized as fuzzy variables, respectively. In order to maximize the expected long-run average profit, a random fuzzy EOQ model is constructed. Since it is almost impossible to find an analytic method to solve the proposed model, a particle swarm optimization (PSO) algorithm based on the random fuzzy simulation is designed. Finally, the effectiveness of the designed algorithm is illustrated by a numerical example.     

Theory of exchange

In the context of production activity, several parameters play an important role in the total cost estimation and its optimization. These parameters include facility setup cost, inventory carrying cost, and manufacturing cost for the basic model. Shortages can be incorporated in certain environment and costs associated with shortages need to be included in the analysis. It is expected that the industries will run their manufacturing facility at an optimum level. In the multi-product manufacture, optimum common cycle time approach is usually adopted and all the items are produced in each cycle. A situation may occur in the real world, in which a particular parameter concerning an item is exchanged with that of another item. It is of interest to examine the aftereffects. Otherwise also, for the purpose of internal benchmarking, a deliberate exchange of parameters can take place. This can be implemented in case of cost improvement. A generalized approach is presented and discussion is made with reference to various parameters.     

Balancing capacity and lot sizes

In many companies there is an on-going discussion about capacity, capacity utilization and capital tied up in inventories. However, traditional models such as the EOQ model only include capacity considerations in the set-up cost, or in the cost of a replenishment order. This implies e.g. that they do not consider the set-up time as a capacity constraint. Furthermore, in these models the set-up cost is usually treated as a constant, even though the opportunity cost for capacity in general is dependent upon the capacity utilization.The purpose of this paper is to derive an analytical model for the balancing of capacity and lot sizes. The model includes costs for capacity, work-in-process (queueing, set-up, and processing time), and finished goods inventory. The total costs are minimized with respect to capacity. Then, the corresponding, recommended lot sizes are determined. The model was tested with data from a Swedish manufacturing company. The results turned out to coincide with experiences of the company in many important respects. The model offers production management an opportunity to discuss the relationship between capacity, work-in-process, and lot sizes.     

The static stochastic knapsack problem with normally distributed item sizes

This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item’s value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the expected net profit resulting from the assignment of items to the knapsack. Although the capacity is fixed in our core model, we show that problems with random capacity, as well as problems in which capacity is a decision variable subject to unit costs, fall within this class of problems as well. We focus on the case where item sizes are independent and normally distributed random variables, and provide an exact solution method for a continuous relaxation of the problem. We show that an optimal solution to this relaxation exists containing no more than two fractionally selected items, and develop a customized branch-and-bound algorithm for obtaining an optimal binary solution. In addition, we present an efficient heuristic solution method based on our algorithm for solving the relaxation and empirically show that it provides high-quality solutions.     

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.     

Dynamic economic lot size model with perishable inventory and capacity constraints

In this study, we consider a dynamic economic lot sizing problem for a single perishable item under production capacities. We aim to identify the production, inventory and backlogging decisions over the planning horizon, where (i) the parameters of the problem are deterministic but changing over time, and (ii) producer has a constant production capacity that limits the production amount at each period and is allowed to backorder the unmet demand later on. All cost functions are assumed to be concave. A similar problem without production capacities was studied in the literature and a polynomial time algorithm was suggested (Hsu, 2003 [1]). We assume age-dependent holding cost functions and the deterioration rates, which are more realistic for perishable items. Backordering cost functions are period-pair dependent. We prove the NP-hardness of the problem even with zero inventory holding and backlogging costs under our assumptions. We show the structural properties of the optimal solution and suggest a heuristic that finds a good production and distribution plan when the production periods are given. We discuss the performance of the heuristic. We also give a Dynamic Programing-based heuristic for the solution of the overall problem.     

Simultaneous optimization of capacity and planned lead time in a two-stage production system with different customer due dates

We consider a two-stage make-to-order manufacturing system with random demands, processing times, and distributed customer due dates. The work to each stage is released based on a planned lead time. A general approach to minimize total inventory holding and customer order tardiness cost is presented to find the optimal manufacturing capacities and planned lead times for each manufacturing stage. Expressions are derived for work-in process inventories, finished-goods-inventory and expected backorders under the assumption of a series of M/M/1 queuing systems and exponentially distributed customer required lead times. We prove that the distribution of customer required lead time has no influence on the optimal planned lead times whenever capacity is predefined but it influences the optimal capacity to invest into. For the simultaneous optimization of capacity and planned lead times we present a numerical study that shows that only marginal cost decreases can be gained by setting a planned lead time for the upstream stage and that a considerable cost penalty is incurred if capacity and planned lead time optimization are performed sequentially.     

Optimization of a Few Lot Sizes to Cover a Range of Requirements

In some stock holding situations, only a small number of lot sizes is feasible or even desirable. This paper defines rules for obtaining the optimal ratios between the lot sizes and for determining the range of requirements appropriate to each lot size.In particular, results have been tabulated for a log-normal distribution of requirements. It is found that with only a small number of lot sizes there is a very small increase in cost above the theoretical minimum. It is shown how the results can be simplified in the design of re-ordering systems with negligible increase in cost.An example is given which shows how the grouped items can also be ordered with simple frequencies.     

Packing items to feed assembly lines

We treat a practical application of packing problems in feeding assembly lines. This study was motivated by a real situation encountered in the shop floor of a major automobile industry plant in Brazil. The assembly line feed problem (LFP) consists in how pack the items in the available containers to meet the line work centers’ requirements with a minimum total cost over the planning horizon. LFP is a variable-sized bin packing problem that has two special features: (i) a cardinality constraint on each bin’s size; and, (ii) a cost structure such that each bin’s cost varies according to the items that are packed in it. We propose an integer programming model and a GRASP heuristic for LFP. Numerical results on real-life test instances are reported.     

Controlling multi-indenture repairable inventories of multiple aircraft parts

This paper presents a model for determining stock levels of repairable items supporting a fleet of commercial aircraft operated by a transportation company in the Philippines. The items are characterised by infrequent demand, high cost and a hierarchical (or indentured) structure. The system has three re-supply sources of serviceable parts, namely, the in-house repair shop, the out-house repair shops, and the suppliers. Non-repairable items are scrapped and replaced with new items on a one-for-one basis. The model considers two levels of indenture represented by modules and components. The objective is to minimise the total expected steady-state annual cost of holding inventories and of aircraft delays. A minimum requirement on module availability is also applied. The formulation is such that the regular discrete optimisers available could not be readily used to solve it. The model is implemented on an illustrative problem, employing an integer search for the item stock levels within a limited range.     

A two-echelon stochastic facility location model for humanitarian relief logistics

We develop a two-stage stochastic programming model for a humanitarian relief logistics problem where decisions are made for pre- and post-disaster rescue centers, the amount of relief items to be stocked at the pre-disaster rescue centers, the amount of relief item flows at each echelon, and the amount of relief item shortage. The objective is to minimize the total cost of facility location, inventory holding, transportation and shortage. The deterministic equivalent of the model is formulated as a mixed-integer linear programming model and solved by a heuristic method based on Lagrangean relaxation. Results on randomly generated test instances show that the proposed solution method exhibits good performance up to 25 scenarios. We also validate our model by calculating the value of the stochastic solution and the expected value of perfect information.     

Integrated Production Inventory Policies for Multistage Multiproduct Batch Production Systems

An integrated production inventory model is considered in this paper, for a flow shop type multiproduct batch production system, with a multifacility structure. Instantaneous production is allowed in each facility. The model aims to determine simultaneously the optimal manufacturing cycle for the multiple products and the corresponding optimal procurement policies for the raw material. The cycle concept of multiproduct batch processing is extended to multifacility system and is integrated with the concept of production-inventory system for a single product, single facility system.     

3.1. OR in banking

In this paper, we describe a deterministic multiperiod capacity expansion model in which a single facility serves the demand for many products. Potential applications for the model can be found in the capacity expansion planning of communication systems as well as in the production planning of heavy process industries. The model assumes that each capacity unit simultaneously serves a prespecified (though not necessarily integer) number of demand units of each product. Costs considered include capacity expansion costs, idle capacity holding costs, and capacity shortage costs. All cost functions are assumed to be nondecreasing and concave. Given the demand for each product over the planning horizon, the objective is to find the capacity expansion policy that minimizes the total cost incurred. We develop a dynamic programming algorithm that finds optimal policies. The required computational effort is a polynomial function of the number of products and the number of time periods. When the number of products equals one, the algorithm reduces to the well-known algorithm for the classical dynamic lot size problem.     

Layout designs in cellular manufacturing

Cellular manufacturing (CM) is now an established international practice to integrate: equipment, people, and systems into `focused factories', `mini-businesses' or `cells' with clear customers, responsibilities and boundaries. The major elements in exploiting the benefits of CM is efficient layout designs. This paper presents the application of recently developed multi-objective inter- and intra-cell layout designs methodologies in a CM environment by the author to a dynamic food manufacturing and packaging company in Australia. Some of the problems expressed by the company were large and unnecessary volume of shop floor material handling cost, difficulties and confusion over production planning, long products lead times resulting in losing customers and high overhead costs. Furthermore the company was deeply concerned about the increasing number of accidents and injuries on the shop floor caused by poor layout of machinery and the lack of proper aisle structures for movement of the lift-trucks. This paper shows the process of developing the final inter-cell layout designs by providing the management with multiple layout configurations and showing the impact of each design on the material handling cost at each stage. These solutions not only provide a safer shop floor but also significant reductions in material handling cost, waste, need for large capital investment and the number of lift-trucks needed on the shop floor.