Some single-machine scheduling problems with general effects of learning and deterioration

Learning and job deterioration co-exist in many realistic scheduling situations. This paper introduces a general scheduling model with the effects of learning and deterioration simultaneously which is a significant generalization of some existing models in the literature. By the effects of learning and deterioration, we mean that job processing times are defined by functions of their start times and positions in the sequence. This paper shows that the single-machine scheduling problems to minimize the makespan, sum of the kth power of completion times, total lateness and sum of earliness penalties (with a common due date) are polynomially solvable under the proposed model. It further shows that the problems to minimize the total weighted completion time, discounted total weighted completion time, maximum lateness, maximum tardiness, total tardiness and total weighted earliness penalties (with a common due date) are polynomially solvable under certain conditions. (C) 2010 Elsevier Ltd. All rights reserved.