On-line order batching and sequencing problem with multiple pickers: A hybrid rule-based algorithm

Existing on-line order batching rules, namely fixed time window batching (FTWB) and variable time window batching (VTWB), try to choose the fixed time window in the case of FTWB or the fixed number of orders in the case of VTWB. However, these solutions are not appropriate for the fluctuating order environment. The reasonable assignment of batches to order pickers is also an important issue in order picking systems. Motivated by these issues, we study the problem of integrating on-line order batching and the assignment of the batches, which is called the on-line order batching and sequencing problem with multiple pickers (OOBSPMP). The objective is to minimize the turnover time. To solve the problem, a hybrid rule-based algorithm, referred to FTWB, is proposed in order to form batches and assign them to appropriate pickers under a fluctuating order environment. Three batching situations (off-peak, normal and peak arrival time) and two assigning situations (assigning to one busy picker and assigning to one idle picker) are distinguished. Through a series of experiments, we discover several enlightening findings: (i) the rule-based algorithm demonstrates high effectiveness and efficiency in turnover time with multiple pickers; (ii) the rule-based algorithm leads to an impressive improvement in both saving time and wage costs under different arrival rates, picking devices and time intervals compared with VTWB; (iii) to obtain both good warehouse performance and a reasonable workload distribution, the factors, such as the fixed time window, the average workload per picker and the average idle time per picker are also important issues in analysing the efficiency of order picking systems.     

Batch picking in narrow-aisle order picking systems with consideration for picker blocking

This paper develops strategies to control picker blocking that challenge the traditional assumptions regarding the tradeoffs between wide- and narrow-aisle order picking systems. We propose an integrated batching and sequencing procedure called the indexed batching model (IBM), with the objective of minimizing the total retrieval time (the sum of travel time, pick time and congestion delays). The IBM differs from traditional batching formulations by assigning orders to indexed batches, whereby each batch corresponds to a position in the batch release sequence. We develop a mixed integer programming solution for exact control, and demonstrate a simulated annealing procedure to solve large practical problems. Our results indicate that the proposed approach achieves a 5–15% reduction in the total retrieval time primarily by reducing picker blocking. We conclude that the IBM is particularly effective in narrow-aisle picking systems.     

单机最优分批排序的结构性质

A batch is a subset of jobs which must be processed jointly in either serial or parallel form. For the single machine, batching, total completion time scheduling problems, the algorithmic aspects have been extensively studied in the literature. This paper presents the optimal batching structures of the problems on the batching ways: all jobs in exactly N(arbitrary fix batch number and 1 < N < n) batches.     

Single-machine serial-batching scheduling with a machine availability constraint,position-dependent processing time,and time-dependent set-up time

This article considers the single-machine serial-batching scheduling problem with a machine availability constraint, position-dependent processing time, and time-dependent set-up time. The objective of this problem is to make the decision of batching jobs and sequencing batches to minimize the makespan. To solve the problem, three cases of machine non-availability periods are considered, and the structural properties of the optimal solution are derived for each case. Based on these structural properties, an optimization algorithm is developed and an example is proposed to illustrate this algorithm.     

Batch scheduling and common due-date assignment on a single machine

We consider the problem of scheduling n groups of jobs on a single machine where three types of decisions are combined: scheduling, batching and due-date assignment. Each group includes identical jobs and may be split into batches; jobs within each batch are processed jointly. A sequence independent machine set-up time is needed between each two consecutively scheduled batches of different groups. A due-date common to all jobs has to be assigned. A schedule specifies the size of each batch, i.e. the number of jobs it contains, and a processing order for the batches. The objective is to determine a value for the common due-date and a schedule so as to minimize the sum of the due date assignment penalty and the weighted number of tardy jobs. Several special cases of this problem are shown to be ordinary NP-hard. Some cases are solved in O(n log n) time. Two pseudopolynomial dynamic programming algorithms are presented for the general problem, as well as a fully polynomial approximation scheme.     

Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning

