An association-based clustering approach to order batching considering customer demand patterns

Research on warehousing systems has gained interest since the 1980s, reflecting the fact that supply chain management has pursued a demand-driven organization with high product variety, small order sizes, and reliable short response times throughout the supply chain. This market trend has affected warehouse management and operations tremendously. Order batching in a warehouse attempts to achieve high-volume order processing operations by consolidating small orders into batches. Order batching is an essential operation of order processing in which several orders are grouped into batches. This paper describes the development of an order batching approach based on data mining and integer programming. It is valuable to discover the important associations between orders such that the occurrence of some orders in a batch will cause the occurrence of other orders in the same batch. An order-clustering model based on 0–1 integer programming can be formulated to maximize the associations between orders within each batch. From the results of several test problems, the proposed approach shows its ability to find quality solutions of order batching problems.     

B2C电子商务环境下订单拣选与配送联合调度优化

如何在顾客下单后协调好拣选和配送环节,在最短的时间、以较低的成本将商品从货架上拣出、打包后配送到顾客手中,已成为B2C电子商务物流管理中亟待解决的问题。本文尝试以最小化订单履行时间为目标,构建非线性拣选与配送联合调度模型,以解决订单拣选顺序、拣选作业方式、车辆行驶线路等联合决策。为求解此NP难问题,设计了三阶段启发式算法：首先采用“聚类-路径优化”思想,依据顾客位置进行配送方案确认;然后采用基于相似度聚类的订单分批规则对每条配送线路的订单进行分批合并;最后调整拣选任务与配送线路顺序。通过数据实验对模型进行验证,并与传统拣选与配送分开优化的结果进行对比。结果表明,三阶段算法能够有效缩短订单完成时间、降低配送车辆等待时间、改善配送资源利用率。     

基于JIT装配模式的网上超市订单分拣优化模型

订单分拣是大型网上超市生存和发展的关键环节，如何在数百万种商品中将订单要求的商品高效、准确地进行拣选并包装，是亟待解决的难题。本文以提高大型网上超市订单分拣方法的科学性为目标，针对订单拣选、集货复核、包装这一作业流程，基于JIT装配流水线思想，建立大型网上超市订单成组分拣的优化模型与求解方法。在构建订单分拣流程中各工序作业时间计算模型的基础上，建立了订单分批与排序的联合优化模型。围绕缩减求解空间的思想提出两阶段启发式优化方法。通过应用实例分析和灵敏度分析证明了算法的有效性。结果表明，本文提出的网上超市订单成组分拣方法相较于传统方法可较大幅度提高订单分拣的效率，为网上零售企业的订单拣选和包装作业流程的优化提供了理论指导。     

一类新型批处理机调度问题的理论分析

钢卷在冷轧生产中,为了改进其性能,需要在罩式炉进行退火,退火过程由加热、保温和降温三段组成,而这三段处理时间由于工艺上的要求不能归结为一个时间,这与传统批处理机调度有明显的差别.对新型批处理机的总加权完成时间最小化问题建立了非线性整数规划模型,开发了基于动态规划的启发式算法.通过理论分析,获得该算法的误差性能比为3.对于三段中的某一段板卷的处理时间相同的情况,证明了启发式算法的误差性能比是2,而且证明是紧界.对于三段中的某二段板卷的处理时间相同的情况,证明了启发式算法是最优算法.对启发式算法扩展到带有任意段的加工时间的一般情况进行了性能分析.     

Testing Systems of Identical Components

We consider the problem of testing sequentially the components of a multi-component reliability system in order to figure out the state of the system via costly tests. In particular, systems with identical components are considered. The notion of lexicographically large binary decision trees is introduced and a heuristic algorithm based on that notion is proposed. The performance of the heuristic algorithm is demonstrated by computational results, for various classes of functions. In particular, in all 200 random cases where the underlying function is a threshold function, the proposed heuristic produces optimal solutions.     

