id: 06094594
dt: j
an: 06094594
au: Rudek, Radosław
ti: The single processor total weighted completion time scheduling problem with
    the sum-of-processing-time based learning model.
so: Inf. Sci. 199, 216-229 (2012).
py: 2012
pu: Elsevier Science Inc. (North-Holland), New York, NY
la: EN
cc: 
ut: scheduling; learning; computational complexity; dynamic programming;
    metaheuristic
ci: 
li: doi:10.1016/j.ins.2012.02.043
ab: Summary: In this paper, we analyse the single processor total weighted
    completion time scheduling problem with the learning effect, where the
    processing time of each job is a non-increasing function dependent on
    the sum of the normal processing times of preceding jobs. We prove that
    the considered problem is at least NP-hard. Moreover, a
    pseudopolynomial time dynamic programming algorithm that optimally
    solves the problem with a step learning function (curve) is
    constructed. Furthermore, fast approximation algorithms for the general
    version of the problem, where job processing times are described by
    arbitrary functions dependent on the sum of the normal job processing
    times, are provided. Their efficiency is verified numerically and for
    Weighted Shortest Processing Times algorithm a worst case analysis is
    also performed.
rv: