|
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:
| 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} |