Single Machine Scheduling Problem With Resource-dependent Variable Processing Time

As one of the most active and potential branches of operational research,scheduling theory(also known as timetable theory)has a profound practical background and broad application prospects,such as machinery manufacturing,process scheduling and airport scheduling,ect.In traditional scheduling problem,it is assumed that the processing time is fixed.However,in actual production and life,the acual processing time of jobs may be changed due to kinds of effects and the allocation of non-renewable resource.This paper mainly studies the following kinds of problems:Firstly,we mainly introduce the background knowledge,the current situation of scheduling problem and present our contribution in this paper.In the second part,we consider a single-machine scheduling problem with variable processing time and deteriorating effect.In this part,the actual procesn the actual processing time of a job is variable and depends on the workload of the job and the amount of non-renewable resources.Three problems are considered.The first one is to minimize the weighted costs of earliness,tardiness,the starting time of the common due-window,the size of the due-window,the makespan and the total completion time.The second is to minimize the costs and problems with early penalty cost,tardy penalty cost and the start time of common due window under the condition of adding resource constraints.The third,we are subject to the constraint that the total cost with early and tardy cost is less than or equal to a fixed amount to minimize the total resource.Three optimal polynomial time algorithms and algorithms complexity are given.In the third part,we further consider a single machine scheduling problem with truncated control learning effect and aging effect.In this section all jobs have a common due-window.Two models are considered.For the first,we aim to minimize the weighted costs of earliness,tardiness,the starting time of the common due-window,the size of the due-window,the total absolute completion difference and the total completion time.For the second,We constrain the total resource amount to minimize the weighted costs of earliness,tardiness,the starting time of the common due-window,the size of the due-window,the total absolute completion difference andthe total completion time.We show that the problems are polynomial solvable by transforming them into assignment problems.Two optimal algorithms and an example are given.In the fourth part,we consider a single machine scheduling problem with variable processing time and setup time on the basis of the first three parts.In this section,the actural processing time of a job is a convex function of the resource amount allocated to it.All jobs have a common due-window.The actual processing time of the jobs has deteriorating effect and depends on the workload of the job and the amount of non-renewable resources.In addition,each job has a controllable ready time,which also depends on the amount of non-renewable resources allocated.The goal is to minimize the total cost of earliness,tardiness,the starting time of the common due-window and the size of due-window by determining the optimal sequence and the optimal resource allocation under the premise that the total resources are limited.The above problems are transformed into matching problems,and a heuristic algorithm is given.Finally,we summarize the whole paper and further research direction is pointed out.