The multi-item capacitated lot-sizing problem with safety stocks and demand shortage costs

We address a multi-item capacitated lot-sizing problem with setup times, safety stock and demand shortages. Demand cannot be backlogged, but can be totally or partially lost. Safety stock is an objective to reach rather than an industrial constraint to respect. The problem is np-hard. We propose a Lagrangian relaxation of the resource capacity constraints. We develop a dynamic programming algorithm to solve the induced sub-problems. An upper bound is also proposed using a Lagrangian heuristic with several smoothing algorithms. Some experimental results showing the effectiveness of the approach are reported.     

Pricing and production lot-size/scheduling with finite capacity for a deteriorating item over a finite horizon

Although the lately evolved manufacturing technologies such as enterprise resource planning (ERP) provide a unified platform for managing and integrating core business processes within a firm, the decision-making between marketing and production planning still remains rather disjoint. It is due in large parts to the inherent weaknesses of ERP such as the fixed and static parameter settings and uncapacitated assumption. To rectify these drawbacks, we propose a decision model that solves optimally the production lot-size/scheduling problem taking into account the dynamic aspects of customer's demand as well as the restriction of finite capacity in a plant. More specifically, we consider a single product that is subject to continuous decay, faces a price-dependent and time-varying demand, and time-varying deteriorating rate, production rate, and variable production cost, with the objective of maximizing the profit stream over multi-period planning horizon. We propose both coordinated and decentralized decision-making policies that drive the solution of the multivariate maximization problem. Both policies are formulated as dynamic programming models and solved by numerical search techniques. In our numerical experiments, the solution procedure is demonstrated, comparative study is conducted, and sensitivity analysis is carried out with respect to major parameters. The numerical result shows that the solution generated by the coordinated policy outperforms that by the decentralized policy in maximizing net profit and many other quantifiable measures such as minimizing inventory investment and storage capacity.Scope and purposeWe consider a manufacturing firm who produces and sells a single product that is subjected to continuous decay over a lifetime, faces a price-dependent and time-varying demand function, shortages are allowed and a completely backlogged, and has the objective of determining price and production lot-size/scheduling so as to maximize the total profit stream over multi-period planning horizon. We develop a tactical-level decision model that solves the production scheduling problem taking into account the dynamic nature of customer's demand which is partially controllable through pricing schemes. As analogous to the sales and operations planning, the proposed scheme can be used as a coordination center of the APS system within a generic enterprise resource planning framework which integrates and coordinates distinct functions within a firm.This paper differs from the existing works in several ways. First, we propose a dynamic version of the joint pricing and lot-size/scheduling problem taking into account the capacitated constraint. Second, several key factors being considered in the model, such as the demand rate, deteriorating rate, production rate, and variable production cost are assumed time-varying that reflect the dynamic nature of the market and the learning effect of the production system. A third difference between the past research and ours is that the price can be adjusted upward or downward in our model, making the proposed pricing policy more responsive to the structural change in demand or supply.     

A novel learning based approach for a new integrated location-routing and scheduling problem within cross-docking considering direct shipment

One of the most important problem in supply chain management is the design of distribution systems which can reduce the transportation costs and meet the customer's demand at the minimum time. In recent years, cross-docking (CD) centers have been considered as the place that reduces the transportation and inventory costs. Meanwhile, neglecting the optimum location of the centers and the optimum routing and scheduling of the vehicles mislead the optimization process to local optima. Accordingly, in this research, the integrated vehicle routing and scheduling problem in cross-docking systems is modeled. In this new model, the direct shipment from the manufacturers to the customers is also included. Besides, the vehicles are assigned to the cross-dock doors with lower cost. Next, to solve the model, a novel machine-learning-based heuristic method (MLBM) is developed, in which the customers, manufacturers and locations of the cross-docking centers are grouped through a bi-clustering approach. In fact, the MLBM is a filter based learning method that has three stages including customer clustering through a modified bi-clustering method, sub-problems’ modeling and solving the whole model. In addition, for solving the scheduling problem of vehicles in cross-docking system, this paper proposes exact solution as well as genetic algorithm (GA). GA is also adapted for large-scale problems in which exact methods are not efficient. Furthermore, the parameters of the proposed GA are tuned via the Taguchi method. Finally, for validating the proposed model, several benchmark problems from literature are selected and modified according to new introduced assumptions in the base models. Different statistical analysis methods are implemented to assess the performance of the proposed algorithms.     

A multi-criteria customer allocation problem in supply chain environment: An artificial immune system with fuzzy logic controller based approach

