Simulating alternative production policies with sequence-dependent costs

This article studies various sequencing and inventory rules in a manufacturing environment with nonlinear technological coefficients and stochastic demand. Multiple products require setup on a single machine and setup time and setup cost decrease with repeated setups. Furthermore, setup operations for different products have common components and an item can benefit from the setup operation of another item. The single-level, multi-item lot size model is used to model the production environment. The learning curve is used to represent this decrease in setup time with repeated setups. The learning transmission between items affects the scheduling of the products and the resulting model considers simultaneous decisions about lot sizing and sequencing in a nonlinear formulation. The problem is formulated and various production policies are simulated. Two sequencing rules and four inventory rules are examined. A simulation experiment of 6400 runs is used to compare the schedules produced by simple policies and those produced by more involved ones. A statistical analysis of the simulation results indicates that the simple rules perform equally well and in some cases better than the computationally harder rules.     

A new directed graph approach for automated setup planning in CAPP

The task of setup planning is to determine the number and sequence of setups and the machining features or operations in each setup. Now there are three main methods for setup planning, i.e., the knowledge-based approach, the graph-based approach and the intelligence algorithm-based approach. In the knowledge-based and graph-based approaches reported in the literature, the main problem is that there is no guarantee that all precedence cycles between setups can be avoided during setup formation. The methods to break precedence cycles between setups are to split one setup into smaller setups. However, the implementation of this method is difficult and complex. In the intelligence algorithm-based approach, the method to handle the precedence constraints is a penalty strategy, which does not reflect the influence of precedence constraints on setup plans explicitly. To deal with the above deficiencies, a new directed graph approach is proposed to describe precedence constraints explicitly, which consists of three parts: (1) a setup precedence graph (SPG) to describe precedence constraints between setups. During the generation of the SPG, the minimal number of tolerance violations is guaranteed preferentially by the vertex clusters algorithm for serial vertices and the minimal number of setups is achieved by using variants of the breadth-first search. Precedence cycles between setups are avoided by checking whether two serial vertex clusters can generate a cycle; (2) operation sequencing to minimise tool changes in a setup; and (3) setup sequencing to generate optimal setup plans, which could be implemented by a topological sort. The new directed graph approach will generate many optimal or near-optimal setup plans and provide more flexibility required by different job shops. An example is illustrated to demonstrate the effect of the proposed approach.     

Capacitated lot-sizing with sequence dependent setup costs

In this paper we consider a single-stage system where a number of different items have to be manufactured on one machine. Expenditures for the setups depend on the sequence in which items are scheduled on the machine. Holding costs are incurred for holding items in inventory. The demand of the items has to be satisfied without delay, i.e. shortages are not allowed. The objective is to compute a schedule such that the sum of holding and setup costs is minimized with respect to capacity constraints. For this problem which we call capacitated lot-sizing problem with sequence dependent setup costs (CLSD) we formulate a new model. The main differences between the new model and the discrete lot-sizing problem with sequence dependent setup costs (DLSDSD), introduced by Fleischmann, is that continuous lot-sizes are allowed and the setup state can be preserved over idle time. For the solution of the new model we present a heuristic which applies a priority rule. Since the priority values are affected by two significant parameters, we perform a local search in the parameter space to obtain low cost solutions. The solution quality is analyzed by a computational study. The comparison with optimal solutions of small instances shows that the solution quality of our heuristic is acceptable. The Fleischmann approach for the DLSPSD computes upper bounds for our new problem. On the basis of larger instances we show that our heuristic is more efficient to solve the CLSD.     

A joint replenishment policy with individual control and constant size orders

We consider inventory systems with multiple items under stochastic demand and jointly incurred order setup costs. The problem is to determine the replenishment policy that minimises the total expected ordering, inventory holding, and backordering costs–the so-called stochastic joint replenishment problem. In particular, we study the settings in which order setup costs reflect the transportation costs and have a step-wise cost structure, each step corresponding to an additional transportation vehicle. For this setting, we propose a new policy that we call the (s, 𝒬) policy, under which a replenishment order of constant size 𝒬 is triggered whenever the inventory position of one of the items drops to its reorder point s. The replenishment order is allocated to multiple items so that the inventory positions are equalised as much as possible. The policy is designed for settings in which backorder and setup costs are high, as it allows the items to independently trigger replenishment orders and fully exploits the economies of scale by consistently ordering the same quantity. A numerical study is conducted to show that the proposed (s, 𝒬) policy outperforms the well-known (𝒬, S) policy when backorder costs are high and lead times are small.     

