480. Joint replenishment meets scheduling
Invited abstract in session HE-20: Design and Evaluation of Approximations, cluster Combinatorial Optimization.
Thursday, 16:15-17:45Room: FENH106
Authors (first author is the speaker)
| 1. | Péter Györgyi
|
| Institute for Computer Science and Control | |
| 2. | Tamas Kis
|
| Institute for Computer Science and Control | |
| 3. | Timea Tamasi
|
| Institute for Computer Science and Control | |
| 4. | József Békési
|
| Department of Applied Informatics, University of Szeged |
Abstract
A combination of two classic problems of operations research is considered - the joint replenishment problem and single machine scheduling with release dates. In this problem, there is a single machine and one or more items. We also have a set of jobs, and each job has a release date, a positive processing time, and a required subset of items. A job can be processed on the machine at time point t if all the required items were replenished between the release date of the job and time point t. Furthermore, the machine can process at most one job at a time. One has to decide about both the replenishments and the schedule on the machine; the objective is to minimize the sum of the replenishment cost and the scheduling cost. The former depends on the number of replenishments; more precisely, 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 in the subset. The latter is a standard scheduling criteria, like the total weighted completion time or the maximum flow time.
First, we survey the complexity results for the offline problem, where the complete input is known in advance. Then, we present some online and semi-online algorithm. We also derive several lower bounds for the best competitive ratio of any deterministic online algorithm under various assumptions. In the online variant of the problem, the jobs arrive over time, and the input becomes known gradually. The solution is built step-by-step, but we cannot interrupt an already scheduled job before its completion time. In the semi-online variants, we have some limited information about the jobs, e.g. there is an upper bound on the time period between the consecutive release dates of the jobs or exactly one job is released at every time point and only the number of jobs is unknown at the beginning.
This research has been supported by the TKP2021-NKTA-01 NRDIO grant on 'Research on cooperative production and logistics systems to support a competitive and sustainable economy'.
Keywords
- Scheduling
Status: accepted
Back to the list of papers