International Journal of Combinatorics
Volume 2009 (2009), Article ID 624108, 8 pages
Research Article

Single-Machine Scheduling Problems with a Sum-of-Processing-Time-Based Learning Function

Business School, University of Shanghai for Science and Technology, Shanghai 200093, China

Received 23 September 2009; Revised 9 December 2009; Accepted 15 December 2009

Academic Editor: Liying Kang

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 a1 remains polynomially solvable under the proposed model. For the case of 0<a<1, we show that an optimal schedule of the total completion time minimization problem is V-shaped with respect to normal job processing times.