Batching and delivery in semi-online distribution systems

Suppose a distribution center receives orders from customers for delivery of some goods. Orders may be delayed to be grouped and delivered in batches. The cost of one delivery does not depend on the number of orders taken. The total cost (to be minimized) is the sum of the total delay time of the orders and the total delivery cost. In the on-line environment, where at any time there is no information about future orders, there is a simple on-line algorithm with competitive ratio 2 which is known to be the best possible. We consider the semi-online environment where at any instant we know the orders that will be released in the next SS time units, but have no information about the orders that will be released later. For this environment, we present a semi-online algorithm and analyze its competitive ratio.