Research On Scheduling Problems With Delivery Times

This article studies single machine scheduling problems with past-sequence-dependent（p-s-d）delivery times,where the p-s-d delivery time of a job dependents on its waiting times of processing.The goal of this paper is to find the optimal sequence,so that the objective functions are to be minimized.The main contents of this paper are given as follows:Chapter 1 expounds the background and significance of the scheduling problems with p-s-d delivery times,introduces the related research results,and the main results and the chapters arrangement of this paper.Chapter 2 focuses on fixed processing times,we study the problems with p-s-d delivery times.We prove that the total（discounted）weighted completion time minimization can be solved in O（nlogn）time,where n is the number of jobs,and the weight is a position-dependent weight.For the common and slack due-window assignment problems with position-dependent weights,some properties of the optimal solution are analyzed,and it is proved that the problems can be solved in O（nlog n）time.The model can also be extended to the problems that minimize the scheduling cost,which involves the makespan,total completion time（TC）,total absolute differences in completion times（TADC）,and total absolute differences in waiting times（TADW）.Chapter 3 considers variable processing times,we study the problems with p-s-d delivery times.There are two variable conditions of the job processing times,which involve the general position-dependent processing times and time-dependent processing times.For the problems with general position-dependent processing times,we prove that the problems can be formulated as an assignment problems,which can be solved in O（n 3）time.For the problems with time-dependent processing times,we prove that the problems can be solved in O（n log n）time.Chapter 4 investigates the processing times controlled by the resource,we research the problems with p-s-d delivery times.The actual processing time of jobs can be expressed as a linear and convex functions of the resource.Under the linear resource consumption and convex resource consumption,we prove that the total cost（i.e.,the liner weighted sum of scheduling cost and resource consumption cost）minimization can be solved in polynomial time.Under the convex consumption,we consider two bi-criterion problems,i.e.,to minimize the scheduling cost subject to the resource consumption cost being limited,and to minimize the resource consumption cost subject to the scheduling cost being limited.Finally,the general problems are applied to some special scheduling problems.We prove that all the problems can be solved in polynomial time.