Some Single-machine Scheduling Problems With Learning Effect And Deterioration

Scheduling problem is an important combinatorial optimization problem. In the classical theory, the processing times of the jobs are generally constant. Job processing time with the learning effect or deterioration of the scheduling problem is the promotion of classical scheduling problem. Although learning effect and deteriorating jobs have been well discussed, it is rarely considered simultaneously. This paper mainly considers single machine scheduling with learning effect and deterioration.In this paper, we introduce the definition and expression of scheduling, as well as the research status of the job processing times which are defined by functions of their starting times or positions in the sequence.In chapter 2, we mainly deal with the single-machine scheduling problems with job processing times defined as follows: they are the functions of their starting times and positions in the sequence. For several objective functions we prove they can be solved by polynomial time algorithms.On the basis of chapter 2, we add the group technology in the chapter 3 and study two kinds model: in the first one the groups need simple linear setup times, and in another one need not.In chapter 4, the jobs have not only learning effect and deterioration, but also past-sequence-dependent setup times.At the last, we give a summary of this thesis and propose a number of new problems to be solved.