An effective approach to multi-item capacitated dynamic lot-sizing problems

In this study we solve the multi-item capacitated dynamic lot-sizing problem, where each item faces a series of dynamic demands, and in each period multiple items share limited production resources. The objective is to find the optimal production plan so as to minimise the total cost, including production cost, inventory holding cost, and fixed setup cost. We consider both single-level and multi-level cases. In the multi-level case, some items are consumed in order to produce some other items and therefore items face internally generated demand in addition to external demands. We propose a simple three-stage approach that is applicable to both classes of problems. In the first stage we perform preprocessing, which is designed to deal with the difficulty due to the joint setup cost (a fixed cost incurred whenever production occurs in a period). In the second stage we adopt a period-by-period heuristic to construct a feasible solution, and in the final stage we further improve the solution by solving a series of subproblems. Extensive experiments show that the approach exhibits very good performance. We then analyse how the superior performance is achieved. In addition to its performance, one appealing feature of our method is its simplicity and general applicability.     

Capacity-constrained reorder intervals for materials requirements planning systems

This paper develops a model for the reorder interval problem for general production systems with constant demand, multiple capacity constraints, commonality, non-instantaneous production, and non-nested reorder intervals. We present this model in the context of a materials requirements planning (MRP) system.

Four simple greedy heuristics are presented to find solutions to the model. A six-factor experiment with 192 test problems is used to evaluate the heuristics. The factors in the experiment included the procedures, number of items, capacity tightness, degree of commonality, setup cost to carrying cost ratio, and setup time to run time ratio. For smaller problems the heuristics are compared with optimal solutions found with an exact branch-and-bound algorithm. For larger problems, the heuristics are compared with a lower bound.

The results of the experiment show that the heuristics provide excellent solutions across all experimental factors. Computing times for the proposed heuristics appear to be practical even for realistic MRP environments with many thousands of items.     

Retrieval Strategies for a Carousel Conveyor

We analyze algorithms that sequence the retrieval of items from a carousel conveyor, and show how the appropriate algorithm depends on the load to which the carousel is subjected. In general, as the load increases, so does the quality of solutions produced by simple heuristics. We conclude by recommending certain greedy heuristics for the problems of sequencing the retrieval of orders and for sequencing the retrieval of the items within each order.     

Exploring the structural properties of the ( D , 0) inventory model

This paper considers the number of defective items in a lot to be a random variable and derives a modified (s, Q) model with stochastic demand and constant lead time. The paper develops explicit results for the case of exponential and uniform demand during lead time when the number of defective items in a lot follows a binomial process. It also investigates the effect of lower setup costs on the operating characteristics of the model. A numerical example is given and sensitivity analysis is performed.     

Scheduling a flow-line manufacturing cell: a tabu search approach

The performance of two heuristic procedures for the scheduling of a flow-line manufacturing cell was compared. We propose a procedure based on a combinatorial search technique known as tabu search. The new procedure is compared with a heuristic based on simulated annealing which was proposed in earlier research. The scheduling problem addressed here differs from the traditional flow-shop scheduling problem in the sense that we are interested in sequencing part families (i.e. groups of jobs which share a similar setup) as well as individual jobs within each family. The results reveal that the tabu search heuristic outperforms the simulated annealing heuristic by generating 'better solutions' in less computation time.     

Setup planning using Hopfield net and simulated annealing

