Optimization Methods For Task Scheduling With Learning And Deteriorating Effects

Nondeterministic of processing times is widespread in manufacturing systems which is one of the key factors on scheduling performance and production efficiency.Learning and deteriorating effects are two important nondeterministic factors in many industries,especially in metallurgical processing,manufacturing and food industries.The robustness of scheduling algorithms are heavily deteriorated by decreased or increased processing times.Generally single machine scheduling problems with learning and/or deteriorating effects could be optimally solved with polynomial time complexities.Because some single machine and majority of multiple machine scheduling problems are NP hard,processing times are dynamic depending on task positions or sum of processing times which result in traditional exact methods,heuristics or meta-heuristics are unsuitable for these problems.Some task scheduling problems with learning and deteriorating effects are considered in this dissertation.The major contributions are shown below.(1)Single machine task scheduling with learning and deteriorating effects.Func-tions between normal processing times and the actual ones are analyzed.A more practical function with learning effects and a general function with learning and deteriorating ef-fects are constructed.Two adjacent tasks in a sequence are exchanged to generate two new sequences.Objective variation functions of the two sequences are constructed.Prop-erties are analyzed and derived.The single-machine problems with learning effects to minimize makespan,total completion time and total square completion time are proved to be polynomial solvable respectively.In addition,optimal solutions could be found single-machine problems with learning and deteriorating effects to minimize the sum of weighted completion times,the maximum lateness,the maximum tardiness and the total tardiness under agreeable situations.(2)Single machine group task scheduling with deteriorating effects to minimize makespan.The problem is described and modeled as a function with time-dependent deteriorating effects by the time series analysis technique.Tasks are assumed to be inter-ruptible.The increasing of maintenance times could lead to the decrease of deteriorating effects.The incremental properties for objective functions with deteriorating effect are derived.Two efficient heuristics are proposed for small size problems.Moreover,an iter-ated algorithm is presented for large size problems which includes for components:initial solution generation,local search,perturbation and the acceptance criterion.Initial solu-tions are constructed by the two heuristics and a random sequence construction method respectively.Initial solutions are improved by an insertion-based local search method.When intensification is strong enough,the current solutions are perturbed and the new current solution is selected from the generated candidate solutions.Whether the current solution is replaced by the newly selected or not is decided by the acceptance criterion.The algorithm stops when the terminal criterion is satisfied and the best solution is re-turned.The analysis of variance technique is adopted to calibrate the involved parameters and algorithm components and to evaluate results among the compared methods.(3)Special multiple stage job scheduling with learning effects.Characteristics of the considered problem are analyzed.The processing time function of a task between its normal processing time and its actual time is developed which is more practical.The function is affected by learning and deteriorating effects as well as task stage.A pair of adjacent jobs in a sequence are exchanged and two different sequences are construct-ed.Properties of the variation function are analyzed and derived.The special multiple stage job problems with learning and deteriorating effects to minimize makespan,total completion time and total square completion time are proved to be polynomial solvable respectively.In addition,optimal solutions could be found for special multiple stage job problems with special learning and deteriorating effects to minimize the sum of weighted completion times,the maximum lateness,the maximum tardiness and the total tardiness under agreeable situations.