Title: Some polynomial solvable single-machine scheduling problems with a truncation sum-of-processing-times-based learning effect

Authors: Chin-Chia Wu; Yunqiang Yin; Wen-Hsiang Wu; Shuenn-Ren Cheng

Addresses: Department of Statistics, Feng Chia University, Taichung, Taiwan. ' College of Mathematics and Information Sciences, East China Institute of Technology, Fuzhou, Jiangxi 344000, China. ' Department of Healthcare Management, Yuanpei University, Hsinchu, Taiwan. ' Graduate Institute of Business Administration, Cheng Shiu University, Kaohsiung County, Taiwan

Abstract: Recently, scheduling with learning effects has received growing attention. A well-known learning model is called 'sum-of processing-times-based learning' where the actual processing time of a job is a non-increasing function of the jobs already processed. However, the actual processing time of a given job drops to zero precipitously when the normal job processing times are large. Motivated by this observation, this paper develops a truncated learning model in which the actual job processing time not only depends on the processing times of the jobs already processed but also depends on a control parameter. The use of the truncated function is to model the phenomenon that the learning of a human activity is limited. In this paper, some single-machine scheduling problems can be solved in polynomial time. Besides, the error bounds are also provided for the problems to minimise the maximum lateness and the total weighted completion time. [Received 20 September 2010; Revised 11 November 2010, 22 January 2011; Accepted 5 February 2011]

Keywords: single-machine scheduling; truncated learning function; job processing time; modelling.

DOI: 10.1504/EJIE.2012.047665

European Journal of Industrial Engineering, 2012 Vol.6 No.4, pp.441 - 453

Published online: 10 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article