This paper reports a new approach to setup planning of prismatic parts using Hopfield neural net coupled with simulated annealing. The approach deals with setup planning in two stages, i.e.: (1) sequence all the features of a workpiece according to geometric and technological constraints; and (2) identify setups from the sequenced features. In the first stage, the task of feature sequencing is converted to a constraint optimization problem (COP) which is similar to the travelling salesman problem (TSP). The setup time due to setup and tool changes is incorporated into the 'distance' between features, while the precedence and critical tolerance relationships between features are treated as constraints. The Hopfield neural net approach for TSP, i.e. energy function, is adopted to model the COP mathematically where the constraints are attached as additional penalty functions. Simulated annealing is then used to search for the minimum energy state of the net while avoiding the local minima. The feature sequence obtained aims at minimizing the number of setups and tool changes while ensuring little or no violation of feature precedence relationship, thus keeping critical tolerance violation to a minimum. In the second stage, setups are generated from the sequenced features using a vector intersection approach based on common tool approach directions. A case study is presented to demonstrate the effectiveness of this approach. A comparison study between this approach and an existing integer programming setup planning system is also given which indicates the superior efficiency of the proposed approach when dealing with problems with large number of features.     

Product batching and batch sequencing for NC punch presses

This paper proposes a two-stage practical product batching and batch sequencing algorithm for NC punch presses used in the production of precision sheet metal electronics components. The first stage of the algorithm batches a given set of products in order to maximize the number of products in a batch as well as the tool magazine utilization. In this stage, tool magazine constraints such as number of available slots, size of slots, tool configurations and tool locations are taken into consideration. The resulting batches are passed to the second stage of the algorithm which sequences these batches. The sequencing is done by using the ‘ nearest neighbour’ heuristic for the ‘ travelling salesman problem’ Comparison of the new method with the procedure previously used by a manufacturer of such components demonstrated a significant reduction in setup times.     

An integrated setup/fixture planning approach for machining prismatic parts

Setup/fixture planning for machining prismatic parts is usually carried out by grouping features/operations into setups, determining suitable locating surfaces for each setup, and sequencing setups and operations in each setup. The presently developed setup/fixture planning methods can be classified into three categories: multi-constraints, fixture driven, and tolerance analysis planning methods. The multi-constraints planning is theoretically sound, but very difficult to use. In fixture driven planning, the generated setup plans are highly practical, but may not be optimal. Tolerance analysis based planning cannot be used to generate the optimal solution by itself. In this research, a new integrated setup/fixture planning approach is developed to identify the optimal and practical setup/fixture plan. The planning is conducted in four steps. (1) The dissimilarity degree matrix (DDM), operation precedence graph (OPG), and hybrid graph are used to describe the requirements and constraints for setup/fixture planning. (2) A setup precedence graph (SPG) is used to describe precedence constraints between setups. The SPG is generated by the vertex clustering algorithm. Precedence loops among setups are avoided by checking whether two serial vertex clusters can generate a loop. (3) Suitable locating surfaces are selected for each setup in a SPG. When the fixture locating surface and design datum surface are different, two types of dimension recalculations are employed to obtain the dimensions against the locating surfaces. (4) All the candidate setup/fixture plans are evaluated based on the number of setups and recalculation of dimensions. An example is given to demonstrate the effectiveness of the developed approach.     

Component allocation and job sequencing for two series-connected SMD placement machines

The problem of component allocation and sequencing PCB assembly jobs for two series-connected SMD placement machines is addressed. With the allocation of components, a balancing of the workload per PCB for the two machines should be achieved. Furthermore, when switching from one type of PCB to another, setup times must be considered. Two heuristic procedures are developed and tested in extensive numeric analyses of a number of realistic case models. The problem examined and the database used represent a concrete case of an industrial application in which very diversified small jobs are to be processed.     

Performance evaluation of two-stage multi-product kanban systems

We propose an approximate evaluation procedure for a kanban-controlled production system with two stages and multiple products. In the first stage, single-product manufacturing facilities produce items that are the input material for a single multi-product manufacturing facility in the second stage. Each manufacturing facility is controlled by a distinct kanban loop with a fixed number of kanbans. Processing and setup times are exponentially distributed, demand arrivals at the output store of the second stage are Poisson and independent for each product. If a customer's demand cannot be met from stock, the customer either waits or leaves the system, depending on the admissible number of backorders and the current number of waiting customers (partial backordering). We describe a new decomposition-based approximation method for the evaluation of such systems in steady state. We focus on the performance measures average fill rate, average fraction of served demand, and average inventory level. We report the results of several numerical tests. The results indicate that the approximation is sufficiently accurate for a large variety of systems. We also illustrate the effects of increasing the maximum number of backorders on the performance of the system.     