考虑交货因素的热轧无缝钢管订单排程模型与算法

无缝钢管的市场需求具有多品种、小批量的特点，为了在满足客户需求的同时保证高效连续化生产，文章在满足生产工艺特征的基础上将配送地址和交货期等合同因素引入热轧无缝钢管订单排程问题中，建立了以适期交货、订单集中生产配送和最小化机器设备调整为优化目标的订单排程优化模型，并设计了两阶段求解算法：首先，以订单交货期与配送地址差异最小为目标，基于凝聚策略设计了订单聚类算法，将具有相同工艺约束、相似合同要求的订单进行聚类，并形成初始轧制计划；然后，以设备调整和提前/拖期最小为目标，设计混合变邻域搜索算法，对初始轧制批次进行排程优化。基于实际订单数据的实验结果表明，模型和算法对问题的描述和求解是可行有效的。     

Storing Fresh Produce for Fast Retrieval in an Automated Compact Cross‐Dock System

We study temporary storage of fresh produce in a cross‐dock center. In order to minimize cooling cost, compact storage systems are used. A major disadvantage of these systems is that additional retrieval time is needed, caused by necessary reshuffles due to the improper storage sequence of unit loads. In practice therefore, a dedicated storage policy is used in which every storage lane in the system accommodates only one product. However, this policy does not use the planned arrival time information of the outbound trucks. To exploit this information, this study proposes a mathematical model for a shared storage policy that minimizes total retrieval time. The policy allows different products to share the same lane. In order to solve real‐sized problems, an effective and efficient heuristic is proposed, based on a greedy construction and an improvement part, which provides near optimal solutions. The gaps between the results of the heuristic and the lower bound are mostly less than 1%. The resulting shared storage policy is generally robust against disturbances in arrival or departure times. We compare our shared storage heuristic with dedicated storage to determine which policy performs best under which circumstances. For most practical cases, shared storage appears to outperform dedicated storage, with a shorter response time and better storage lane utilization.     

Revenue Management in Order‐Driven Production Systems

This article investigates the effectiveness of a tactical demand‐capacity management policy to guide operational decisions in order‐driven production systems. The policy is implemented via a heuristic that attempts to maximize revenue by selectively accepting or rejecting customer orders for multiple product classes when demand exceeds capacity constantly over the short term. The performance of the heuristic is evaluated in terms of its ability to generate a higher profit compared to a first‐come‐first‐served (FCFS) policy. The policies are compared over a wide range of conditions characterized by variations in both internal (firm) and external (market) factors. The heuristic, when used with a Whole Lot order‐processing approach, produces higher profit compared to FCFS when profit margins of products are substantially different from each other and demand exceeds capacity by a large amount. In other cases it is better to use the heuristic in conjunction with the Split Lot order‐processing approach.     

Production quantity allocation for order fulfilment in the supply chain: a neural network based approach

In the current global business environment, it is very important to know how to allocate products from the producer to buyers (or distributors). If products are not appropriately distributed due to absence of an effective allocation policy, the producer and buyers cannot expect to increase customer satisfaction and financial profit. Sometimes some buyers can order more than the actual demand due to inappropriately forecasting customer orders. This is the big obstacle to the effective allocation of products. If the producer can become aware of buyers’ actual demands, it is possible to realise high-level order fulfilment through the effective allocation of products. In this study, new allocation policies are proposed considering buyers’ demands. The back propagation algorithm, one of the learning algorithms in neural network theory, is used to recognise actual demands from the previous buyers’ orders. After excluding surplus demands included in buyers’ demands, products are allocated to buyers according to one of the existing allocation policies depending on the company's decision. In the numerical examples, new allocation policies reducing buyers’ surplus demands outperform previous allocation policies with respect to average amount of backorder.     

SIMULTANEOUS BATCHING AND SCHEDULING FOR CHEMICAL PROCESSING WITH EARLINESS AND TARDINESS PENALTIES

