ABC β–a heuristic for dynamic capacitated lot sizing with random demand under a fill rate constraint

This paper deals with the dynamic multi-item capacitated lot-sizing problem (CLSP) with random demand over a finite discrete time horizon. Unfilled demands are backordered. It is assumed that a fill rate constraint is in effect. We propose a heuristic solution procedure called ABC _β that extends the A/B/C heuristic introduced by Maes and Van Wassenhove for the deterministic CLSP to the case of random demands.     

Nesting of two-dimensional parts in multiple plates using hybrid algorithm

Hybrid heuristic algorithms are proposed for the nesting of two-dimensional rectangular parts in multiple plates. The nesting algorithm of Babu and Babu is first modified and a new heuristic nesting algorithm, IBH, is proposed to utilize the material plate further. IBH is then combined in a meta-heuristic approach, simulated annealing. The proposed hybrid algorithms can then be extended to solve the nesting problem involving irregular parts by embedding irregular parts to rectangles. One problem arises in this 'irregular-to-rectangular' process, i.e. conversion of demands of the original irregular parts into demands of the embedding rectangles. A greedy heuristic rule is therefore presented to determine the number of embedding rectangles of different types to be used in order to maximize the utilization of the material plate given that the demand of each irregular part must be satisfied. Promising computational results are obtained and reported by running examples from the literature and data relevant to the footwear industry.     

New Tabu search heuristics for the dynamic facility layout problem

A manufacturing facility is a dynamic system that constantly evolves due to changes such as changes in product demands, product designs, or replacement of production equipment. As a result, the dynamic facility layout problem (DFLP) considers these changes and is defined as the problem of assigning departments to locations during a multi-period planning horizon such that the sum of the material handling and re-arrangement costs is minimised. In this paper, three tabu search (TS) heuristics are presented for this problem. The first heuristic is a simple TS heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic TS heuristic. To test the performances of the heuristics, two sets of test problems from the literature are used in the analysis. The results show that the second heuristic out-performs the other proposed heuristics and the heuristics available in the literature.     

A DISCRETE LOCATION ASSIGNMENT PROBLEM WITH CONGESTION

Given a set of sites, this paper deals with the selection of sites for installing facilities and the assignment of customers to them. The customers have random demands for service and form finite source queues at the installed facilities. The objective is to minimize the expected total cost per unit of time consisting of travel cost, waiting cost for service, and fixed cost for installing and maintaining the facilities. A heuristic algorithm is developed. Computational results supporting the efficiency and accuracy of the heuristic are included. Under specific conditions, the problem is reduced to a linear integer programming problem and is solved by a branch and bound algorithm.     

时滞变质物品库存与运输联合优化模型

针对一类有保鲜期的易腐品——时滞变质物品,考虑需求受价格、广告投入及存货陈列量的影响,在允许缺货和不同的短缺量拖后率下建立该类物品的库存与运输联合优化模型,并针对模型特点设计出一种启发式算法,从而得到最优库存策略及运输策略。给出算例,利用MATLAB7的最优化求解功能容易求出模型的最优解。结果表明:引入由价格、广告和存货陈列量共同决定的需求率,不仅更符合实际,而且有利于将复杂模型转化为关于多项式的问题来处理,大大降低了求解难度,同时节约了求解时间。     

Incorporating Physical Demand Criteria into Assembly Line Balancing

Many assembly line balancing algorithms consider only task precedence and duration when minimizing cycle time. However, disregarding the physical demands of these tasks may contribute to the development of work-related musculoskeletal disorders in the assembly line workers. Three line balancing heuristics that incorporate physical demand criteria were developed to solve the problem of finding assembly line balances that consider both the time and physical demands of the assembly tasks: a ranking heuristic, a combinatorial genetic algorithm, and a problem space genetic algorithm. Each heuristic was tested using 100 assembly line balancing problems. Incorporating physical demands using these algorithms does impact the assembly line configuration. Results indicated that the problem space genetic algorithm was the most adept at finding line balances that minimized cycle time and physical workload placed upon participants. Benefits of using this approach in manufacturing environments are discussed.     

Multi-item production routing problem with backordering: a MILP approach

The aim of this paper is to present mixed integer linear programming formulations for the production routing problem with backordering (PRP-B) and a new hybrid heuristic to solve the problem. The PRP-B is considered in the context of a supply chain consisting of a production facility with limited production and storage capacities and geographically dispersed points of sale with limited storage capacities. The PRP-B integrates multiple item lot sizing decisions and vehicle routing decisions to the points of sale, where backordering of end customer demands is allowed at a penalty. Two integrated mixed integer programming models are formulated and a solution procedure consisting of a relax-and-fix heuristic combined with a local search algorithm is proposed. The numerical results show that this hybrid heuristic outperforms a state-of-the-art MIP commercial solver, in terms of solution quality and CPU times.     

A robust cell formation approach for varying product demands

