04.08.2020 | Ausgabe 4/2020
Note on the time complexity of resource constrained scheduling with general truncated job-dependent learning effect
- Zeitschrift:
- Journal of Combinatorial Optimization > Ausgabe 4/2020
Wichtige Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Abstract
In a recent paper (He et al. in J Comb Optim 33(2):626–644, 2017), the authors considered single machine resource allocation scheduling with general truncated job-dependent learning effect. For the convex resource consumption function and limited resource cost, the problem is to minimize the weighted sum of makespan, total completion time, the total absolute deviation in completion time and resource consumption cost. They conjectured that this problem is NP-hard. In this note we show that this problem can be solved in \(O(n^3)\) time. It is also shown that Lemma 4 in He et al. (2017) is incorrect by a counter-example.