We consider the problem of determining the allocation of demand from different customer orders to production batches and the schedule of resulting batches to minimize the total weighted earliness and tardiness penalties in context of batch chemical processing. The problem is formulated as a mixed-integer nonlinear programming model. An iterative heuristic procedure that makes use of the network nature of the problem formulation is presented to approximate an optimal solution. An algorithm polynomial in the number of batches to produce is also presented that optimally solves the problem under special cost structures.     

Joint production and subcontracting planning of unreliable multi-facility multi-product production systems

This article addresses the problem of joint optimization of production and subcontracting of unreliable production systems. The production system considered presents a common problem in the pharmaceutical industry. It is composed of multiple production facilities with different capacities, each of which is capable of producing two different classes of medications (brand name and generic). The resort to subcontracting is double: first, it involves the quantity of products received on a regular basis in order to compensate for insufficient production capacity in existing facilities, second, when needed, urgent orders are also launched in order to reduce the risk of shortages caused by breakdowns of manufacturing facilities. Failures, repairs and urgent delivery times may be represented by any probability distributions.The objective is to propose a general control policy for the system under consideration, and to obtain, in the case of two facilities, optimal control parameters that minimize the total incurred cost for a specific level of the customer service provided. Given the complexity of the problem considered, an experimental optimization approach is chosen in order to determine the optimal control parameters. This approach includes experimental design, analysis of variance, response surface methodology and simulation modeling. It allows the accurate representation of the dynamic and stochastic behaviors of the production system and the assessment of optimal control parameters. Other control parameters which represent the subcontracting are introduced and three joint production/subcontracting control policies (general, urgent, regular) are compared to one another. The proposed joint production/regular subcontracting control policy involves a cost decrease of up to 20%, as compared to results obtained by Dror et al. [1], who used a simplified control policy in addition to a heuristic solution approach for a real case study. This policy offers not only cost savings, but is also easier to manage, as compared to that proposed by Dror et al. [1]. Numerical examples and a sensitivity analysis are also performed to illustrate the robustness of the proposed control policy and the solution approach.     

Myopic Analysis for Multi‐Echelon Inventory Systems with Batch Ordering and Nonstationary/Time‐Correlated Demands

We provide an exact myopic analysis for an N‐stage serial inventory system with batch ordering, linear ordering costs, and nonstationary demands under a finite planning horizon. We characterize the optimality conditions of the myopic nested batching newsvendor (NBN) policy and the myopic independent batching newsvendor (IBN) policy, which is a single‐stage approximation. We show that echelon reorder levels under the NBN policy are upper bounds of the counterparts under both the optimal policy and the IBN policy. In particular, we find that the IBN policy has bounded deviations from the optimal policy. We further extend our results to systems with martingale model of forecast evolution (MMFE) and advance demand information. Moreover, we provide a recursive computing procedure and optimality conditions for both heuristics which dramatically reduces computational complexity. We also find that the NBN problem under the MMFE faced by one stage has one more dimension for the forecast demand than the one faced by its downstream stage and that the NBN policy is optimal for systems with advance demand information and stationary problem data. Numerical studies demonstrate that the IBN policy outperforms on average the NBN policy over all tested instances when their optimality conditions are violated.     

Experimental Results Indicating Lattice‐Dependent Policies May Be Optimal for General Assemble‐To‐Order Systems