In cellular manufacturing environments, manufacturing cells are generally formed based on deterministic product demands. In this paper, we consider a system configuration problem with product demands expressed in a number of probabilistic scenarios. An optimization model integrating cell formation and part allocation is developed to generate a robust system configuration to minimize machine cost and expected inter-cell material handling cost. A two-stage Tabu search based heuristic algorithm is developed to find the optimal or near optimal solutions to the NP-hard problem. Numerical examples show that this model leads to an appropriate compromise between system configuration costs and expected material handling costs to meet the varying product demands. These example problems also show that the proposed algorithm is effective and computationally efficient for small or medium size problems.     

A simple linear heuristic for the service constrained random yield problem

We consider the problem of setting order quantities for purchased components subject to uncertainty in the delivery amounts. Assuming the periodic production volumes (demands)to be known and constant, we model this as a random yield problem with the objective of minimizing average inventory cost subject to a service level constraint over the infinite horizon. We first demonstrate that under conditions of random yield, conventional definitions of service can be inappropriate. Then we refine the definition of service for random yield cases and use this to formulate an optimization model. Exact solution of this model proves to be computationally impractical and, as we show, the common heuristic of inflating demands by a constant proportion is not robustly accurate. Therefore, we develop a new heuristic, which we term the linear inflation policy, that specifies a linear function for the inflation factors. Numerical tests indicate that this heuristic can substantially outperform the traditional constant inflation policy and works well relative to a lower bound on the optimal solution on a range of examples.     

A Framework For Probabilistic Vehicle Routing

The stochastic vehicle routing problem is a problem of considerable current importance in operations research and industrial engineering. The basic problem is to determine a fixed set of vehicle routes of minimal expected total distance. All vehicles must leave from and eventually return to a central depot, and capacity constraints and probabilistic customer demands must be satisfied. In previous work, we assumed that the demand at each node i could be modeled by a Poisson distribution with mean Λi and that demands at nodes are mutually independent. We then developed an efficient heuristic solution procedure which was quite effective in generating an excellent set of fixed vehicle routes, as evidenced by extensive computational results. With this previous work as a starting point, in this paper we investigate solution procedures for the case where other appropriate probability distributions are assumed. In addition, we present analytical results describing the various relationships between design parameters and provide a framework for performing perturbation analysis. Finally, we focus on a more flexible model in which demands are correlated.     

A heuristic for production scheduling and inventory control in the presence of sequence-dependent setup times

The consideration of sequence-dependent setup times is one of the most difficult aspects of production scheduling problems. This paper reports on the development of a heuristic procedure to address a realistic production and inventory control problem in the presence of sequence-dependent setup times. The problem considers known monthly demands, variable production rates, holding costs, minimum and maximum inventory levels per product, and regular and overtime capacity limits. The problem is formulated as a Mixed-Integer Program (MIP), where subtour elimination constraints are needed to enforce the generation of job sequences in each month. By relaxing the subtour elimination constraints, the MIP formulation can be used to find a lower bound on the optimal solution. CPLEX 3.0 is used to calculate lower bounds for relatively small instances of this production problem, which are then used to assess the merit of a proposed heuristic. The heuristic is based on a simple short-term memory tabu search method that coordinates linear programming and traveling salesperson solvers in the search for optimal or near-optimal production plans.     

A parallel machine lot-sizing and scheduling problem with a secondary resource and cumulative demand

We investigate a parallel machine multi-item lot-sizing and scheduling problem with a secondary resource, in which demands are given for the entire planning horizon rather than for every single period. All-or-nothing assumption of the discrete lot-sizing and scheduling problem is valid so that a machine is either idle or works at full capacity in a period. The objective is to minimise the number of setups and teardowns. We prove that the problem is NP-hard and present two equivalent formulations. We show some properties of the optimal objective value, give optimality conditions and suggest a heuristic algorithm. We discuss and formulate two possible extensions related to real-life applications. Finally, we carry out computational experiments to compare the two formulations, to determine the effect of our proposed modeling improvements on solution performance, and to test the quality of our heuristic.     

A genetic algorithm-based model for solving multi-period supplier selection problem with assembly sequence

Under fierce market competition, only products that can meet market demands timely and are competitive can enjoy advantages in the market. Production planning is important in enhancing product competitiveness by effectively reducing both production cost and time. To complete the planning task, a better assembly sequence that includes selecting suitable part suppliers and satisfying the multi-period demands should be designed. In this paper, a mathematical model is presented for dealing with this planning problem, and its objective is to minimise the value of integrated criteria. A hybrid heuristic algorithm, which involves guided genetic algorithm combined with Pareto genetic algorithm, known as Guided-Pareto genetic algorithm (Gu-PGA), is developed for solving the addressed problem. Finally, experiments are conducted to validate the proposed algorithm. The results demonstrate that the Gu-PGA is more effective in solving the multi-period supplier selection problem.     

A Petri net-based heuristic for mixed-model assembly line balancing problem of Type-E

To effectively respond to the changing market demands, a manufacturer should produce variety of products with small lots. Thus, multiple products (models) are assembled simultaneously on a same line. However, it is very challenging to balance such an assembly line. This paper conducts a study on balancing a mixed-model assembly line of Type E. To solve this problem, a coloured-timed Petri net model is developed to describe the task precedence relationship. Also, the optimisation problem is formulated as a mathematical programming model. Then, with the models, a two-stage heuristic algorithm is proposed to solve the problem. At the first stage, based on the Petri net model, a P-invariant algorithm (PA) is presented to minimise the number of workstations. At the second stage, a heuristic is proposed to further minimise the cycle time by combining the PA with a binary search algorithm (BSA). Performance of the proposed method is evaluated by an illustrative example and numerical experiments. It is shown that it works well in terms of both solution accuracy and computational efficiency for large size problems.     