This paper investigates a single machine serial-batching scheduling problem considering release times, setup time, and group scheduling, with the combined effects of deterioration and truncated job-dependent learning. The objective of the studied problem is to minimize the makespan. Firstly, we analyze the special case where all groups have the same arrival time, and propose the optimal structural properties on jobs sequencing, jobs batching, batches sequencing, and groups sequencing. Next, the corresponding batching rule and algorithm are developed. Based on these properties and the scheduling algorithm, we develop a hybrid VNS–ASHLO algorithm incorporating variable neighborhood search (VNS) and adaptive simplified human learning optimization (ASHLO) algorithms to solve the general case of the studied problem. Computational experiments on randomly generated instances are conducted to compare the proposed VNS–ASHLO with the algorithms of VNS, ASHLO, Simulated Annealing (SA), and Particle Swarm Optimization (PSO). The results based on instances of different scales show the effectiveness and efficiency of the proposed algorithm.     

Statistical analysis of steady-state simulations: survey of recent progress

For non-terminating simulations with steady-state responses the following alternative analysis techniques are evaluated: (i) replicated runs (ii) approximately independent subruns or batches (iii) renewal or regenerative analysis. Two general techniques for reducing nonnormality and bias are presented: grouping (or batching) and jackknifing. Applications of the various techniques are discussed. Besides the estimation of the mean, the estimation of variances and quantiles is presented.     

Batching deteriorating items with applications in computer communication and reverse logistics

We study two deterministic scheduling problems that combine batching and deterioration features. In both problems, there is a certain demand for identical good quality items to be produced in batches. In the first problem, each batch is assigned an individual machine that requires a cost and a time to be activated. All the machines are identical, work in parallel, and always produce good quality items. All the items are available at time zero and they deteriorate while waiting for production. Deterioration results in a linear increase of time and cost of production. In the second problem, there is a single machine that produces good quality as well as defective items in batches. Each batch is preceded by a setup time and requires a setup cost. Defective items have to be reworked on the same machine. They deteriorate while waiting for rework. At a time to be decided, the machine switches from production to rework defective items of the current batch. After rework, every defective item has the required good quality. In both problems, the objective is to find batch partitioning such that a linear combination of the production cost and production completion time is minimized. The two problems are observed at computer service providers and also reverse logistics. In computer service providers, machines and items correspond to communication service channels and information transfer tasks, respectively. We reduce both problems to minimizing a function of one variable representing the number of batches. In an optimal solution of either problem, there are at most two different batch sizes. Linear time algorithms are proposed for both problems.     

Two-stage assembly-type flowshop batch scheduling problem subject to a fixed job sequence

This paper discusses a two-stage assembly-type flowshop scheduling problem with batching considerations subject to a fixed job sequence. The two-stage assembly flowshop consists of m stage-1 parallel dedicated machines and a stage-2 assembly machine which processes the jobs in batches. Four regular performance metrics, namely, the total completion time, maximum lateness, total tardiness, and number of tardy jobs, are considered. The goal is to obtain an optimal batching decision for the predetermined job sequence at stage 2. This study presents a two-phase algorithm, which is developed by coupling a problem-transformation procedure with a dynamic program. The running time of the proposed algorithm is O(mn+n⁵), where n is the number of jobs.     

考虑商品数量和商品拣选成本的AGV智能仓库订单分批问题研究

AGV(Automated Guided Vehicle,自动导引车)智能仓库是一种基于“货到人”拣选模式的自动化仓库。本文考虑了订单中商品的需求量和货架上商品的存储量,以极小化货架搬运成本和商品拣选成本为目标,建立了AGV智能仓库订单分批问题的整数规划模型。本文针对订单分批问题的特点,提出了一种基于订单和货架交替选择的贪婪求解算法。对比CPLEX求解器的精确最优解,本文提出的贪婪算法的误差百分比不超过10%,平均误差百分比为5.38%;对比基于相似性的分批算法的求解结果,本文提出的贪婪算法不仅运算时间更短,解的质量也更好。进一步地,对比不考虑商品拣选成本的订单分批模型,本文提出的模型在不明显增加货架搬运成本的前提下,可以大幅度降低商品拣选成本。因此,在订单分批模型中考虑商品拣选成本是非常必要的。     

A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem

