Scheduling problems with learning and ageing effects: a survey <s> TOTAL NORMAL PROCESSING TIME AND POSITION DEPENDENT MODELS <s> In this paper, we introduce a new scheduling model in which deteriorating jobs and learning effect are both considered simultaneously. By deterioration and the learning effect, we mean that the actual processing time of a job depends not only on the processing time of the jobs already processed but also on its scheduled position. For the single-machine case, we show that the problems of makespan, total completion time and the sum of the quadratic job completion times remain polynomially solvable, respectively. In addition,we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain conditions. <s> BIB001 </s> Scheduling problems with learning and ageing effects: a survey <s> TOTAL NORMAL PROCESSING TIME AND POSITION DEPENDENT MODELS <s> Recently, interest in scheduling with deteriorating jobs and learning effects has kept growing. However, research in this area has seldom considered setup times. We introduce a new scheduling model in which job deterioration and learning, and setup times are considered simultaneously. In the proposed model, the actual processing time of a job is defined as a function of the setup and processing times of the jobs already processed and the job's own scheduled position in a sequence. In addition, the setup times are assumed to be proportional to the actual processing times of the already scheduled jobs. We derive polynomial-time optimal solutions for some single-machine problems with or without the presence of certain conditions. <s> BIB002 </s> Scheduling problems with learning and ageing effects: a survey <s> TOTAL NORMAL PROCESSING TIME AND POSITION DEPENDENT MODELS <s> In this paper we consider the single machine scheduling problems with time-dependent deterioration and exponential learning effect, i.e., the actual processing time of a job depends not only on the processing times of the jobs already processed but also on its scheduled position. We consider the following objective functions: the makespan, the sum of the @dth (@d>=0) power of job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the sum of the @dth power of job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions. <s> BIB003
Another group of scheduling problems with learning and ageing effects are such that the processing times depend on sum of normal processing times of already finished jobs (not the starting times as in previous models) and on positions. BIB002 introduce the following model of processing time: where p j [r] is actual processing time of job j scheduled in rth position, p j is normal processing time of this job, p [l] denotes normal processing time of job scheduled in lth position, a < 0 and b > 0 are learning and ageing indices, respectively. Logarithm in the above equation prevents dramatic decline of the processing time when number of jobs increases. Authors investigate single processor problems where setup before processing job j scheduled in rth position is described as follows: where γ is a normalizing parameter (0 < γ < 1). It is proven that problems with criteria C max , C j , C 2 j are polynomially solvable. Moreover, some special, polynomially solvable cases of minimization of T i and L max are shown. As a practical application of the above mentioned model of setups, the manufacturing of integrated circuit boards is given. However, this example does not include such complicated model of job processing times as presented above. Sun's paper BIB001 ) concerns a slightly different model of processing time: In the above equation a 1 is an ageing index and b < 0 is a learning index. Contrary to the previous model, wear of the processor is a function of sum of normal processing times and learning is a function of position. It is shown that single processor problems of minimization C max , C j , C 2 j and special cases of minimization w j C j and L max are polynomially solvable. A similar model is introduced by BIB003 . In their model processing time is not a power function but exponential: where a > 1 and α ∈ (0, 1] are ageing and learning indices, respectively. In the paper some exact polynomial time algorithms for single processor problems with criteria C max , C j are developed. Authors also construct polynomial time algorithms for special cases of minimization of L max and w j C j . No detailed examples of practical applications of the models analyzed by Sun and by Huang et al. are provided in the above mentioned papers. There are only short vague sentences (similar in the both papers) that the phenomena of deteriorating jobs (i.e., starting time dependent processing times) and learning effect exist simultaneously in many real-life situations. Then few vague examples are provided (ignoring for instance the scheduling process). In our opinion, such sentences are not sufficient motivation (from practical point of view) to lead research on these -quite complicated -models. Problems with the job processing times dependent on the sum of normal processing times already finished jobs and position of the job are also considered by . They suggest the following model of processing time: where a 1 and a 2 are learning or ageing indices (a 1 < 0, a 2 > 0 -ageing, a 1 > 0, a 2 < 0 -learning) and p 0 is constant. It is proven that special cases of single processor problems with this model of processing time and criteria C max , C j and their weighted sum are polynomially solvable. For other special cases it is shown that optimal schedule is V-shaped with respect to job normal processing times. Unfortunately, authors again do not give an example of real life system that can be modelled in such way.