Single Machine Scheduling Problems With Varying Processing Times

This paper considers single machine scheduling problems with varying processing times, which are described below:First of all, the first chapter studies the background, the research status and the research contents.Secondly, the second chapter studies single machine scheduling with learning effect and controllable deteriorating jobs. The objective is to find the optimal sequence of jobs, the optimal processing time and the optimal resource allocation, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost. Two versions are considered. First is a linear resource function of the job dependent learning factor of job. Second is a convex resource function which combine the learning effect and the actual processing time of a job that depends its starting time. We analyze some important properties of the optimal solution, formulate them as an assignment problem separately, give two optimal O(n3) time algorithms.Thirdly, the third chapter studies single machine scheduling problem with past sequence dependent delivery times, position dependent processing times and multiple common due date. when assumed that the delivery time of a job is proportional to its waiting time, single machine scheduling problem with past sequence dependent delivery times, position dependent processing times and multiple common due date is reseached. We combine past sequence dependent delivery times, position dependent processing times with multiple common due date effectively, we analyze some properties of the optimal solution. And then, we formulate it as an assignment problem and prove it can be solved in polynomial time. In the end, by running an O (n3) algorithm, we ascertain the optimal sequence of jobs, the optimal due date and minimizing the total of earliness, tardiness, due date costs.Then, the forth chapter studies single machine scheduling with piecewise linear decreasing processing times and rejection. In this model, the actual processing time of a job is a piecewise linear decreasing function of its starting time. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected jobs. The problem is NP hard. Based on the analysis of the problem, we give a fully polynominal time approximation scheme. The complexity of the fully polynominal time approximation scheme is O(n4L4/ε3).Finally, the last section in this paper gives some main conclusions.