Some Single-Machine Scheduling Problems WithPosition Dependent Processing Times

In the classical scheduling model, assuming that the processing time is a constant, and jobs being processed on the machine one by one. According to the actual need, the actual processing time of a job is no longer a constant, but is related to the actual problems variables. This thesis mainly studies the some single-machine scheduling problems with position dependent processing times. Among them, the actual processing time of a job is a function depends on its starting time and position in the sequence. The specific content is summarized as follows:1) We consider some single-machine scheduling problems with deteriorating jobs and learning effects. In the model, the actual processing time of a job is a function of its position due to learning effects. The deteriorating effects of jobs are linear functions of their starting time. Firstly, we consider the problems of the makespan, the total completion times and total absolute differences in completion times, respectively. We show that these problems are polynomially solvable under the proposed model. Then, we consider a common due-date assignment problem with learning and deteriorating effect and resource allocation on a single machine. All jobs have a common due-date. The objective is to determine the optimal common due-date, the optimal resource allocation and the optimal sequence to minimize the total costs based on earliness, tardiness, common due-date, and resource consumption. We show that the common due-date assignment problem with learning and deteriorating effect and resource allocation is polynomially solvable.2) In the model, the actual processing time of a job is a general function of its position due to learning effects. The deteriorating effects of jobs are linear functions of their starting time. We consider the problems of the makespan, the total completion times and total absolute differences in completion times, respectively, and show that these problems are polynomially solvable under the proposed model.3) We investigate single-machine scheduling problems under a deteriorating maintenance activity consideration. The actual processing time of a job is a general function depends on its processing time and position in the sequence. The objective is to find the optimal common due-date, the scheduled and the optimal maintenance position as well as the optimal location of the common due-date for minimizing the total of earliness, tardiness and due-date costs. We introduce a polynomial time solution for the problem by transforming this problem into the assignment problem. We also present a special case of the problem and show that it can be optimally solved.