Single Machine Scheduling Problem With Deteriorating Maintenance And Resource Allocation

One branch of the combinatorial optimization is scheduling.It has an important position and profound practical background.It emerges in the process of machine manufacturing,and has been widely used in many fields such as management science,transportation industry,computer science and engineering technology.Scheduling plays a certain role in improving efficiency,resource development and allocation,project progress arrangement and economic operation.In the classical scheduling problem,it is assumed that the processing time of a job is constant and the job must be processed continuously without interruption.However,in actual production,the actual processing time of the job will be affected by many factors,such as machine equipment or job itself,resource allocation,so it is impossible to remain constant all the time,and it may be necessary to maintain the machine for a period of time to improve its efficiency.The main content of this paper is as follows.In chapter 1,we briefly introduce the research background of scheduling problem,the status here and abroad,the content and chapter arrangement of this paper.In chapter 2,we mainly study a single machine scheduling problem with deteriorating maintenance,slack due-date assignment and resource allocation.The actual processing time of a job is a function of two parameters,one is the amount of resource allocated,and the other is position-dependent and time-dependent deterioration effect.In order to counteract the deterioration effect on the machine,we can add a maintenance activity and the maintenance duration is dependent on its starting time.Under the condition that the total resource amount is limited,the objective is to determine the optimal results of common slack time,the maintenance position,the resource allocation and the job schedule to minimize the objective function consisting of the earliness and tardiness of the jobs,the common slack time,the makespan and the total completion time,i.e.minimize the total costs.According to the related knowledge of convex optimization,the problem is transformed into an assignment problem through a series of transformations,and we present a polynomial time optimal algorithm.In chapter 3,we mainly consider a single machine scheduling problem with variable job processing times and maintenance,slack due-date assignment and convex resource allocation.The actual processing time of a job is a function of the non-renewable resource amount allocated,position-dependent and starting time-dependent deterioration effect,maintenance is also performed throughout the planning time.The objective is to determine the optimal job schedule,optimal common slack time,optimal maintenance position and optimal resource allocation to minimize the objective function consisting of a series of parameters.According to the related knowledge of optimization,we show that the problem is polynomial solvable.In chapter 4,we mainly study a single machine scheduling problem with setup times and deteriorating maintenance.The actual processing time of a job is determined by the non-renewable resource amount allocated and position-dependent deterioration effect.In this problem,each job requires a period of setup time before processing,which is a convex function of resource allocation.Execute a maintenance activity within the planning time.Similarly,only a certain amount of resource are given to determine the job schedule,common due-date,maintenance position and resource allocation when the objective function consisting of earliness and tardiness of the jobs,common due-date and the makespan is minimum.We finally present a heuristic algorithm to solve the problem.