We consider an assemble‐to‐order (ATO) system with multiple products, multiple components which may be demanded in different quantities by different products, possible batch ordering of components, random lead times, and lost sales. We model the system as an infinite‐horizon Markov decision process under the average cost criterion. A control policy specifies when a batch of components should be produced, and whether an arriving demand for each product should be satisfied. Previous work has shown that a lattice‐dependent base‐stock and lattice‐dependent rationing (LBLR) policy is an optimal stationary policy for a special case of the ATO model presented here (the generalized M‐system). In this study, we conduct numerical experiments to evaluate the use of an LBLR policy for our general ATO model as a heuristic, comparing it to two other heuristics from the literature: a state‐dependent base‐stock and state‐dependent rationing (SBSR) policy, and a fixed base‐stock and fixed rationing (FBFR) policy. Remarkably, LBLR yields the globally optimal cost in each of more than 22,500 instances of the general problem, outperforming SBSR and FBFR with respect to both objective value (by up to 2.6% and 4.8%, respectively) and computation time (by up to three orders and one order of magnitude, respectively) in 350 of these instances (those on which we compare the heuristics). LBLR and SBSR perform significantly better than FBFR when replenishment batch sizes imperfectly match the component requirements of the most valuable or most highly demanded product. In addition, LBLR substantially outperforms SBSR if it is crucial to hold a significant amount of inventory that must be rationed.     

Energy-oriented bi-objective optimization for the tempered glass scheduling

This paper investigates a real life bi-objective hybrid flow shop scheduling problem in an energy-intensive manufacturing system, in which glass is produced successively in cutting, printing and tempering stages. The problem aims to simultaneously optimize makespan and the total electricity cost under a time-of-use electricity pricing policy. The glass production has to respect the following environments: (i) the cutting and printing operations are processed in parallel machine environments; (ii) the tempering operation is processed on a batch machine; (iii) machine eligibility and setup time have to be considered in the cutting and printing stages; (iv) the whole manufacturing system is under a time-of-use electricity pricing policy. For the problem, an integer programming model is firstly proposed and shown to be strongly NP-hard. Then a model-based heuristic is adopted and a bi-objective differential evolution algorithm (BODE) is devised based on problem features. Computational experiments on randomly generated instances demonstrated that the BODE outperforms the model-based heuristic in terms of computation time and solution quality. Moreover, with mild increase on computation burden, the BODE significantly outperforms the classic NSGA II in terms of solution quality.     

Distribution lot-sizing models for arborescent supply chains with discrete-period variable demand

This study formulates a novel mixed-integer programming lot-sizing model for arborescent supply chains with discrete-period variable demand and then develops an efficient two-phase heuristic method, in which a combined multi-period demand ordering policy, rather than the lot-for-lot ordering policy usually assumed in previous papers, is adopted. Two important properties are introduced and used to obtain a better initial feasible solution. The good performance of the proposed heuristic method is verified through a comparison with the optimal solution method. It is also shown that the performance of the proposed combined multi-period demand ordering method is superior to that of the lot-for-lot ordering method. Sensitivity analysis is conducted to explore the impacts of changing the values of relevant parameters on the total supply chain cost, the total number of orders and the total number of opened members. Finally, a well-known logistics company in Taiwan is chosen to demonstrate the excellent performance and the aptness of the proposed ordering method.     

A reinforcement-learning approach for admission control in distributed network service systems

In the distributed network service systems such as streaming-media systems and resource-sharing systems with multiple service nodes, admission control (AC) technology is an essential way to enhance performance. Model-based optimization approaches are good ways to be applied to analyze and solve the optimal AC policy. However, due to “the curse of dimensionality”, computing such policy for practical systems is a rather difficult task. In this paper, we consider a general model of the distributed network service systems, and address the problem of designing an optimal AC policy. An analytical model is presented for the system with fixed parameters based on semi-Markov decision process (SMDP). We design an event-driven AC policy, and the stationary randomized policy is taken as the policy structure. To solve the SMDP, both the state aggregation approach and the reinforcement-learning (RL) method with online policy optimization algorithm are applied. Then, we extend the problem by considering the system with time-varying parameters, where the arrival rates of requests at each service node may change over time. In view of this situation, an AC policy switching mechanism is presented. This mechanism allows the system to decide whether to adjust its AC policy according to the policy switching rule. And in order to maximize the gain of system, that is, to obtain the optimal AC policy switching rule, another RL-based algorithm is applied. To assess the effectiveness of SMDP-based AC policy and policy switching mechanism for the system, numerical experiments are presented. We compare the performance of optimal policies obtained by the solutions of proposed methods with other classical AC policies. The simulation results illustrate that higher performance and computational efficiency could be achieved by using the SMDP model and RL-based algorithms proposed in this paper.     

