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.     

Batch scheduling of deteriorating reworkables

The problem of scheduling the production of new and recoverable defective items of the same product manufactured on the same facility is studied. Items are processed in batches. Each batch comprises two sub-batches processed consecutively. In the first sub-batch, all the items are newly manufactured. Some of them are of the required good quality and some are defective. The defective items are remanufactured in the second sub-batch. They deteriorate while waiting for rework. This results in increased time and cost for their remanufacturing. All the items in the same sub-batch complete at the same time, which is the completion time of the last item in the sub-batch. Each remanufactured defective item is of the required good quality. It is assumed that the percentage of defective items in each batch is the same. A setup time is required to start batch processing and to switch from manufacturing to remanufacturing. The demands for good quality items over time are given. The objective is to find batch sizes such that the total setup and inventory holding cost is minimized and all the demands are satisfied. Dynamic programming algorithms are presented for the general problem and some important special cases.     

Taxonomy of batch queueing models in manufacturing systems

Batching plays an important role in performance evaluation of manufacturing systems. Three types of batching are commonly seen: transfer batches, parallel batches and serial batches. To model the batching behavior correctly, a comprehensive classification of batching is proposed. Eight types of batching behavior are classified and corresponding queueing models are given. The newly proposed models are validated by simulation.     

Computing lower and upper bounds for a large-scale industrial job shop scheduling problem

In this paper we present a case study from the lighting industry concerned with the scheduling of a set of job families each representing the production of a particular end-item in a given quantity. It is a job shop type problem, where each job family has a number of routing alternatives, and the solution has to respect batching and machine availability constraints. All jobs of the same job family have a common release date and a common due date, and they differ only in size. The objective is to minimize the total tardiness of the job families, rather than that of individual jobs. We propose a two-phase method based on solving a mixed-integer linear program and then improving the initial solution by tabu search. We evaluate our method on real-world as well as generated instances.     

The EOQ problem with decidable warehouse capacity: Analysis, solution approaches and applications

The Economic Order Quantity (EOQ) problem is a fundamental problem in supply and inventory management. In its classical setting, solutions are not affected by the warehouse capacity. We study a type of EOQ problem where the (maximum) warehouse capacity is a decision variable. Furthermore, we assume that the warehouse cost dominates all the other inventory holding costs. We call this the EOQ-Max problem and the D-EOQ-Max problem, if the product is continuously divisible and discrete, respectively. The EOQ-Max problem admits a closed form optimal solution, while the D-EOQ-Max problem does not because its objective function may have several local minima. We present an optimal polynomial time algorithm for the discrete problem. Construction of this algorithm is supported by the fact that continuous relaxation of the D-EOQ-Max problem provides a solution that can be up to 50% worse than the optimal solution, and this worst-case error bound is tight. Applications of the D-EOQ-Max problem include supply and inventory management, logistics and scheduling.     

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.     

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.     

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.