Single-machine Scheduling Problems With General Effects Of Learning And Deterioration

Scheduling problem is an important combinatorial optimization problem. It can be described as using some machines process some given tasks optimally, under certain conditions. In classical scheduling problems, the processing time of a job is assumed to be a constant. However, there are many situations where the processing times of jobs may be subject to change due to learning or deterioration phemomena. But most model are based on sepecific functions. We study the scheduling problems with general of learning and deterioration simultaneously.In this paper, we firstly introduce the definition and classification and expression of scheduling problem, as well as the present research of the scheduling problems with learning effect and deteriorating jobs and the scheduling problem with setup time. In the chapter 2, we mainly discuss a general model with learning effect and deteriorating jobs simultaneously, and every job has a past-sequence-dependent delivery time after it was processed.The actual processing time of a job depends not only on its scheduling position but also on its starting time. We show that the makespan minimization prob-lem, the total completion time minimization problem can be solved in polynomial time. In addition, we show that the total weighted completion time minimization problem, the maximum lateness minimization problem can be solved in polynomial time under certain conditions. In the chapter 3, we study single-machine problems with setup time and general effects of learning and deterioration simultaneously. The setup times are proportional to the length of the already scheduled jobs. That is, the setup times are past-sequence-depentent(p-s-d). The actual processing time of a job depends not only on the processing times of the jobs already processed but also on its scheduled posi-tion. We show that the makespan minimization problem and the total completion time minimization problem are polynomially solvable under the model. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain condition.Althought the concepts of learning effect and aging effect have received extensively attention, most model are based on sepecific functions. We introduce a general model with learning effect and deteriorating jobs, and our results are significant extensions of some of the existing models.