An evaluation of group scheduling heuristics in a flow-line manufacturing cell

When a company adopts cellular manufacturing and creates a cell, one operational problem that must be addressed is how to schedule parts within the cell. Many studies have investigated scheduling rules in a cellular manufacturing environment. However, there has been little consensus on the best scheduling rule to use. To address this lack of consensus, this study evaluated the best scheduling rules from most of these studies in a flow-line cell. The impact of two environmental factors, setup to runtime ratio and number of part families, was also investigated. Out of the five best scheduling rules found, three of these had not been investigated in previous group scheduling studies. The scheduling rule that most often performed best was selecting the part family with the most waiting jobs and sequencing these jobs in shortest processing time order, a relatively simple rule. The more complex rules generally showed poorer performance.     

保证公差要求的装夹和加工顺序自动规划

提出了一个保证公差要求的装夹方案和特征加顺序自动规划方法。该方法根据机床的加工精度确定关键公差特征,以关键公差特征和唯一加工方法特征为基础,将零件的特征模型分解为相同装夹特征集合。该方法具有较快的规划与排序的速度,与设计系统紧密集成,并可在规划的过程中实现零件的整体可制造性评价功能。     

Increasing the profitability and competitiveness in a production environment with random and bounded setup times

The link between makespan and the profitability and competitiveness of a firm is addressed first. We then study the problem of minimising makespan in a two-machine flowshop with setup times. Jobs have random setup times that are bounded within certain intervals. The distributions of job setup times are not known. We propose a polynomial time algorithm that generalises Yoshida and Hitomi's algorithm. The algorithm uses a weighted average of lower and upper bounds for setup times. Different combinations of weights result in nine different versions of the algorithm. The computational results indicate that one of the versions, with equal weights given to the lower and upper bounds of setup times, performs much better than the others. Next, the performance of this best version is compared with that of the optimal solution, which is obtained by Yoshida and Hitomi's algorithm applied to the problem after setup times have been realised. Computational analysis shows that the overall average absolute error of the best algorithm is 0.03%, and this decreases in size as the number of jobs increases. The analysis also shows that the proposed best version yields robust results regardless of setup-time distributions and the range of setup times.     

Scheduling The Production Of Components At A Common Facility

We formulate a problem dealing with the manufacture of components at a single facility for subsequent assembly into end products. Each product requires both unique components and common components, and each production batch requires a setup. An optimal schedule for mean completion time is found by means of an algorithm which combines a sequencing procedure and a dynamic programming procedure.     

Setup adjustment for discrete-part manufacturing processes with asymmetric cost functions

This paper presents a feedback adjustment rule for discrete-part manufacturing processes that experience errors at the setup operation which are not directly observable due to part-to-part variability and measurement error. In contrast to previous work on setup adjustment, the off-target cost function of the process is not symmetric around its target. Two asymmetric cost functions—constant and quadratic functions—are considered in this paper. By introducing a bias term in the feedback adjustment rule, the process quality characteristic converges to the optimal steady-state target from the lower cost side of the cost function. This minimizes the off-target loss incurred during the transient phase of adjustment. A machining application is used to illustrate the proposed adjustment procedure and to demonstrate the savings generated by the proposed feedback adjustment rule compared to an adjustment rule due to Grubbs and to an integral controller. It is shown that the advantage of the proposed rule is significant when the cost of the items is high, items are produced in small lot sizes and the asymmetry of the cost function is large.     

Capacitated lot sizing with parallel machines,sequence-dependent setups,and a common setup operator

In this paper, we consider a special variant of a capacitated dynamic lot sizing problem which, despite its practical relevance, has not been treated sufficiently in the literature. In addition to the significant complexity introduced by the sequence dependency of setup times, the problem is further complicated by the fact that there is only one single setup operator which is responsible for all setups on all machines. Hence, the multi-machine problem cannot be decomposed into multiple single machine problems, as the setup operations must be coordinated among the different machines. In addition, lots are produced in batches whereby the processing time of a lot is a step-wise function of the number of batches per lot. Due to perishability and quarantine issues, time windows for the production are given. We formulate a big-bucket lot sizing model and apply MIP-based heuristics to two industrial data sets.