An online joint replenishment problem combined with single machine scheduling

DOI10.1007/S10878-023-01064-ZarXiv2208.02748MaRDI QIDQ6166202FDOQ6166202

Authors: Péter Györgyi, Tamás Kis, Tímea Tamási 

Publication date: 2 August 2023

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: This paper considers a combination of the joint replenishment problem with single machine scheduling. There is a single resource, which is required by all the jobs, and a job can be started at time point $t$ on the machine if and only the machine does not process another job at $t$, and the resource is replenished between its release date and $t$. Each replenishment has a cost, which is independent of the amount replenished. The objective is to minimize the total replenishment cost plus the maximum flow time of the jobs. We consider the online variant of the problem, where the jobs are released over time, and once a job is inserted into the schedule, its starting time cannot be changed. We propose a deterministic 2-competitive online algorithm for the general input. Moreover, we show that for a certain class of inputs (so-called $p$-bounded input), the competitive ratio of the algorithm tends to $sqrt2$ as the number of jobs tends to infinity. We also derive several lower bounds for the best competitive ratio of any deterministic online algorithm under various assumptions.

Full work available at URL: https://arxiv.org/abs/2208.02748

zbMATH Keywords

single machine schedulingjoint replenishmentonline algorithmmaximum flow time

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Cites Work

• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A review of the joint replenishment problem literature: 1989--2005
• Computational complexity of uncapacitated multi-echelon production planning problems
• Primal-Dual Algorithms for Deterministic Inventory Problems
• The submodular joint replenishment problem
• A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines
• Better Approximation Bounds for the Joint Replenishment Problem
• Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem
• Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms
• Joint replenishment meets scheduling

This page was built for publication: An online joint replenishment problem combined with single machine scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166202)