Scheduling problems with learning and ageing effects: a survey <s> TIME AND POSITION DEPENDENT MODELS <s> In this paper, we consider the single-machine scheduling problems with the effects of learning and deterioration. By the effects of learning and deterioration, we mean that job processing times are defined by functions of their starting times and positions in the sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, single-machine makespan and sum of completion times (square) minimization problems remain polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion times and the maximum lateness, this paper proves that the WSPT rule and the EDD rule can construct the optimal sequence under some special cases, respectively. <s> BIB001 </s> Scheduling problems with learning and ageing effects: a survey <s> TIME AND POSITION DEPENDENT MODELS <s> The paper deals with some single-machine scheduling problems with setup time considerations where the processing time of a job is given as a function of its starting times and position in a sequence. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We consider the following objective functions: the makespan, the total completion time, the sum of the δth (\( \delta \geqslant 0 \)) power of job completion times, the total weighted completion time, the maximum lateness and the number of tardy jobs. We show that the makespan minimization problem, the total completion time minimization problem, and the sum of the δth power of job completion times minimization problem can be solved in polynomial time, respectively. We also show that the total weighted completion time minimization problem, the maximum lateness minimization problem and the number of tardy jobs minimization problem can be solved in polynomial time under certain conditions. <s> BIB002 </s> Scheduling problems with learning and ageing effects: a survey <s> TIME AND POSITION DEPENDENT MODELS <s> This paper considers a single-machine scheduling problem with both deterioration and learning effects. The objectives are to respectively minimize the makespan, the total completion times, the sum of weighted completion times, the sum of the kth power of the job completion times, the maximum lateness, the total absolute differences in completion times and the sum of earliness, tardiness and common due-date penalties. Several polynomial time algorithms are proposed to optimally solve the problem with the above objectives. <s> BIB003 </s> Scheduling problems with learning and ageing effects: a survey <s> TIME AND POSITION DEPENDENT MODELS <s> In this paper we consider the single-machine scheduling problems with the effects of learning and deterioration. By the effects of learning and deterioration, we mean that job processing times are defined by functions of their starting times and positions in the sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, single machine makespan and sum of completion times (square) minimization problems remain polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion times and the maximum lateness, this paper proves that the WSPT rule and the EDD rule can construct the optimal sequence under some special cases, respectively. <s> BIB004 </s> Scheduling problems with learning and ageing effects: a survey <s> TIME AND POSITION DEPENDENT MODELS <s> In this paper we consider a two-machine flow shop scheduling problem with effects of deterioration and learning. By the effects of deterioration and learning, we mean that the processing time of a job is a function of its execution starting time and its position in a sequence. The objective is to find a sequence that minimizes the total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed, which is shown by computational experiments to perform effectively and efficiently in obtaining near-optimal solutions. <s> BIB005 </s> Scheduling problems with learning and ageing effects: a survey <s> TIME AND POSITION DEPENDENT MODELS <s> Abstract This paper studies the single machine scheduling problems with learning effect and deteriorating jobs simultaneously. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, the makespan, the total completion time and the sum of the k th power of completion times minimization problems remain polynomially solvable, respectively. But for the following objective functions: the total weighted completion time and the maximum lateness, this paper proves that the shortest weighted processing time first (WSPT) rule and the earliest due-date first (EDD) rule can construct the optimal sequence under some special cases, respectively. <s> BIB006 </s> Scheduling problems with learning and ageing effects: a survey <s> TIME AND POSITION DEPENDENT MODELS <s> In this paper we consider a single-machine scheduling problem with the effects of learning and deterioration. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of earliness, tardiness and due-date. We show that the problem remains polynomially solvable under the proposed model. <s> BIB007 </s> Scheduling problems with learning and ageing effects: a survey <s> TIME AND POSITION DEPENDENT MODELS <s> This paper considers some scheduling problems with deteriorating jobs and learning effects. The following objective functions are considered: the makespan, the total completion times, and the total absolute differences in completion times. Several polynomial time algorithms are proposed to optimally solve the single-machine scheduling problems. Finally, we show that several special cases of the flowshop scheduling problems remain polynomially solvable under the proposed model. <s> BIB008
As it was mentioned above, the first paper considering a scheduling problem with simultaneous learning and ageing effects is  . He considers a model of job processing times dependent on starting times and positions (learning effect + deteriorating jobs) of the following form: where t is the job starting time, r is position of the job in a sequence, a 0 is a learning index and α j is a deterioration rate. The author shows that the single processor problems with criteria C max , C j and L j is polynomially solvable by SDR (the smallest deteriorating rate) principle. He proves also that the corresponding problems with a slightly different model: a (where p 0 is common basic processing time) are no longer optimally solvable by SDR principle. No practical application is presented for the considered problem by  . However, research on this kind of scheduling problems is continued by BIB001 , where a short vague example of simultaneous existing of learning and deteriorarting effects is provided. In this description it is explained that workers learn by repeating some tasks, but they forget the acquired abilities while they are moved to another kind of tasks. Unfortunately, this description does not reflect the considered problem (in particular scheduling process and the considered model of processing times). In fact, Wang considers a slightly more general model of job processing times than Lee, namely: where p j is the normal processing time, α(t) is an increasing function, β is a constant and a 0 is the learning index. The author proves that the single processor problems with C max , C j , C 2 j criteria and some special cases with w j C j and L max criteria are polynomially solvable. Similar model is investigated by Kuo (2009),Wang and BIB007 , : where a 0 and α 0 are learning and ageing indices, respectively. In the paper of BIB003 , single processor problems are considered. It is shown that minimization of C max , C j , C k j and some special cases of minimization of w j C j , L max , T ADC 1 , ET CP 2 are polynomially solvable. In the paper of BIB007 it is proven that the single processor due-date assignment problem with effects of learning and ageing is still polynomially solvable (O(n log n)). The same -short and vague -description of practical application as in Wang (2007) is given in the both above mentioned papers. What is more, BIB007 give another example (independent of the previous one) describing due-date assignment (but without the learning and ageing effects!). Instead, simply assembly line balancing problem (SALBP) is investigated by . Authors show that SALBP with this model of job processing time can be solved optimally in polynomial time, using mixed nonlinear integer programming. Moreover, for bigger instances of the problem a heuristic algorithm is constructed. The authors give a short practical example (and references to several other papers) of SALBP problem only with the learning effect (without ageing or job deterioration effect). BIB008 formulate the following model of processing time: where b j 0 denotes a learning index of job j and α > 0 is an ageing index. In this paper the special case with learning index common for all jobs (b j = b) is investigated as well. Some single processor scheduling problems and flow shop problems are taken into consideration. It is proven that single processor problems and some flow shop problems with criteria C max , C j and T ADC are polynomially solvable. However, authors do not show practical applications for their research. The models, in which learning effect and ageing effect multiply together, are also considered in the scientific literature. Namely, BIB002 formulate job processing time as: (αE i + βT i + γd) -sum of earliness, tardiness and common due-date penalty (α, β, γ -some coefficients) where α j is an ageing index of job j, a 0 is a learning index and b, c, d are some constant parameters. They also consider setup times: where p * [i] denotes actual processing time of job scheduled in position i. They prove that single processor problems with such model of processing time and setups and criteria C max , C j and C δ j are polynomially solvable. Moreover, some special cases with criteria L max , U j , w j C j are proven to be solvable in polynomial time. Unfortunately, an example of a real life system with learning effect, ageing effect and setups is not given. In this group of scheduling problems, there are such that include arbitrary function of starting time BIB004 ): and where α(t) in the above equations is an increasing ageing function (α(0) 0) and M ∈ [0, 1] is a constant. It is shown that single processor problems with job processing time expressed by one of the above equations and criteria C max , C j and C 2 j are polynomially solvable. Some special cases of minimization of w j C j and L max are also shown to be polynomially solvable. However, explanation for such model of processing time is not sufficient (especially from practical point of view, since exactly the same example as in Wang (2007) is given). Finally, the problems, in which ageing index depended on jobs and on processors, are analyzed BIB005 ), i.e. the processing time is expressed as: where α ij > 0 is an ageing index of job j processed on processor i and a 0 is a learning index. Starting time of job must be a positive number (t > 0). In this paper some single processor polynomial solvable problems are provided. For two machine flow shop problem, domination rules and a lower bound are shown and they are later used in a branch and bound algorithm. What is more, some heuristic algorithms are constructed. Unfortunately, a real life system that can be modelled as a flow shop problem with effects of learning and ageing is not shown. Different model -in which not power but exponential function of position is given -is introduced by BIB006 : In the above equation a ∈ (0, 1] is a learning index, α 0 and β 0 are learning parameters and b 0, c 0 are ageing parameters. It is proven that problems with criteria C max , C j , C δ j and some special cases with criteria w j C j and L max are solvable in polynomial time. As a practical motivation of the considered model, the authors give the same short and vague example as in BIB001 BIB004 ), Kuo (2009), Wang and BIB007 . Moreover, they provide another short example (preheating of the ingot in steel production), but only to justify consideration of coefficient of starting time proportional to the normal processing time. Thus, the authors again do not provide exhaustive (i.e., including dependency of the job processing times on their starting times and positions in a sequence) and convincing practical example of the analyzed scheduling model.