Sequentially Degraded Workpiece Ordering Problems With Distribution

Scheduling problem is also called the timetable theory,it is an important part of combinatorial optimization.It comes from our actual production and life,and is widely used in scientific management,voyage transportation,engineering technology and many other fields.With the progress of science and the competition among industries,for an enterprise,how to arrange production and transportation that makes cost optimal is particularly important.And for customers,how to spend less money and get the best products and service is also something that we want.The scheduling with proportional deterioration and supply-chain scheduling with deterioration are relatively new scheduling models.In this dissertation,many new results of the above models on complexities and algorithms are presented.In chapter one,we introduce some basic fundamental knowledge of scheduling problem and some symbols used in this dissertation.In Chapter two,we consider two supply-chain single-machine problems with proportional deterioration and batch delivery.For the case with each batch delivery cost is relevant to the number of jobs assigned to the delivery batch,we discuss the properties of the optimal schedule and present a pseudo-polynomial time dynamic programming algorithm to minimize the total completion time plus the total delivered cost.And for the case with each batch delivery cost is a fixed constant,we propose and analyze a dynamic programming algorithm to minimize the maximum lateness plus the total delivered cost.In Chapter three,we consider the supply-chain scheduling with an availability constraint and proportional deterioration,in which the machine has an availability constraint and each batch delivery cost is a fixed constant.For the two minimization maximum completion plus the total delivered cost and the total completion time plus the total delivered cost problems,we prove that they are NP-hard,and present pseudo-polynomial time algorithms,respectively.Furthermore,we discuss one special polynomial solvable case.In Chapter four,we consider the single-machine scheduling with proportional deterioration and delivery time.When jobs are released at the same time,we prove that the problem is solvable in polynomial time.When the jobs have distinct release dates,we prove that the problem is NP-hard in the ordinary sense,and present a 2-approximation algorithm.