Single-machine Scheduling Problems With Variable Processing Time And Setup Times

Scheduling problems is an important combinatorial optimization problem. In the classic scheduling model, the actual processing time is fixed. However, following with the development of society, in some actual production, the processing time of a job depends not only on its normal processing time of the job but also on its scheduling position. As we know, some of the job need setup, thus, the scheduling problems with setup times is produced. This paper mainly considers the single machine scheduling problems with variable processing time and proportional setup times.In this paper, we introduce the definition and expression and classification of the scheduling, as well as the research of the learning effects and the setup times. In the chapter 2, we mainly deal with the single-machine scheduling problems with learning effects and proportional setup times. The actual processing time of a job depends not only on the processing time of the job which is already processed but also on its scheduling position. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent(p-s-d).we show that the makespan minimization problems, the total completion time minimization problem and the sum of kth powers of completion time minimization problem can be solved in polynomial time. In the chapter 3,we mainly discuss the single-machine scheduling problems with position-dependent processing time proportional setup times. The actual processing time is related to its scheduling position, the setup times are proportional to the length of the already processed jobs. We also show that the problems to minimize makespan, to minimize total completion time, to minimize the completion time, earliness and tardiness penalties,and so on are polynomially solved. The last of the paper concludes a summary of the content of the paper, and discussed the direction of efforts for the future work.