Two Kinds Of Single Machine Problems With Learning Effect

Scheduling is a kind of important field of combinatorial optimization and an active branch of operations research. So it has very broad applied prospect. Scheduling with learning effect is a new scheduling model, which is attracting more and more attention recently. In this dissertation, two kinds of scheduling problems with learning effect are studied. The structure of the article is arranged as follows:In the first chapter, some notations, definitions and basic background infor-mation about the subject are introduced, and then the main research results in this dissertation have been summaried.In the second chapter, we consider several scheduling problems on single-machine with learning effect. The objective functions are the total weighted com-pletion time, the maximum lateness, the lateness and the number of tardy tasks. For the first problem, polynomial time algorithm is given and the computational complexity is analysised. For the other problems, we give optimal algorithms and prove that these algorithms are optimal under corresponding consistent condition: (?) Ji, Jj, pi≤pj=> di≤dj, respectively.In the third chapter, we consider some group scheduling problems on single-machine with learning effect. The objective functions are the makespan, the total completion time,the total weighted completion time and the maximum lateness. We give polynomial time algorithms and prove that these algorithms are optimal for the first three problems, respectively. For the last problem, we give optimal algorithm and prove that the solution obtained by the algorithm is optimal under corresponding consistent condition:(?)Ji,Jj, pi≤pj=>di≤dj.