Anzeige
Erschienen in:
04.08.2020
Note on the time complexity of resource constrained scheduling with general truncated job-dependent learning effect
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2020
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.