Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS UNDER AN AGEING EFFECT <s> Abstract This paper considers the following scheduling problem: Minimize the makespan in a single facility problem where the processing time of a job consists of a fixed and a variable part. The variable part depends on the start time of the job. The objective is to minimize makespan. Two optimizing algorithms based on dynamic programming and branch-and-bound techniques and five heuristic rules have been proposed. The heuristic solutions have been compared with the optimal solution for upto 7 jobs to identify the best heuristic. The detailed computational results for the branch-and-bound and the best heuristic rule are then obtained for problems with up to 15 jobs. <s> BIB001 </s> Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS UNDER AN AGEING EFFECT <s> The paper is devoted to some single machine scheduling problems, where job processing times are defined by functions dependent on their positions in the sequence. It is assumed that each job is available for processing at its ready time. We prove some properties of the special cases of the problems for the following optimization criteria: makespan, total completion time and total weighted completion time. We prove strong NP-hardness of the makespan minimization problem for two different models of job processing time. The reductions are done from the well-known 3-Partition Problem. In order to solve the makespan minimization problems, we suggest the Earliest Ready Date algorithms, for which the worst-case ratios are calculated. We also prove that the makespan minimization problem with job ready times is equivalent to the maximum lateness minimization problem. <s> BIB002 </s> Scheduling problems with learning and ageing effects: a survey <s> SCHEDULING PROBLEMS UNDER AN AGEING EFFECT <s> In this paper a scheduling problem that takes into consideration a phenomenon called ‘aging effect’ with reference to Computer Numerical Control drilling or cutting machines is investigated. In the aftermath of this effect an execution of jobs leads to a deterioration of a machine; thus processing times of jobs increase and the production facility becomes less efficient. However, it is highly desirable to minimize the negative influence of this effect. In general, it can be done by formulating such a problem in the scheduling context and optimizing an order of jobs to minimize the given criterion. Therefore, on this basis a makespan minimization problem on a single machine with release dates and the aging effect is formulated, where the job processing times are described by non-decreasing functions dependent on fatigue (wear) of machine. It is proved that even the special cases of the problem are NP-hard. Moreover, some problems equivalences are shown and polynomially solvable cases are also provided. <s> BIB003
An ageing effect is a phenomenon of reduction the processor efficiency as a result of its fatigue (wear). Thus, the processing times of the subsequent jobs executed by the processor increase. Job processing time may be an (increasing) function of: job starting time (deteriorating jobs), position or sum of normal processing times of jobs already processed. Moreover, there was considered a general model, in which processing of one job may cause different wear of the processor than processing of another job. Analogous to the learning effect, several types of relation between job processing time and wear of a processor were considered: exponential, linear, piecewise linear, exponential with ageing threshold and stepwise. There are much less papers on the scheduling problems with the ageing effect than the ones with the learning effect -see, e.g., for a survey. Let us show some selected, most important results in this area. A model with linear curve of wear is investigated by BIB002 : where p j [r] denotes actual processing time of the job j scheduled in position r, p j is normal processing time of this job and α j 0 is an ageing index. The authors describe short and general practical example of the phenomenon of ageing in the context of decreasing sharpness of drills, however they do not explain scheduling process, model of job processing times, etc. BIB001 introduce a piecewise linear model and processing time dependent on starting time: where t is starting time of job j, α j is its ageing index and g j denotes ageing threshold dependent on this job. Analogous model but with processing time dependent on position, r, of the job is formulated by  : The authors present an interesting example of practical application of the analyzed problem -an optimization of data transmission in a client-server type computer network. The problem is as follows. There are a server and a set of clients. The server connection has a limited bandwidth. When each client connects to the server, it gets some available part of the bandwith. In response, the server must send a large amount of initialization data (e.g. configuration data, program code) and keep the connection open. Note that every client requires different initialization data and a different amount of work from server to prepare data. When the number of established connections increases, resources (processor time, network bandwidth, etc.) become scarce. As a result, the time required to open new connection, prepare and send initialization data increases. What is important, is the fact that client requests occur in different moments. The objective is to determine such a sequence of processing of clients' requests that minimizes the time required to open and initialize all connections. This problem can be considered as a scheduling problem with an ageing effect, ready times and a makespan criterion. Although the example is interesting, there should be explained more precisely the details of network communication (especially in the context of scheduling clients' requests and ageing effect in initializing of new connections), since in the present form the described problem seems to be immaterial. BIB003 introduce a general model of wear of the processor, W (r − 1) = r−1 j=1 w j , caused by processing the jobs from the positions 1, . . . , r − 1 of a sequence. Obviously, each job causes wear of the processor in different extent, which is described just by the parameter w j . Based on the described general wear model, the authors investigate exponential curve with an ageing threshold: In the above equation all indices are non-negative rational numbers and W (r − 1) is wear of the processor after completion of r − 1 jobs. As a practical application for this model, a production with usage of Computer Numerical Control (CNC) drilling or cutting machines is shown. This example is based on that presented by BIB002 and again it is short and vague. Indeed, the both examples are unconvincing and do not include the scheduling process. Similarly as for the scheduling problems with the learning effect, the presented practical examples of scheduling problems with the ageing effect are vague or incomplete. Especially, the process of scheduling is not explained sufficiently in the presented examples. Therefore, the conducted research should be much more justified from a practical point of view. Unless complete and convincing real-life example (in which the both scheduling and ageing processes would be shown) is not given, there is no use to consider such problems from practical point of view.