Quick minimization of tardy processing time on a single machine

DOI10.1007/978-3-031-38906-1_42arXiv2301.05460OpenAlexW4385356976MaRDI QIDQ6139045FDOQ6139045

Authors: Baruch Schieber, Pranav Sitaraman 

Publication date: 16 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We consider the problem of minimizing the total processing time of tardy jobs on a single machine. This is a classical scheduling problem, first considered by [Lawler and Moore 1969], that also generalizes the Subset Sum problem. Recently, it was shown that this problem can be solved efficiently by computing $(max,min)$-skewed-convolutions. The running time of the resulting algorithm is equivalent, up to logarithmic factors, to the time it takes to compute a $(max,min)$-skewed-convolution of two vectors of integers whose sum is $O(P)$, where $P$ is the sum of the jobs' processing times. We further improve the running time of the minimum tardy processing time computation by introducing a job ``bundling technique and achieve a $ildeOleft(P^{2-1/alpha}ight)$ running time, where $ildeOleft(P^{a}lphaight)$ is the running time of a $(max,min)$-skewed-convolution of vectors of size $P$. This results in a $ildeOleft(P^{7/5}ight)$ time algorithm for tardy processing time minimization, an improvement over the previously known $ildeOleft(P^{5/3}ight)$ time algorithm.

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

zbMATH Keywords

convolutionschedulingtardy processing time

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Cites Work

• Title not available (Why is that?)
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Faster minimization of tardy processing time on a single machine

This page was built for publication: Quick minimization of tardy processing time on a single machine

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