In the present day business environment, customer satisfaction is a pre-requisite for providing good service to the customer. The present day market is a customer driven market and only those who can fulfill customer demands at minimal rate and in shortest time can share a greater market share. Owing to the aforementioned factors, the problem of customers’ allocation to the vendors is considered to be very important problem and has attracted the attention of a lot of researchers. In this paper, a multiple vendor transportation problem having a variety of products and multiple customers has been taken into consideration. The problem considers two criteria: transportation time and transportation cost, thus making it a multi-criteria problem. To solve this problem, a heuristic based on a new approach, called artificial immune system (AIS) has been proposed. To strengthen AIS, a fuzzy logic controller (FLC) has been incorporated in the AIS heuristic. FLC changes the hyper mutation rate adaptively at iteration. A benchmark problem from the prominent literature review has been taken for showing the efficacy of the proposed algorithm. The supremacy of the problem has been shown by the randomly generated data set with increased complicacy of the problems.     

An out-of-kilter based heuristic for the integer multicommodity transportation problem

A new formulation of the multicommodity transportation problem is introduced whereby all supply and demand constraints and in addition, a subset of the capacity constraints are incorporated into an equivalent single commodity, uncapacitated network. Solution of this network problem generally yields stronger lower bounds than one obtains by solving the individual single commodity transportation problems independently. A heuristic algorithm using this formulation is developed for the integer problem and limited computational experience indicates that the new formulation does provide a significant advantage over the unconstrained approach and solutions that are generally within seven percent of the lower bound. The application of this formulation in solving the continuous problem is also discussed.     

Heuristic approaches for master planning in semiconductor manufacturing

In this paper, we propose heuristic approaches for solving master planning problems that arise in semiconductor manufacturing networks. The considered problem consists of determining appropriate wafer quantities for several products, facilities, and time periods by taking demand fulfillment (i.e., confirmed orders and forecasts) and capacity constraints into account. In addition, fixed costs are used to reduce production partitioning. A mixed-integer programming (MIP) formulation is presented and the problem is shown to be NP-hard. As a consequence, two heuristic procedures are proposed: a product based decomposition scheme and a genetic algorithm. The performance of both heuristics is assessed using randomly generated test instances. It turns out that the decomposition scheme is able to produce high-quality solutions, while the genetic algorithm achieves results with reasonable quality in a short amount of time.     

A two-stage heuristic method for vehicle routing problem with split deliveries and pickups

The vehicle routing problem （VRP） is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups （VRPSPDP） is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity, that is, to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm, Solomon benchmark datasets and extended Solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.     

Product mix optimization for a semiconductor fab: Modeling approaches and decomposition techniques

To optimize the product mix of a semiconductor fab, the production capabilities and capacities are matched with the demand in the most profitable way. In this paper we address a linear programming model of the product mix problem considering product dependent demand limits (e.g. obligations and demand forecast) and profits while respecting the capacity bounds of the production facility. Since the capacity consumption is highly dependent on choosing from different production alternatives we are implicitly solving a static capacity planning problem for each product mix. This kind of planning approach is supported by the fluid flow concept and complete resource pooling in high traffic. We propose a general model that considers a wide range of objectives, and we introduce a heuristic that is based on the decomposition of the static capacity planning problem. A computational study reports on the quality of the decomposition approaches, and examples from practice demonstrate the versatility of the model.     

面向个性化订单的家具资源管理系统集成研究

为了解决家具企业对客户个性化需求的快速应变能力和生产供货能力、增加企业的市场份额,通过对家具市场供需矛盾的分析,对家具企业资源管理系统的架构进行了研究,设计了基于SOA面向个性化订单的资源管理系统集成的模型,并给出了模型的应用方法。该模型能够针对个性化订单,使企业在信息资源管理上做出敏捷、快速的反应,解决供需矛盾,实现家具企业与客户的双赢。该模型在某家具企业的应用,得到了较好的效果。     

Stochastic skill-based manpower allocation in a cellular manufacturing system

In this paper, stochastic skill-based manpower allocation problem is addressed, where operation times and customer demand are uncertain. A four-phased hierarchical methodology is developed. Egilmez and Süer's [1] stochastic general manpower allocation problem is extended such that each worker's individual performance is considered for a more accurate manpower allocation to manufacturing cells to maximize the production rate. The proposed methodology optimized the manpower levels, product-cell formations and individual worker assignment hierarchically with respect to a specified risk level. Three stochastic nonlinear mathematical models were developed to deal with manpower level determination, cell loading and individual worker assignment phases. In all models, processing times and demand were assumed to be normally distributed. Firstly, alternative configurations were generated. Secondly, IID sampling and statistical analysis were utilized to convert probabilistic demand into probabilistic capacity requirements. Thirdly, stochastic manpower allocation was performed and products were loaded to cells. In the final phase, individual worker assignments were performed. The proposed methodology was illustrated with an example problem drawn from a real manufacturing company. The hierarchical approach allows decision makers to perform manpower level determination, cell loading and individual worker assignment with respect to the desired risk level. The main contribution of this approach is that each worker's expected and standard deviation of processing time on each operation is considered individually to optimize the manpower assignment to cells and maximize the manufacturing system production rate within a hierarchical robust optimization approach.     