Impacts of buyers' order batching on the supplier's demand correlation and capacity utilization in a branching supply chain

There are several ways for a manufacturer to cope with demand uncertainty, e.g. inventories, capacity and cash. Among these, this study focuses on the second one, the capacity, especially on the problem of investing in flexible facilities and enhancing their utilization via demand management. In a supply chain, demands that an upstream firm (supplier) faces are the purchase orders from the downstream members (buyers). We analyse the impacts of buyers' order batching on the supplier's demand correlation and capacity utilization in a simple branching supply chain, where a supplier does business with two buyers whose market demands are correlated. Our results show that: (i) a supplier whofacesa smaller demand correlation coefficient (i.e. closer to-1) would invest more in flexible facilities; (ii) an increase in order lot size mitigates the correlation of purchase orders; and (iii) a supplier whose facilities are flexible would prefer frequent orders with smaller lots only when market demands are highly negatively correlated. This means that even suppliers whose facilities are flexible would rather prefer infrequent orders with larger lots in the presence of positively correlated demands. Additionally, some managerial implications are discussed.     

Single machine batch scheduling with release times

Motivated by a high-throughput logging system, we investigate the single machine scheduling problem with batching, where jobs have release times and processing times, and batches require a setup time. Our objective is to minimize the total flow time, in the online setting. For the online problem where all jobs have identical processing times, we propose a 2-competitive algorithm and we prove a corresponding lower bound. Moreover, we show that if jobs with arbitrary processing times can be processed in any order, any online algorithm has a linear competitive ratio in the worst case. A preliminary version of a part of this paper was presented at the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). We gratefully acknowledge reviewers’ comments that helped to improve the presentation of this work. Supported by the Swiss SBF under contract no. C05.0047 within COST-295 (DYNAMO) of the European Union. Research carried out while B. Weber was affiliated with the Institute of Theoretical Computer Science, ETH Zurich.     

Coordinated Replenishments from a Common Supplier

Coordinated replenishment strategies may be implemented by jointly ordering multiple items from a common supplier. A major benefit of coordinated replenishment is that it increases the size of shipments, permitting the buyer to enjoy transportation economies without a major increase in average inventory levels. The coordinated replenishment problem is complex because side constraints govern the attainment of transportation rate breaks. The problem is further complicated by the presence of purchase quantity discount opportunities. Thus, the buyer must decide which items to order independently, which items to include in a group order, and the order quantities of each item, governed by the frequency of independent or group orders. We present a mathematical model and a heuristic solution procedure that provide analytical support to the buyer seeking to minimize total costs of replenishing multiple items from a common supplier. The relevant costs are purchase prices, ordering costs, holding costs, and transportation costs. Coordinated replenishment provides nearly a 30 percent reduction in controllable costs relative to independent control. Experimentation with the heuristic has yielded optimal solutions over 88 percent of the time. When optimality was not obtained, the mean penalty was much less than one percent. The average heuristic search was more than two orders of magnitude faster than branch and bound, even for small problems, and possessed a much tighter distribution around the mean search time.     

Order Progress Information: Improved Dynamic Emergency Ordering Policies

Technologies such as radio‐frequency identification and global positioning systems can provide improved real‐time tracking information for products and replenishment orders along the supply chain. We call this type of visibility order progress information. In this paper, we investigate how order progress information can be used to improve inventory replenishment decisions. To this end, we examine a retailer facing a stochastic lead time for order fulfillment. We characterize a replenishment policy that is based on the classical (Q, R) policy and that allows for releasing emergency orders in response to the order progress information. We show that the optimal structure of this policy is given by a sequence of threshold values dependent on order progress information. In a numerical study we evaluate the cost savings due to this improved replenishment policy.