18938523
A two-dimensional vector packing model for the efficient use of coil cassettes
We consider the problem of efficiently packing steel products, known as coils, into special containers, called cassettes for shipping. The objective is to minimize the number of cassettes used for packing all the given coils where each cassette has capacity limits on both total payload weight and size. We model this problem as a two-dimensional vector packing problem and propose a heuristic. We also analyze the worst-case performance of the proposed algorithm under a special condition which, in fact, holds for the particular real-world case that we handled. Our computational experiment with real production data shows that the proposed algorithm performs quite satisfactorily in practice.
18088728
Order Consolidation for Batch Processing
We consider the batch processing of orders where either whole or part of a single order or a specific pair of different orders may be grouped in a batch with a fixed capacity. The problem can be modelled by a graph G = (V,E), where each node v$${\in}$$V corresponds to an order, its weight w(v) corresponds to the amount of ordered quantity and a pair of orders, say u and v may be grouped in a batch if there exists the edge (u,v) $${\in}$$E. The objective is to maximize the number of batches filled up to its capacity $$\lambda$$. In this paper, we prove that the problem is NP-hard and, moreover, that no PTAS exists unless P = NP. Then, an optimal algorithm is developed with running time O(|V|log |V|) for the special case when G is a tree.
7967901
The effect of machine availability on the worst-case performance of LPT
We consider the makespan minimization parallel machine scheduling problem where each machine may be unavailable for a known time interval. For this problem, we investigate how the worst-case behavior of the longest processing time first algorithm (LPT) is affected by the availability of machines. In particular, for given m machines, we analyze the cases where arbitrary number, λ, ranging from one to m - 1, machines are unavailable simultaneously. Then, we show that the makespan of the schedule generated by LPT is never more than the tight worst-case bound of 1 + ½ ⌊m/(m - λ)⌋ times the optimum makespan.
16926226
Optimal histogram matching by monotone gray level transformation
This paper investigates the problem of optimal histogram matching using monotone gray level transformation, which always assigns all picture points of a given gray level <italic>i</italic> to another gray level <italic>T</italic>(<italic>i</italic>) such that if <italic>i</italic> ≥ <italic>j</italic>, then <italic>T</italic>(<italic>i</italic>) ≥ <italic>T</italic>(<italic>j</italic>). The objective is to find a transformed digital picture of a given picture such that the sum of absolute errors between the gray level histogram of the transformed picture and that of a reference picture is minimized. This is equivalent to placing <italic>k</italic>1 linearly ordered objects of different sizes one by one into <italic>k</italic>2 linearly ordered boxes of assorted sizes, such that the accumulated error of space underpacked or overpacked in the boxes is minimized; the placement function is monotonic, which ensures a polynomial time solution to this problem. A tree search algorithm for optimal histogram matching is presented which has time complexity <italic>O</italic>(<italic>k</italic>1 × <italic>k</italic>2). If the monotone property is dropped, then the problem becomes <italic>NP</italic>-complete, even if it is restricted to <italic>k</italic>2 = 2.
206416394
An Intelligent Image Database System
A prototype intelligent image database system (IIDS) that is based on a novel pictorial data structure is presented. This prototype system supports spatial reasoning, flexible image information retrieval, visualization, and traditional image database operations. A pictorial data structure, based on 2-D strings, provides an efficient means for iconic indexing in image database systems and spatial reasoning. The modular design of IIDS facilitates its implementation. Further extensions of the prototype system are discussed. >
15686205
Transform coding of arbitrarily-shaped image segments
Envisioned advanced multimedia video services include both rectangular and arbitrarily-shaped image segments. Image segments of the TV weather reporter produced by the chromo-key technique and image segments produced by video segmentation or image editing are typical examples. In this paper, we investigate efficient transform coding techniques of arbitrarily-shaped image segments. We formulate the optimal representation problem in two different domains — the full rectangular domain and the shape-projected domain. In the former, we still use the traditional rectangular transform coding method (e.g. DCT) but try to find optimal pixel values outside the segment boundary in order to make the transform spectrum as compact as possible. A simple but efficient mirror-image extension technique is proposed. In the shape-projected domain, we project the image segment and all basis functions into the subspace spanned over the image region only. Existing coding algorithms, such as orthogonal transform by Gilge [1] and iterative coding by Kaup and Aach [2], can be intuitively interpreted. To demonstrate the flexibility of the proposed formulation, we also derive a new KLT-like algorithm in the shape-projected domain. We analyze tradeoff between compression performance, computational complexity, and codec complexity for different coding schemes. Simulation results show that complicated algorithms (e.g. iterative, adaptive) can improve the quality by about 5-10 dB at some computational or hardware cost. On the other hand, the proposed simple mirror-image extension technique improves the quality by about 3-4 dB without any overheads. The contributions of this paper lie in efficient problem formulation, new transform coding techniques, and numerical tradeoff analyses. Currently, we are implementing a software program for AS image object editing and manipulation .
5538880
A generalized parser for 2-D languages
The authors present an extension of the Earley's (1970) generalized parser to the case of two-dimensional languages. They describe two-dimensional (positional) grammars as generalizations of context-free string grammars. The technique used to extend the Earley's algorithm is the same used for constructing a positional LR (pLR) parser. The main idea is to allow the parser to choose the next symbol to parse from a two-dimensional space.<<ETX>>
16993485
The reconstruction of binary patterns from their projections
Given the horizontal and vertical projections of a finite binary pattern <italic>f</italic>, can we reconstruct the original pattern <italic>f</italic>? In this paper we give a characterization of patterns that are reconstructable from their projections. Three algorithms are developed to reconstruct both unambiguous and ambiguous patterns. It is shown that an unambiguous pattern can be perfectly reconstructed in time <italic>m</italic> × <italic>n</italic> and that a pattern similar to an ambiguous pattern can also be constructed in time <italic>m</italic> × <italic>n</italic>, where <italic>m</italic>, <italic>n</italic> are the dimensions of the pattern frame.