Design of robust cellular manufacturing system for dynamic part population considering multiple processing routes using genetic algorithm

In this paper, a comprehensive mathematical model is proposed for designing robust machine cells for dynamic part production. The proposed model incorporates machine cell configuration design problem bridged with the machines allocation problem, the dynamic production problem and the part routing problem. Multiple process plans for each part and alternatives process routes for each of those plans are considered. The design of robust cell configurations is based on the selected best part process route from user specified multiple process routes for each part type considering average product demand during the planning horizon. The dynamic part demand can be satisfied from internal production having limited capacity and/or through subcontracting part operation without affecting the machine cell configuration in successive period segments of the planning horizon. A genetic algorithm based heuristic is proposed to solve the model for minimization of the overall cost considering various manufacturing aspects such as production volume, multiple process route, machine capacity, material handling and subcontracting part operation.     

需求可拆分车辆路径问题的聚类求解算法

针对传统的车辆路径问题通常假设客户的需求不能拆分,即客户的需求由一辆车满足,而实际上通过需求的拆分可使需要的车辆数更少,从而降低配送成本的问题,分析了需求可拆分的车辆路径问题的解的特征,证明了客户需求不宜拆分应满足的条件,设计了符合解的特征的聚类算法,并对其求解.通过实验仿真,将所提出的聚类算法与蚁群算法和禁忌搜索算法进行比较,所得结果表明了所提出的算法可以更有效地求得需求可拆分车辆路径问题的优化解,是解决需求可拆分车辆路径问题的有效方法.     

Multiple lot-sizing decisions with an interrupted geometric yield and variable production time

This study examines a multiple lot-sizing problem for a single-stage production system with an interrupted geometric distribution, which is distinguished in involving variable production lead-time. In a finite number of setups, this study determined the optimal lot-size for each period that minimizes total expected cost. The following cost items are considered in optimum lot-sizing decisions: setup cost, variable production cost, inventory holding cost, and shortage cost. A dynamic programming model is formulated in which the duration between current time and due date is a stage variable, and remaining demand and work-in-process status are state variables. This study then presents an algorithm for solving the dynamic programming problem. Additionally, this study examines how total expected costs of optimal lot-sizing decisions vary when parameters are changed. Numerical results show that the optimum lot-size as a function of demand is not always monotonic.     

A scatter search-based heuristic to locate capacitated transshipment points

We consider a fixed charge two-stage location problem in which a given number of intermediate transshipment points are to be located between the supply plants and the customer locations. Both plants and transshipment points are capacitated. Scatter search is a population-based heuristic that has been applied to several combinatorial optimization problems. We develop an efficient scatter search-based heuristic approach with hybrid improvements including local search and path-relinking routines. Computational results demonstrate the effectiveness of the heuristic even for realistic problems with larger instances and tighter capacities.     

The mixed-product assembly line sequencing problem of a door-lock company in Taiwan

This paper investigates the mixed-product assembly line sequencing problem in the door-lock manufacturing industry. Companies in the door-lock industries schedule their production processes to minimize their costs while meeting customer demand. The variances and diversities of each lock’s components complicate the mixed-product assembly line sequencing problem and directly influence the material requirement planning and human resource costs. In the current research, we study one of the largest ironware manufacturing companies in Asia, company F. For this company, an export-oriented strategy makes its main products (such as door locks and door closers) available around the globe. The primary customers of company F are the largest home improvement co-op stores (such as Home Depot, Lowe’s and True Value in the US) from the region of North America. The sales from this region account for over 80% of company F’s total sales. The remaining company sales are geographically distributed around the world in areas such as Europe, Asia and Australia. However, as labor cost is the major concern, this company seeks supply sources in southeast Asia, China and Taiwan. In this paper, we analyze company F and formulate an integer programming mathematical model with constraints regarding production lines, labor, warehouse capacity and order fulfillment rates to minimize the total cost. The customer demand is derived from real data from company F. We use the branch and bound algorithm (CPLEX) to solve this problem and analyze the results. Salient results and practical issues involved in this unique problem are discussed in detail in this paper.     

