TR-2019-05

New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints

Péter Györgyi, Tamás Kis



Abstract

In this paper we consider a single machine scheduling problem with additional non-renewable resource constraints and the total weighted completion time objective. There are only a few complexity and approximability results for this problem. We consider special cases and describe new complexity results and also an FPTAS for a variant which is extended to instances with high-multiplicity jobs. We also prove some non-trivial approximation results for a simple greedy algorithm.


Bibtex entry:

@techreport{egres-19-05,
AUTHOR = {Györgyi, P{\'e}ter and Kis, Tam{\'a}s},
TITLE = {New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-05}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!