Single-machine Due-window Assignment With Deteriorating Maintenance

Scheduling problem is an important combinatorial optimization problem, and it isattracting a lot of attention because of its deep background in the real world and brightfuture in various application environments. A feature of the scheduling problem is: thereare a lot of models to study; the algorithms to be applicable to some models are not beingable to suit for other problems even if the conditions in the models are changed slightly.The classical scheduling problem usually assumes that all the processing time is constant,while due to many factors (such as the processing machines, jobs to be processed andprocessing sequences, etc) the processing time of jobs is not necessarily changed. Thispaper mainly study Single-machine due-window assignment with deterioratingmaintenance, the mainly content is as follows:Chapter 1 first introduces the definition and expression and classification of thescheduling problems, introduce some research results of scheduling problem withmaintenance activity. Then we introduce scheduling problem with deterioratingmaintenance and scheduling problem with due-window.Chapter 2 mainly studies the single-machine and due-window assignment schedulingproblem with deteriorating processing time. The objective is to find jointly the optimal timeto perform maintenance, the optimal location and size of the due-window, and the optimaljob sequence to minimize the total earliness, tardiness and due-window related costs. Weshow that the problem has an optimal algorithm and can be optimally solved inO ( n 2logn )time.Chapter 3 studies two single machine scheduling problems with due-windowassignment and deteriorating maintenance: processing time depends on maintenanceactivity and scheduling position. We show that each of the problems has an optimalalgorithm and can be optimally solved inO ( n 2logn )time.