Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS WITH A LEARNING EFFECT <s> We show that minimizing total flow time on parallel identical processors with nonincreasing unit processing time is achieved with shortest processing time SPT scheduling: Sequence the tasks in an order of nondecreasing lengths. Following this order and starting with the shortest task, process any task by the first processor that becomes available. If the unit processing time is allowed to be increasing, e.g., quadratically, the problem becomes NP-hard. <s> BIB001 </s> Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS WITH A LEARNING EFFECT <s> Abstract We consider a single machine scheduling problem in which the machine experiences the effects of learning of fatigue as it continues to work and the jobs have due dates and are subject to penalties if they are not completed on time. Because of the effects of learning or fatigue, the performance rate of the machine varies over time. As a result, the processing time of a job depends on its work content as well as the total work content of the jobs completed prior to its loading. In this paper, we prove that even when the machine works at a variable rate, the pair-wise interchange of jobs minimizes the maximum tardiness and a simple modification to the well-known Moore-Hodgson's algorithm yields the minimum number of tardy jobs. Further, we formulate the problem of minimizing the total penalty for tardy jobs as a 0–1 knapsack problem with nested constraints, and solve it by using dynamic programming recursion as well as the maximum-weighted network path algorithm. Then we combine these two techniques and solve the 0–1 knapsack problem, by inducing a nested constraint structure and constructing a network with fewer nodes. <s> BIB002 </s> Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS WITH A LEARNING EFFECT <s> The focus of this work is to analyze learning in single-machine scheduling problems. It is surprising that the well-known learning effect has never been considered in connection with scheduling problems. It is shown in this paper that even with the introduction of learning to job processing times two important types of single-machine problems remain polynomially solvable. <s> BIB003 </s> Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS WITH A LEARNING EFFECT <s> Abstract Several recent papers focused on the effect of learning on the optimal solution of scheduling problems. We extend the setting studied so far to the case of job-dependent learning curves, that is, we allow the learning in the production process of some jobs to be faster than that of others. Our learning curve approach, which assumes learning takes place as a function of repetition of the production process, is otherwise completely general, and is not based upon any particular model of learning acquisition. We show that in the new, possibly more realistic setting, the problems of makespan and total flow-time minimization on a single machine, a due-date assignment problem and total flow-time minimization on unrelated parallel machines remain polynomially solvable. <s> BIB004 </s> Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS WITH A LEARNING EFFECT <s> In this study, we introduce a time-dependent learning effect into a single-machine scheduling problem. The time-dependent learning effect of a job is assumed to be a function of total normal processing time of jobs scheduled in front of it. We introduce it into a single-machine scheduling problem and we show that it remains polynomially solvable for the objective, i.e., minimizing the total completion time on a single machine. Moreover, we show that the SPT-sequence is the optimal sequence in this problem. <s> BIB005 </s> Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS WITH A LEARNING EFFECT <s> Abstract We show that the O( n log n ) (where n is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment. <s> BIB006 </s> Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS WITH A LEARNING EFFECT <s> Recently learning effects in scheduling have received considerable attention in the literature. All but one paper are based on the learning-by-doing (or autonomous learning) assumption, even though proactive investments in know how (induced learning) are very important from a practical point of view. In this review we first discuss the questions why and when learning effects in scheduling environments might occur and should be regarded from a planning perspective. Afterwards we give a concise overview on the literature on scheduling with learning effects. <s> BIB007 </s> Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS WITH A LEARNING EFFECT <s> In this paper, we bring into the scheduling field a new model of the learning effect, where in two ways the existing approach is generalized. First we relax one of the rigorous constraints, and thus in our model each job can provide different experience to the processor. Second we formulate the job processing time as a non-increasing k-stepwise function, that, in general, is not restricted to a certain learning curve, thereby it can accurately fit every possible shape of a learning function. Furthermore, we prove that the problem of makespan minimization with the considered model is polynomially solvable if every job provides the same experience to the processor, and it becomes NP-hard if the experiences are diversified. The most essential result is a pseudopolynomial time algorithm that solves optimally the makespan minimization problem with any function of an experience-based learning model reduced into the form of the k-stepwise function. <s> BIB008 </s> Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS WITH A LEARNING EFFECT <s> In this paper, we analyze the two-machine flowshop problem with the makespan minimization and the learning effect, which computational complexity was not determined yet. First, we show that an optimal solution of this problem does not have to be the 'permutation' schedule if the learning effect is taken into consideration. Furthermore, it is proved that the permutation and non-permutation versions of this problem are NP-hard even if the learning effect, in a form of a step learning curve, characterizes only one machine. However, if both machines have learning ability and the learning curves are stepwise then the permutation version of this problem is strongly NP-hard. Furthermore, we prove the makespan minimization problem in m-machine permutation proportional flowshop environment remains polynomially solvable with identical job processing times on each machine even if they are described by arbitrary functions (learning curves) dependent on a job position in a sequence. Finally, approximation algorithms for the general problem are proposed and analyzed. <s> BIB009
A learning effect, i.e. a phenomenon of improving efficiency of a processor, was firstly observed and described by  . Into scheduling theory it was brought by BIB003 as a dependency of job processing times on the number of already processed jobs (i.e., on the position of the job in a sequence). However, the learning effect in the context of scheduling was defined already in the 80s and 90s of 20th century (see e.g., BIB001 , BIB002 , where the processing times were dependent on the total processing time of already processed jobs rather than their number). The obtained results in this domain were summarized recently by BIB007 . Anyway, the main idea of scheduling problems with the learning effect is that a processor gains an experience while executing jobs. This experience improves efficiency of the processor and as a result it helps to shorten the processing times of the jobs (i.e., the more experience the processor gains, the more the processing time of the next job is shortened). Relation between the job processing time and the experience of the processor is called a learning curve. The following three learning curves were investigated so far: Wright's curve (Figure 1 In the Wright's curve it is assumed that first unit of the experience gives the most shortening of the job processing time and each next unit experience gives less shortening of this time because of a saturation or weariness (thus it looks like convex decreasing exponential function). The S-shaped curve describes the learning effect more precisely, since it includes three main phases of this phenomenon, i.e., initiation, learning and maturity. In the first phase, the processor does not acquire the experience in its maximal capabilities (e.g. because of organizing of a workplace) -thus the function decreases slowly. The processor is the most efficient in acquiring the experience in the next phase -just after the initiation -then the function decreases the fastest. Finally, in the last phase, the processor possesses almost the whole possible experience and thus each next unit experience gives less shortening of the job processing time (similarly like in the Wright's curve). As a result, we obtain a function which resembles the letter "S". The stepwise curve describes the learning phenomenon in discrete way and one can obtain different shapes by matching its parameters (value and length of each step). Three models of gaining experience were formulated in the analyzed papers: the model dependent on a number of processed jobs, on a sum of normal processing times of finished jobs and general model where each job can provide different experience to the processor. Now some selected, most important models of processing time covering learning effect will be shown. BIB003 introduces the model in which processing time of a job depends on position of the job in a sequence (in other words it depends on the number of jobs already processed) and which realizes Write's curve: In the above equation p j [r] denotes an actual processing time of job j sequenced in rth position, p j is a normal processing time (without learning) of job j and α > 0 is a learning index. Generalization of this model is considered by BIB004 . They assume that each job can have its own learning index α j : Janiak and  find out that existing models of learning are rather crude simplification of complex industrial problems. Therefore, they consider scheduling problems with more general, experience based processing time: where r l=1 e [l] is an experience of a processor at the moment when processing of the job scheduled in rth position is started (this experience is gained by processing the jobs from positions 1, . . . , r). Note that the above model is generalization of the model of BIB004 , i.e., it is based on the Write's curve and it is assumed that each job can provide different amount of experience, e j , to the processor (unlike the above mentioned position-based models, where each job provides an amount of experience equal to 1). The same authors discover that experience gaining is often a continuous process  . They introduce a general model of experience obtained by the processor at the beginning of processing of a job sequenced in rth position, E β (r). In this model, it is assumed that a part of the experience from a job sequenced in rth position is gained at the beginning of its processing and the remaining part after the completion of this job: [r] e [r] , where E(r − 1) is the total experience gained by the processor during processing the jobs from the positions 1, . . . , r − 1 and β [r] ∈ [0, 1] is a parameter which determines the part of experience e [r] provided to the processor at the beginning of processing of job sequenced in rth position. Based on the above model of the experience, the authors provide a general model of the job processing time with the learning effect and the S-shaped learning curve: where g j denotes a learning threshold of job j and α j is a learning index of this job. In BIB008 these authors introduce a stepwise function of processing time including the general model of experience E β (r): . . . The authors analyze this model, since it is not restricted to any particular shape and thus it can fit every possible learning function by matching its parameters (value, p j,q , and length, [ The authors of the above mentioned papers describe there only short and general examples of learning phenomenon (without scheduling process) in practical situations, mainly in assembly environment where workers improve their skills by repeating similar operations (i.e., they learn). These examples seem to be intuitive, however there is not presented full and exhaustive real-life example (considering also scheduling process), with all necessary details, where scheduling process, specific environment of processors, model of job processing times, etc., would be noticeable explicitly. Another research direction in the area of scheduling with the learning effect is to analyze the problems with the job processing times dependent on time spent by processor on executing earlier jobs rather than only on number of these jobs. As an example of this phenomenon, an optimization of surface inspection of steel plates or bars in a foundry is given. There is a set of steel plates or bars that need to be checked if they do not have any surface deffects. Time required to perform the inspection of one element depends on its area (plates) or length (bars). Authors claim that a person who makes inspection learns more if more time spends on checking. In scheduling context a set of elements to be checked is a set of jobs and a person that perform this quality control may be viewed as a processor. Unfortunately, again the example is superficial and unconvincing (especially the learning process). In the considered area, BIB005 propose the following model: where p [l] denotes normal processing time of job scheduled in lth position and α j > 0 is a learning index of job j. Similar model is investigated also by BIB006 : Finally, it is worth mentioning that the concept of learning under scheduling context was mentioned some years earlier BIB001 , BIB002 ), however, these authors do not consider any specified model of job processing times. They provide only some preliminary general considerations. To sum up practical motivation of the analyzed research, there should be emphasized that the presented examples of practical application of scheduling problems with the learning effect are too brief. They usually contain only a description of the learning effect or (rarely) only scheduling process, but do not contain a meaningful combination of both these processes. As long as full and exhaustive real-life example is not given, there is no sense to do research (from practical point of view) in the area of scheduling with the learning effect. Recently, there were published two papers BIB009 ,  ) examining even the learning effect in a multiprocessor flow shop environment without any real-life practical justification.