Given a set of customer orders and a routing policy, the goal of the order-batching problem?(OBP) is to group customer orders to picking orders (batches) such that the total length of all tours through a rectangular warehouse is minimized. Because order picking is considered the most labor-intensive process in warehousing, effectively batching customer orders can result in considerable savings. The OBP is NP-hard if the number of orders per batch is greater than two, and the exact solution methods proposed in the literature are not able to consistently solve larger instances. To address larger instances, we develop a metaheuristic hybrid based on adaptive large neighborhood search and tabu search, called ALNS/TS. In numerical studies, we conduct an extensive comparison of ALNS/TS to all previously published OBP methods that have used standard benchmark sets to investigate their performance. ALNS/TS outperforms all comparison methods with respect to both average solution quality and run-time. Compared to the state-of-the-art, ALNS/TS shows the clearest advantages on the larger instances of the existing benchmark sets, which assume a higher number of customer orders and higher capacities of the picking device. Finally, ALNS/TS is able to solve newly generated large-scale instances with up to 600 customer orders and six articles per customer order with reasonable run-times and convincing scaling behavior and robustness.     

Batching in single operation manufacturing systems

We introduce a new decision problem important to the efficient operation of resources in manufacturing systems. This problem of ‘batching’ is considered for single machine activities. It is shown that even for these simple models, lot splitting may occur and that these batching decisions may have a dramatic impact on the manufacturing lead time of items to be processed.     

Optimal methods for batch processing problem with makespan and maximum lateness objectives

In this paper we consider the problem of scheduling n jobs on a single batch processing machine in which jobs are ordered by two customers. Jobs belonging to different customers are processed based on their individual criteria. The considered criteria are minimizing makespan and maximum lateness. A batching machine is able to process up to b jobs simultaneously. The processing time of each batch is equal to the longest processing time of jobs in the batch. This kind of batch processing is called parallel batch processing. Optimal methods for three cases are developed: unbounded batch capacity, b > n, with compatible job groups and bounded batch capacity, b  n, with compatible and non compatible job groups. Each job group represents a different class of customers and the concept of being compatible means that jobs which are ordered by different customers are allowed to be processed in a same batch. We propose an optimal method for the problem with incompatible groups and unbounded batches. About the case when groups are incompatible and bounded batches, our proposed method is considered as optimal when the group with maximum lateness objective has identical processing times. We regard this method, however, as a heuristic when these processing times are different. When groups are compatible and batches are bounded we consider another problem by assuming the same processing times for the group which has the maximum lateness objective and propose an optimal method for this problem.     

A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse

Batching customer orders in a warehouse can result in considerable savings in order pickers’ travel distances. Many picker-to-parts warehouses have precedence constraints in picking a customer order. In this paper a joint order-batching and picker routing method is introduced to solve this combined precedence-constrained routing and order-batching problem. It consists of two sub-algorithms: an optimal A^∗-algorithm for the routing; and a simulated annealing algorithm for the batching which estimates the savings gained from batching more than two customer orders to avoid unnecessary routing. For batches of three customer orders, the introduced algorithm produces results with an error of less than 1.2% compared to the optimal solution. It also compares well to other heuristics from literature. A data set from a large Finnish order picking warehouse is rerouted and rebatched resulting in savings of over 5000 kilometres or 16% in travel distance in 3 months compared to the current method.     

Using genetic algorithms for the coordinated scheduling problem of a batching machine and two-stage transportation

This paper considers a coordinated scheduling problem. For the first-stage transportation there is a crane available to transport the product from the warehouse to a batching machine. For the second-stage transportation there is a vehicle available to deliver the completed jobs from the machine shop floor to the customer. The coordinated scheduling problem of production and transportation deals with sequencing the transportation of the jobs and combining them into batches to be processed. The problem of minimizing the sum of the makespan and the total setup cost was proven by Tang and Gong [1] to be strongly NP-hard. This paper proposes two genetic algorithm (GA) approaches for this scheduling problem, with different result representations. The experimental results demonstrate that a regular GA and a modified GA (MGA) can find near-optimal solutions within an acceptable amount of computational time. Among the two proposed metaheuristic approaches, the MGA is superior to the GA both in terms of computing time and the quality of the solution.     

