TY - JOUR
T1 - Batching and delivery in semi-online distribution systems
AU - Averbakh, Igor
AU - Baysan, Mehmet
PY - 2013/1
Y1 - 2013/1
N2 - 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 S 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.
AB - 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 S 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.
KW - Competitive analysis
KW - Semi-online algorithm
KW - Supply chain scheduling
UR - http://www.scopus.com/inward/record.url?scp=84869081307&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2012.08.003
DO - 10.1016/j.dam.2012.08.003
M3 - Article
AN - SCOPUS:84869081307
SN - 0166-218X
VL - 161
SP - 28
EP - 42
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 1-2
ER -