Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
Copyright © 2009 Xingong Zhang and Guangle Yan. This is an open access article distributed under the
Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Recently, learning scheduling problems have received increasing
attention. However, the majority of the research assume that the
actual job processing time is a function of its position. This paper
deals with the single-machine scheduling problem with a
sum-of-processing-time-based learning effect. By the effect of
sum-of-processing-time-based learning, we mean that the processing
time of a job is defined by total normal processing time of jobs in
front of it in the sequence. We show that the single-machine
makespan problem remains polynomially solvable under the proposed
model. We show that the total completion time minimization problem
for remains polynomially solvable under the proposed
model. For the case of , we show that an optimal schedule of
the total completion time minimization problem is -shaped with respect to normal job processing times.