Solving the stochastic dynamic lot-sizing problem through nature-inspired heuristics

We investigate the dynamic lot-size problem under stochastic and non-stationary demand over the planning horizon. The problem is tackled by using three popular heuristic methods from the fields of evolutionary computation and swarm intelligence, namely particle swarm optimization, differential evolution and harmony search. To the best of the authors' knowledge, this is the first investigation of the specific problem with approaches of this type. The algorithms are properly manipulated to fit the requirements of the problem. Their performance, in terms of run-time and solution accuracy, is investigated on test cases previously used in relevant works. Specifically, the lot-size problem with normally distributed demand is considered for different planning horizons, varying from 12 up to 48 periods. The obtained results are analyzed, providing evidence on the efficiency of the employed approaches as promising alternatives to the established Wagner–Whitin algorithm, as well as hints on their proper configuration.     

基于启发式带时间窗的车辆路径规划问题求解

车辆路径规划问题广泛地存在于现代物流行业中,该问题属于NP难的组合优化问题.随着客户需求的多样化、道路限行等因素的影响,该问题变得更加的复杂,采用传统的组合优化方法和运筹学方法往往难以求解.本文对一类常见的带时间窗的车辆路径规划问题进行了研究,根据时间窗参数来调整客户的优先级,以减少车辆的等待时间,由此改进了几个常见的启发式算法,并对56个常见的车辆路径规划问题进行了测试,实验结果表明,改进的节约算法在带容量约束的车辆路径问题中效果较好,改进的插入法则在带时间窗的车辆路径问题中具有优越性,另外,改进的启发式算法在4个测试用例上使用更多车辆时可使总路程优于已知最优值.     

Admission control and scheduling in simple series parallel networksusing fuzzy logic

Two outstanding problems of admission control and scheduling in networks with three and two workstations, respectively, are solved using fuzzy logic. Neither problem has been tackled up until now analytically, whereas the fuzzy approach provides computational solutions. In the first case, we have one workstation with two parallel ones. A reward is earned whenever the first stage accepts a customer and a holding cost is incurred by a customer in queue in the second stage. The class of customer to be next served by the first stage is dynamically selected so as to maximize an average benefit over an infinite horizon. In the second case, there are two parallel servers and three arrival processes generated by independent Poisson streams. Each server has its own queue and receives customers from its own arrival stream. A third arrival stream consists of customers with resource demand on both servers. Each customer pays a holding cost per unit time in the system. Again, the scheduling policy is specified which minimizes the average cost. The fuzzy models are new in this context and tackle computationally problems for which we have not analytical solutions     

Selection of cutting conditions for power constrained parallel machine scheduling

Most previous studies on machining optimization focused on aspects related to machining efficiency and economics, without accounting for environmental considerations. Higher cutting speed is usually desirable to maximize machining productivity, but this requires a high power load peak. In Taiwan, electricity prices rise sharply if instantaneous power demand exceeds contract capacity. Many studies over the previous decades have examined production scheduling problems. However, most such studies focused on well-defined jobs with known processing times. In addition, traditional sequencing and scheduling models focus primarily on economic objectives and largely disregard environmental issues raised by production scheduling problems. This study investigates a parallel machine scheduling problem for a manufacturing system with a bounded power demand peak. The challenge is to simultaneously determine proper cutting conditions for various jobs and assign them to machines for processing under the condition that power consumption never exceed the electricity load limit. A two-stage heuristic approach is proposed to solve the parallel machine scheduling problem with the goal of minimizing makespan. The heuristic performance is tested by distributing 20 jobs over 3 machines with four possible cutting parameter settings.     

An improved heuristic for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is an important and practical problem in the OR literature. In short, the problem is to identify routes to service (e.g., pickup or deliver) demand located along the edges of a network such that the total cost of the routes is minimized. In general, a single route cannot satisfy the entire demand due to capacity constraints on the vehicles. CARP belongs to the set of NP-hard problems; consequently numerous heuristic and metaheuristic solution approaches have been developed to solve it. In this paper an “ellipse rule” based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy-add heuristics for this problem. The innovation consists basically of selecting edges only inside ellipses when the vehicle is near the end of each route. This new approach was implemented and tested on three standard datasets and the solutions are compared against: (i) the original path-scanning heuristic; (ii) two other path-scanning heuristics and (iii) the three best known metaheuristics. The results indicate that the “ellipse rule” approach lead to improvements over the three path-scanning heuristics, reducing the average distance to the lower bound in the test problems by about 44%.