Time-restricted batching models and solution approaches for integrated forward and return product flow handling in warehouses

With the rise of Internet sales, retailers witness increases in returned products, generally because website pictures and specifications tend to be insufficient for customers to determine the right size, colour or suitability of a product. Efficient processing of the return flow can improve inventory management and increase the utilisation of warehouse capacities. Moreover, short response times to customer orders and on-time delivery are critical and shape warehouse operations. To address the problem of integrated order and return job batching, this article proposes two optimisation models with constraints on the delivery time. We propose different objectives in offline and online contexts which require unique solution approaches. Time constraints also need to be taken into account to exploit the different characteristics of order and return jobs, as well as to incorporate response time-oriented objectives. Computational examples confirm the effectiveness of included returns and the impact of consumer-oriented objectives. Finally, a comparison of the proposed solution approaches with batching procedures used by a library warehouse indicates significant savings in travel distance through integrated order and return job processing.     

基于AGV的智能仓库系统订单分批问题研究

研究了基于自动引导小车(AGV)的“货到人”智能仓库订单分批拣选问题, 在同时考虑工作人员拣选商品成本和AGV搬运货架成本的前提下, 建立了以总成本极小化为目标函数的订单分批问题整数规划模型。根据订单中包含的商品信息和商品所在的货架信息构建了描述订单之间关系的加权相似度指标, 分析了加权相似度与总拣选成本之间的正相关关系。基于订单之间的加权相似度设计了求解模型的贪婪算法。利用具体算例进行模拟计算, 分析了加权系数的变化对订单分批结果的影响, 以及加权系数λ的取值与工作人员拣取一件商品的成本c₁和AGV搬运一次货架的成本c₂之间的关系, 得到了贪婪算法中加权系数λ的确定方法。进一步分析了贪婪算法的计算时间和计算效果, 结果显示, 通过适当选取加权系数, 利用贪婪算法可以在短时间内得到订单分批问题的近似最优解;对于小规模算例, 贪婪算法在最坏情况下近似比不超过1.35。利用本文的模型和算法进行订单分批, 兼顾了工作人员拣取商品的成本和AGV搬运货架的成本, 可以有效提高订单拣选效率, 降低订单拣选总成本。     

Analysis of expected queueing delays for decision making in production planning

Concepts such as Time Based Competition and criticism of traditional cost accounting's role as a basis for decision making in production planning have emphasized the need for operational measures as indicators of manufacturing performance. One such measure is the expected queueing delay at a production facility. In this paper a typical bottleneck work center is considered where semi-manufactured products are processed in batches. The expected queueing delay depends on the batch sizes used at the work center. Emphasis is placed on the derivation of analytical expressions of (bounds on) the minimal expected queueing delay that can be achieved by an optimal batching decision. The analytical expressions can be applied easily to support managerial decisions on reduction of setup time and on expansion of capacity.     

Rich routing problems arising in supply chain management

The purpose of this paper is to provide basic models for highly relevant extensions of the classical vehicle routing problem in the context of supply chain management. The classical vehicle routing problem is extended in various ways. We will especially focus on extensions with respect to lotsizing, scheduling, packing, batching, inventory and intermodality. The proposed models allow for a more efficient use of resources, while explicitly taking into account interdependencies among the subproblems. The contribution of this survey is twofold: (i) it provides an overview of recent and suitable literature for the interested scholar and (ii) it presents six integrative models for the above mentioned extensions.     

Serial-batching scheduling with time-dependent setup time and effects of deterioration and learning on a single-machine

This paper deals with serial-batching scheduling problems with the effects of deterioration and learning, where time-dependent setup time is also considered. In the proposed scheduling models, all jobs are first partitioned into serial batches, and then all batches are processed on a single serial-batching machine. The actual job processing time is a function of its starting time and position. In addition, a setup time is required when a new batch is processed, and the setup time of the batches is time-dependent, i.e., it is a linear function of its starting time. Structural properties are derived for the problems of minimizing the makespan, the number of tardy jobs, and the maximum earliness. Then, three optimization algorithms are developed to solve them, respectively.