Optimizing a dynamic order-picking process

This research studies the problem of batching orders in a dynamic, finite-horizon environment to minimize order tardiness and overtime costs of the pickers. The problem introduces the following trade-off: at every period, the picker has to decide whether to go on a tour and pick the accumulated orders, or to wait for more orders to arrive. By waiting, the picker risks higher tardiness of existing orders on the account of lower tardiness of future orders. We use a Markov decision process (MDP) based approach to set an optimal decision making policy. In order to evaluate the potential improvement of the proposed approach in practice, we compare the optimal policy with two naïve heuristics: (1) “Go on tour immediately after an order arrives”, and, (2) “Wait as long as the current orders can be picked and supplied on time”. The optimal policy shows a considerable improvement over the naïve heuristics, in the range of 7–99%, where the specific values depend on the picking process parameters. We have found that one measure, the slack percentage of the picking process, associated with the difference between the promised lead time and the single item picking time, predicts quite accurately the cost reduction generated by the optimal policy. Since relatively small-scale problems could be solved by the optimal algorithm, a heuristic was developed, based on the structure and properties of the optimal solutions. Numerical results show that the proposed heuristic, MDP-H, outperforms the naïve heuristics in all experiments. As compared to the optimal solution, MDP-H provides close to optimal results for a slack of up to 40%.     

An exactly conservative particle method for one dimensional scalar conservation laws

A particle scheme for scalar conservation laws in one space dimension is presented. Particles representing the solution are moved according to their characteristic velocities. Particle interaction is resolved locally, satisfying exact conservation of area. Shocks stay sharp and propagate at correct speeds, while rarefaction waves are created where appropriate. The method is variation diminishing, entropy decreasing, exactly conservative, and has no numerical dissipation away from shocks. Solutions, including the location of shocks, are approximated with second order accuracy. Source terms can be included. The method is compared to CLAWPACK in various examples, and found to yield a comparable or better accuracy for similar resolutions.     

On-line steiner trees in the Euclidean plane

Suppose we are given a sequence ofn points in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of lengths of its edges. The points appear one at a time, and at each step the on-line algorithm must construct a connected graph that contains all current points by connecting the new point to the previously constructed graph. This can be done by joining the new point (not necessarily by a straight line) to any point of the previous graph (not necessarily one of the given points). The performance of our algorithm is measured by its competitive ratio: the supremum, over all sequences of points, of the ratio between the total length of the graph constructed by our algorithm and the total length of the best Steiner tree that connects all the points. There are known on-line algorithms whose competitive ratio isO(logn) even for all metric spaces, but the only lower bound known is of [IW] for some contrived discrete metric space. Moreover, for the plane, on-line algorithms could have been more powerful and achieve a better competitive ratio, and no nontrivial lower bounds for the best possible competitive ratio were known. Here we prove an almost tight lower bound of Ω(logn/log logn) for the competitive ratio of any on-line algorithm. The lower bound holds for deterministic algorithms as well as for randomized ones, and obviously holds in any Euclidean space of dimension greater than 2 as well. Noga Alon was supported in part by a USA-Israeli BSF grant.     

Approximating Probability Distributions Using Small Sample Spaces

We formulate the notion of a "good approximation" to a probability distribution over a finite abelian group ?. The quality of the approximating distribution is characterized by a parameter ɛ which is a bound on the difference between corresponding Fourier coefficients of the two distributions. It is also required that the sample space of the approximating distribution be of size polynomial in and 1/ɛ. Such approximations are useful in reducing or eliminating the use of randomness in certain randomized algorithms. We demonstrate the existence of such good approximations to arbitrary distributions. In the case of n random variables distributed uniformly and independently over the range , we provide an efficient construction of a good approximation. The approximation constructed has the property that any linear combination of the random variables (modulo d) has essentially the same behavior under the approximating distribution as it does under the uniform distribution over . Our analysis is based on Weil's character sum estimates. We apply this result to the construction of a non-binary linear code where the alphabet symbols appear almost uniformly in each non-zero code-word. Received: September 22, 1990/Revised: First revision November 11, 1990; last revision November 10, 1997     

A practical algorithm for completing half-Hadamard matrices using LLL

Journal of Algebraic Combinatorics - A (classical) partial Hadamard Matrix is an $$m\times n$$ matrix H with values in $$\{-1,1\}$$ such that $$HH^T=nI_m$$ . If $$m=n$$ , we say that H is a (full)...     

The relationship between DEA efficiency and the type of production function, the degree of homogeneity, and error variability

In this paper, we use simulations to investigate the relationship between data envelopment analysis (DEA) efficiency and major production functions: Cobb-Douglas, the constant elasticity of substitution, and the transcendental logarithmic. Two DEA models were used: a constant return to scale (CCR model), and a variable return to scale (BCC model). Each of the models was investigated in two versions: with bounded and unbounded weights. Two cases were simulated: with and without errors in the production functions estimation. Various degrees of homogeneity (of the production function) were tested, reflecting a constant increasing and decreasing return to scale. With respect to the case with errors, three distribution functions were utilized: uniform, normal, and double exponential. For each distribution, 16 levels of the coefficient of variance (CV) were used. In all the tested cases, two measures were analysed: the percentage of efficient units (from the total number of units), and the average efficiency score. We applied a regression analysis to test the relationship between these two efficiency measures and the above parameters. Overall, we found that the degree of homogeneity has the largest effect on efficiency. Efficiency declines as the errors grow (as reflected by larger CV and of the expansion of the probability distribution function away from the centre). The bounds on the weights tend to smooth the effect, and bring the various DEA versions closer to one other. The type of efficiency measure has similar regression tendencies. Finally, the relationship between the efficiency measures and the explanatory variables is quadratic.     

On Two Dimensional Packing

The paper considerspacking of rectanglesinto an infinite bin. Similar to theTetris game, the rectangles arrive from the top and, once placed, cannot be moved again. The rectangles are moved inside the bin to reach their place. For the case in which rotations are allowed, we design an algorithm whose performance ratio is constant. In contrast, if rotations are not allowed, we show that no algorithm of constant ratio exists. For this case we design an algorithm with performance ratio ofO(log(1/)), where is the minimum width of any rectangle. We also show that no algorithm can achieve a better ratio than for this case.