Two Kinds Of Scheduling Problems With Special Effects

As a branch of operational research, an applied science, scheduling problems has a profound practical background and broad applicational prospect. During the 1990s and the 21st century, mathematics, focusing on the development from continuous objects to discrete objects and combinational optimization will have great development. Because in this field, there are many urgent and extremely difficult problems, including how to let each parts divise, wiring and layout. The division, wiring and layout is related with scheduling.Scheduling with learning effect, deteriorating effect and availability con-straint are three popular scheduling models, Because of they are more close to real production and life, so attracting more and more attention recently. In this dissertation,two kinds of scheduing problems with special effects 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 summarized.In the second chapter, we study the problems of minimizing the total weighted completed time on single machine problems, identical machines and uniform ma-chines, which has the same actual processing time and with an special learning effect which not only related to the position of job bot also concerned with the time of all jobs who in front of it. We provide a optimal algorithms correspond-ing to a special case of all jobs with constant processing time and prove their optimality.In the third chapter,aiming at the scheduling problems with availability con-straint, in which the processing time of job is variable. we study scheduling problems of availability constraint with learning and deteriorating effects on single machine problems,two identical machines and two uniform machines. A dynamic programming algorithm is provided for the machine maintenance in a general case at any time, and the validity of the algorithm is also illustrated by an example. A polynomial algorithm is given for the maintenance before the use of the machine in the special case.