Due Window Assignment Scheduling Problems With Position-dependent Weights

Under just-in-time production,this paper studies single machine due-window assignment scheduling problems with position-dependent weights.The objective function(cost)includes the weighted sum of earliness/tardiness,due-window starting time,and due-window size,where the weight of job earliness/tardiness only dependent on its position in a sequence.We need to determine the optimal sequence of jobs,and due-window position such that objective function can be minimized.The main contents of this paper are given as follows:Chapter 1 expounds the background and significance of the due-window scheduling problems with position-dependent weights,introduces the related research results,and the main results and chapters arrangement of this paper.Chapter 2 focuses on fixed processing time,we study due-window assignment scheduling problems with position-dependent weights.The due-window includes the common due-window(CONW),slack due-window(SLKW)and different due-window(DIFW).The dynamic programming algorithm(DP)and general formula deduction are proposed,such that the due-window assignment problem can be solved in(9)~3)and(9)log9))time respectively,where9)is the number of jobs.The model can also be extended to problems with general position-dependent processing time,we prove that the problems can be formulated as an assignment problem,which can be solved in(9)~3)time.Chapter 3 studies single machine due-window assignment scheduling problems with position-dependent weights and variable processing times.The due-window includes the CONW,SLKW and DIFW,and the job actual processing time can be controlled by the resources allocated,its starting time and the position in the sequence.The resource consumption models are divided into the linear resource consumption and convex resource consumption.Under the linear resource consumption and convex resource consumption,we prove that the total cost(i.e.,the linear weighted sum of scheduling cost and resource consumption cost)minimization can be solved in polynomial time,respectively.Under the convex resource 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,we prove that these both problems can be solved in(9)log9))time,respectively.Chapter 4 summarizes the contents of Chapters 2 and 3.