Some Single-machine Scheduling Problems With Learning Effect And Deteriorated Jobs

As one important combinatorial optimization problem, scheduling problems have attracted more and more attention and research and have some important achievements and application. Single-machine scheduling is the most simple problem and one of the most important scheduling problems. In real life, single-machine scheduling has a wide practical background, and is relatively easy to solve, as well as providing guidance for more complex scheduling problems. In classical scheduling problems, there is a basic assumption that jobs’processing time is a constant. But in some real-life situations, the processing time of a job is not a constant, instead, a function of its starting time. On one hand, as machines are more and more proficient, the job’s processing time can be reduce, which is called the learning effect. On the other hand, the job’s processing time can be increase after machines’long-time working, which is called the effect of deteriorating. The phenomena of learning effect and deteriorating jobs occurring simultaneously can be found in many real-life situations. Recently, the learning effect and the concept of deteriorating jobs have been extensively studied. In this paper, we study some single-machine scheduling problems with the learning effect and deteriorating jobs.In the paper, we first establish two different model for the single-machine schedul-ing problem with these two effects. The first model is for the case that there is no basic processing time. The learning effect is related to the job’s position in a sequence and the deterioration model is a linear function of their starting times. In the second model, we assume that the deteriorating rate is proportional to the basic job processing time. Based on the two models, we solve the single-machine scheduling problem with the per-formance measures including makespan, total completion time, total weighted comple-tion time and maximum lateness. The makespan and total completion time minimization problems can be solved by the smallest deteriorating rate (SDR) rule. The weighted total completion time minimization problem can be solved by the weighted smallest deterio- rating rate (WSDR) rule under some agreeable condition. The maximum lateness mini-mization problem can be solved by the earliest due date (EDD) rule under some agreeable condition.