Two Kinds Of Scheduling Problems With Resource Controllable Processing Times

Scheduling problem is a typical class of combinatorial optimization problem.Set a certain number of machines and jobs.Specified the processing time that required for each job at each machine,and the orders for machine which processed each job.The problem is that ensure the processing order of the jobs at each machine to minimize the selected objective function in advance.In traditional scheduling problems,the processing time of a job is a constant.However,in the actual environment,the processing time of the job may be a function related to the allocation of resources and the position of the job in the order.In chapter 1,we mainly introduce the background,the current situation of scheduling problem and present our works in this paper.In chapter 2,we consider the multiple common due-window assignment and single machine scheduling with a job-dependent aging effect and deteriorating maintenance activity.We assume that the processing time of a job is a convex function of the amount of a resource allocated to it,its position in the processing sequence,and its aging effect.The objective is to find the optimal due-window,the optimal maintenance position so as to minimize the total cost,which is a function of earliness,tardiness,due-window starting time.due-window size,resource consumption,makespan.We introduce an efficient(7)(8)4O n and(7)(8)m(10)3O n algorithm to solve the problem,where n is the number of jobs.In chapter 3,We consider a common due-date assignment and single machine scheduling problem in which job processing time has position-dependent workload.Assume that the processing time of a job is a convex function of the amount of a resource allocated to it,its position in the processing sequence and workload.All jobs have a common due date.The objective is to find the optimal due date,the optimal resource allocation scheme and the optimal job sequence so as to minimize the total cost,which is a function of earliness,tardiness,due-date,resource consumption.We introduce an efficient(7)(8)3O n algorithm to solve the problem.Finally,the thesis is summarized,and some sorts of problems to be solved are put forward.