The Library
Approximation algorithms for the joint replenishment problem with deadlines
Tools
Bienkowski, Marcin, Byrka, Jarosław, Chrobak, Marek, Dobbs, Neil, Nowicki, Tomasz, Sviridenko, Maxim, Świrszcz, G. and Young, Neal E. (2015) Approximation algorithms for the joint replenishment problem with deadlines. Journal of Scheduling, 18 (6). pp. 545-560. doi:10.1007/s10951-014-0392-y ISSN 1094-6136.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s10951-014-0392-y
Abstract
The Joint Replenishment Problem ( JRP) is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the retailers, the supplier ships orders, via a warehouse, to the retailers. The objective is to schedule these orders to minimize the sum of ordering costs and retailers’ waiting costs. We study the approximability of JRP-D, the version of JRP with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of 1.207, a stronger, computer-assisted lower bound of 1.245, as well as an upper bound and approximation ratio of 1.574. The best previous upper bound and approximation ratio was 1.667; no lower bound was previously published. For the special case when all demand periods are of equal length, we give an upper bound of 1.5, a lower bound of 1.2, and show APX-hardness.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Journal or Publication Title: | Journal of Scheduling | ||||||
Publisher: | Springer New York LLC | ||||||
ISSN: | 1094-6136 | ||||||
Official Date: | December 2015 | ||||||
Dates: |
|
||||||
Volume: | 18 | ||||||
Number: | 6 | ||||||
Page Range: | pp. 545-560 | ||||||
DOI: | 10.1007/s10951-014-0392-y | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Embodied As: | 1 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |