Joint replenishment meets scheduling. (English) Zbl 1517.90047
Summary: In this paper, we consider a combination of the joint replenishment problem (JRP) and single-machine scheduling with release dates. There is a single machine and one or more item types. Each job has a release date, a positive processing time, and it requires a subset of items. A job can be started at time \(t\) only if all the required item types were replenished between the release date of the job and time point \(t\). The ordering of item types for distinct jobs can be combined. The objective is to minimize the total ordering cost plus a scheduling criterion, such as total weighted completion time or maximum flow time, where the cost of ordering a subset of items simultaneously is the sum of a joint ordering cost, and an additional item ordering cost for each item type in the subset. We provide several complexity results for the offline problem, and competitive analysis for online variants with min-sum and min-max criteria, respectively.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
joint replenishment; single-machine scheduling; complexity; polynomial time algorithms; online algorithmsReferences:
| [1] | Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., & Sviridenko, M. (1999). Approximation schemes for minimizing average weighted completion time with release dates. In 40th annual symposium on foundations of computer science (Cat. No. 99CB37039) (pp. 32-43). IEEE |
| [2] | Anderson, EJ; Potts, CN, Online scheduling of a single machine to minimize total weighted completion time, Mathematics of Operations Research, 29, 3, 686-697 (2004) · Zbl 1082.90033 · doi:10.1287/moor.1040.0092 |
| [3] | Arkin, E.; Joneja, D.; Roundy, R., Computational complexity of uncapacitated multi-echelon production planning problems, Operations Research Letters, 8, 2, 61-66 (1989) · Zbl 0674.90044 · doi:10.1016/0167-6377(89)90001-1 |
| [4] | Averbakh, I.; Baysan, M., Approximation algorithm for the on-line multi-customer two-level supply chain scheduling problem, Operations Research Letters, 41, 6, 710-714 (2013) · Zbl 1287.90017 · doi:10.1016/j.orl.2013.10.002 |
| [5] | Averbakh, I.; Xue, Z., On-line supply chain scheduling problems with preemption, European Journal of Operational Research, 181, 1, 500-504 (2007) · Zbl 1121.90051 · doi:10.1016/j.ejor.2006.06.004 |
| [6] | Azar, Y., Epstein, A., Jeż, L., & Vardi, A. (2016). Make-to-order integrated scheduling and distribution. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms (pp. 140-154). SIAM. · Zbl 1415.90038 |
| [7] | Bansal, N.; Dhamdhere, K., Minimizing weighted flow time, ACM Transactions on Algorithms (TALG), 3, 4, 39-es (2007) · Zbl 1445.90029 · doi:10.1145/1290672.1290676 |
| [8] | Baptiste, P., Scheduling equal-length jobs on identical parallel machines, Discrete Applied Mathematics, 103, 1-3, 21-32 (2000) · Zbl 0971.90027 · doi:10.1016/S0166-218X(99)00238-3 |
| [9] | Becchetti, L.; Marchetti-Spaccamela, A.; Vitaletti, A.; Korteweg, P.; Skutella, M.; Stougie, L., Latency-constrained aggregation in sensor networks, ACM Transactions on Algorithms (TALG), 6, 1, 1-20 (2009) · Zbl 1300.68063 · doi:10.1145/1644015.1644028 |
| [10] | Bienkowski, M.; Byrka, J.; Chrobak, M.; Dobbs, N.; Nowicki, T.; Sviridenko, M.; Świrszcz, G.; Young, NE, Approximation algorithms for the joint replenishment problem with deadlines, Journal of Scheduling, 18, 6, 545-560 (2015) · Zbl 1333.90015 · doi:10.1007/s10951-014-0392-y |
| [11] | Bienkowski, M., Byrka, J., Chrobak, M., Jeż, Ł., Nogneng, D., & Sgall, J. (2014). Better approximation bounds for the joint replenishment problem. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms (pp. 42-54). SIAM. · Zbl 1423.68589 |
| [12] | Bosman, T., & Olver, N. (2020). Improved approximation algorithms for inventory problems. In International conference on integer programming and combinatorial optimization (pp. 91-103). Springer. · Zbl 1503.90003 |
| [13] | Buchbinder, N.; Kimbrel, T.; Levi, R.; Makarychev, K.; Sviridenko, M., Online make-to-order joint replenishment model: Primal-dual competitive algorithms, Operations Research, 61, 4, 1014-1029 (2013) · Zbl 1291.90010 · doi:10.1287/opre.2013.1188 |
| [14] | Chekuri, C., Khanna, S., & Zhu, A. (2001). Algorithms for minimizing weighted flow time. In Proceedings of the thirty-third annual ACM symposium on theory of computing (pp. 84-93). · Zbl 1323.90019 |
| [15] | Chekuri, C.; Motwani, R.; Natarajan, B.; Stein, C., Approximation techniques for average completion time scheduling, SIAM Journal on Computing, 31, 1, 146-166 (2001) · Zbl 0992.68066 · doi:10.1137/S0097539797327180 |
| [16] | Chen, ZL, Integrated production and outbound distribution scheduling: Review and extensions, Operations Research, 58, 1, 130-148 (2010) · Zbl 1233.90151 · doi:10.1287/opre.1080.0688 |
| [17] | Cheung, M.; Elmachtoub, AN; Levi, R.; Shmoys, DB, The submodular joint replenishment problem, Mathematical Programming, 158, 1-2, 207-233 (2016) · Zbl 1346.90301 · doi:10.1007/s10107-015-0920-3 |
| [18] | Epstein, L., & Van Stee, R. (2001). Lower bounds for on-line single-machine scheduling. In International symposium on mathematical foundations of computer science (pp. 338-350). Springer. · Zbl 0999.68502 |
| [19] | Goemans, MX; Queyranne, M.; Schulz, AS; Skutella, M.; Wang, Y., Single machine scheduling with release dates, SIAM Journal on Discrete Mathematics, 15, 2, 165-192 (2002) · Zbl 1009.90096 · doi:10.1137/S089548019936223X |
| [20] | Graham, RL; Lawler, EL; Lenstra, JK; Rinnooy Kan, A., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [21] | Hoogeveen, J. A., & Vestjens, A. P. (1996). Optimal online algorithms for single-machine scheduling. In International conference on integer programming and combinatorial optimization (pp. 404-414). Springer. · Zbl 1414.90152 |
| [22] | Karlin, AR; Manasse, MS; McGeoch, LA; Owicki, S., Competitive randomized algorithms for nonuniform problems, Algorithmica, 11, 6, 542-571 (1994) · Zbl 0806.68053 · doi:10.1007/BF01189993 |
| [23] | Karlin, AR; Manasse, MS; Rudolph, L.; Sleator, DD, Competitive snoopy caching, Algorithmica, 3, 1, 79-119 (1988) · Zbl 0645.68034 · doi:10.1007/BF01762111 |
| [24] | Karp, R. M. (1992). On-line algorithms versus off-line algorithms: How much is it worth to know the future? In IFIP congress (1) (Vol. 12, pp. 416-429). |
| [25] | Kellerer, H.; Tautenhahn, T.; Woeginger, G., Approximability and nonapproximability results for minimizing total flow time on a single machine, SIAM Journal on Computing, 28, 4, 1155-1166 (1999) · Zbl 0926.68014 · doi:10.1137/S0097539796305778 |
| [26] | Khouja, M.; Goyal, S., A review of the joint replenishment problem literature: 1989-2005, European Journal of Operational Research, 186, 1, 1-16 (2008) · Zbl 1138.90322 · doi:10.1016/j.ejor.2007.03.007 |
| [27] | Lenstra, JK; Kan, AR; Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362 (1977) · Zbl 0353.68067 · doi:10.1016/S0167-5060(08)70743-X |
| [28] | Levi, R.; Roundy, R.; Shmoys, D.; Sviridenko, M., A constant approximation algorithm for the one-warehouse multiretailer problem, Management Science, 54, 4, 763-776 (2008) · Zbl 1232.90071 · doi:10.1287/mnsc.1070.0781 |
| [29] | Levi, R.; Roundy, RO; Shmoys, DB, Primal-dual algorithms for deterministic inventory problems, Mathematics of Operations Research, 31, 2, 267-284 (2006) · Zbl 1278.90026 · doi:10.1287/moor.1050.0178 |
| [30] | Levi, R.; Sviridenko, M.; Díaz, J.; Jansen, K.; Rolim, JDP; Zwick, U., Improved approximation algorithm for the one-warehouse multi-retailer problem, Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 188-199 (2006), Springer · Zbl 1155.90311 · doi:10.1007/11830924_19 |
| [31] | Nonner, T., & Souza, A. (2009). A 5/3-approximation algorithm for joint replenishment with deadlines. In International conference on combinatorial optimization and applications (pp. 24-35). Springer. · Zbl 1246.90011 |
| [32] | Potts, CN, Analysis of a heuristic for one machine sequencing with release dates and delivery times, Operations Research, 28, 6, 1436-1441 (1980) · Zbl 0447.90041 · doi:10.1287/opre.28.6.1436 |
| [33] | Starr, MK; Miller, DW, Inventory control: Theory and practice (1962), Prentice-Hall |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
