Two Single Machine Scheduling Problems With Controllable Processing Times

Scheduling problem is an important combinatorial optimization problem, which iswidely used in the fields of management, economic, and other subjects. With thedevelopment of modern industry, scheduling problems have broken through thelimitations of classical scheduling problems. The processing time of a job is not constant,and it will change with the change of the starting time of the job, the position of the jobor resource allocation. In the competition among modern enterprises, just-in-timeproduction has become an important competitive strategy. According to the principle ofjust-in-time production, the completion time of a job should be close to a certainmoment (time internal). It will not causes penalty if the job is completed at the moment(during the time internal), and it will cause penalty if the job is finished before or afterthe moment (time internal). In order to improve the productivity of the machine, weconsider performing maintenance on the machine. This paper mainly discusses twosingle-machine scheduling problems with controllable processing times, which containthe main contents are as follows:First of all, in the first chapter, it introduces preliminary knowledge of thescheduling problems, research status of the related problem and the main results of thispaper. In the second chapter, it mainly discusses single machine scheduling problemwith a common due-window and controllable processing times. The processing time of ajob is given as a linear non-increasing function of resource allocation, and the resourceallocation will causes cost. The objective is to minimize total costs which include totalcompletion time, earliness, tardiness, the due-window finishing time, and resourceallocation costs. We have shown that the problem can be formulated as an assignmentproblem, that is, the problem is solvable in polynomial time. The third chapter considersscheduling problem on a single machine with three-models of due-date assignment and controllable processing times under a deteriorating maintenance consideration. It mainlydiscusses the machine maintenance duration is given as a linear nondecreasing functionof its starting time. The three-models of due-date assignment include common due-date,slack due-date and unrestricted due-date. In addition, the actual processing time of a jobis a function of its starting time, its position and resource allocation. The objective is tofind the optimal maintenance position and the optimal sequences to minimize the totalcosts which include total earliness, total tardiness, due date and resource allocation costs.We had shown that the problem is solvable in polynomial time. Finally, we summarizethe mainly result of the paper, and put up with the direction of future research.