Some Single Machine Scheduling Problems With Controllable Processing Time

In the past classical scheduling problems,the processing time of the job was a fixed constant.However,the actual processing time of job is often affected by many factors.Different factors have different effects on the processing time of jobs,e.g.learning effects,deteriorating effects,maintenance activity.This paper studies some single machine scheduling problems with controllable processing time,in which the processing time of the job is a function of its starting time and its position.In the single machine scheduling problem with learning effect,deterioration effect and resource allocation,the learning effect is related to the position of the job,and the deterioration effect is related to the start processing time of the job.The details are follows:1.For the case of convex resource allocation with controllable processing time,we analyze this problem for the CON,SLK and DIF due date assignment methods.The objective is to determine the optimal resource allocation to minimize the weighted costs of earliness,tardiness,due date and resource consumption.It is proved that these problems are all polynomially time solvable.2.For the case of linear resource allocation with controllable processing time,in order to shorten the processing time of the jobs,we add resources to the job and carry out deteriorating maintenance activities at the same time,the time of the maintenance activities is linear degradation and depends on its starting time.The objective is to determine the optimal resource allocation 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 optimal polynomial time algorithms and algorithms complexity are given.3.For the case of linear resource allocation with controllable processing time,one maintenance model is considered:the time of maintenance model depends on its starting time and resource.The objective is to determine the optimal resource allocation 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 optimal polynomial time algorithms are given.