An online joint replenishment problem combined with single machine scheduling

DOI10.1007/S10878-023-01064-ZMaRDI 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

Recommendations

• Joint replenishment meets scheduling
• Better Approximation Bounds for the Joint Replenishment Problem
• Online inventory replenishment scheduling of temporary orders
• An optimal online algorithm for single machine scheduling with bounded delivery times
• Online scheduling on a single machine with grouped processing times

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

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

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)