Analysis and solution to the single-level batch production smoothing problem

Many companies use mixed-model production systems running under the Just-in-Time philosophy in order to efficiently meet customer demands for a variety of products. Such systems require demand be stable and production sequence be leveled. The production smoothing problem aims at finding level schedules in which the appearances of products are dispersed over the horizon as uniformly as possible. In this paper, the production smoothing problem is extended to a more general manufacturing environment where a single machine can be identified as either the final or the bottleneck stage of the system and products may have arbitrary non-zero setup and processing time requirements on this single machine. An optimization model is built for the problem and a two phase solution methodology is developed. The first phase problem is shown to be NP-hard and a parametric heuristic procedure is proposed for its solution. In contrast, the second phase problem is shown to be efficiently solvable and currently available solution methods are adopted from the literature. A computational study is designed to test the proposed two phase solution methodology and also the parametric heuristic procedure. Computational results show that the proposed two phase solution methodology enables effective and efficient control of the studied manufacturing system, and the heuristic procedure developed for the first phase problem is time efficient and promises near optimal solutions for a variety of test instances.     

Order acceptance in food processing systems with random raw material requirements

This study considers a food production system that processes a single perishable raw material into several products having stochastic demands. In order to process an order, the amount of raw material delivery from storage needs to meet the raw material requirement of the order. However, the amount of raw material required to process an order is not exactly known beforehand as it becomes evident during processing. The problem is to determine the admission decisions for incoming orders so as to maximize the expected total revenue. It is demonstrated that the problem can be modeled as a single resource capacity control problem. The optimal policy is shown to be too complex for practical use. A heuristic approach is proposed which follows rather simple decision rules while providing good results. By means of a numerical study, the cases where it is critical to employ optimal policies are highlighted, the effectiveness of the heuristic approach is investigated, and the effects of the random resource requirements of orders are analyzed.     

Inventory control of raw materials under stochastic and seasonal lead times

Most inventory modelling has assumed stochastic demands and constant lead times. However, here we consider a problem for which the opposite situation holds; namely, there is a known constant demand rate, but lead times are random variables. Moreover, the probability distributions of the lead times change in a seasonal fashion. Also, shortages of raw materials result in lost sales. The goal of this paper is to propose heuristic methods for minimizing the expected costs in such a situation. This study was motivated by a problem of management of raw material at a sawmill.     

Workload allocation in multi-product, multi-facility production systems with setup times

In this article, we model the problem of assigning work to M heterogeneous servers (machines), which arises from exogenous demands for N products, in the presence of nonzero setup times. We seek a workload allocation which minimizes the total expected Work-in-Progress (WIP) inventory. Demands are assumed to arrive according to independent Poisson processes, but the setup and the processing times can have arbitrary distributions. Whenever a machine produces more than one product type, production batch sizes are determined by a group scheduling policy; which is also known as the cyclic-exhaustive polling policy. We formulate the workload allocation problem as a nonlinear optimization problem and then provide several insights gleaned from first order necessary conditions, from numerical examples, and from a close examination of the objective function. For example, we show that increasing either the load or the number of products assigned to a machine, or both, does not necessarily increase its contribution to total WIP. These insights are then used to devise a heuristic workload allocation as well as a lower bound. The heuristic allocation is further refined using a nonlinear optimization algorithm.     

Layout optimization considering production uncertainty and routing flexibility

The unequal area facility layout problem is studied considering both production uncertainty and routing flexibility. Stochastic production quantities are introduced under the assumption of dependent demands and incorporated into the usual objective of material handling cost minimization. Concurrently, alternative routings are considered based on production quantity. An efficient simulation approach is used to estimate the resulting department pairwise flows, both their expected values and variances. Using these estimates, a tabu search heuristic procedure performs the layout design optimization.     

A heuristic approach to grade transition strategy of the HDPE slurry process in different operation modes

To satisfy fast changing market demands, polymer plants are forced to operate under frequent grade transition polices which produce a huge amount of off-specification product and waste the time of normal production. In the present study, a model of grade transition is presented for the industrial continuous high-density polyethylene (HDPE) slurry process, which includes two stirred reactors connected in either parallel mode or series mode. The objective of the study is to maximize the economic benefit and minimize the negative environmental impact of the process. Different objective functions are constructed according to the different operation modes. The trajectories of the operating variables can be optimized successfully with the desired polymer quality targets. A heuristic combined strategy is proposed to solve the unstable problem caused by mathematical optimization during the transition between parallel mode and series mode. The problem is solved from three aspects: temperature, operating variables, and material flow. The result indicates that the heuristic combined grade transition takes longer time, but is more feasible in the restriction of the manipulated variables and therefore more effective in controlling the instantaneous properties of the polymer produced.