Some Single Machine Scheduling Problems With Deterioration Effects

In practical production,the jobs are processed on the machine in order and each job has a basic processing time.However,the actual processing time of the job will increase if it is scheduled later in a sequence,which is essentially the concept of deterioration effects.The machine may have setup times before processing different jobs,and no job can be processed during this period.When the setup time is proportional to the length of the already processed jobs,we define the setup time is past-sequence dependent(p-s-d).In production activities,the machine can be restored to a better state by adding maintenance activities.At the same time,we can use resources to reduce the actual processing time of the jobs.In addition,outsourcing and other methods can be adopted to refuse to process some jobs with low profits or long processing time et.al,thus improving production efficiency.Therefore,it is meaningful to study the scheduling problems with deteriorating effects,past sequence dependent setup times,job rejection,resource allocation and maintenance activities.This paper studies several single-machine scheduling problems with deteriorating effects.The main contents are summarized as follows:1.This paper considers single machine scheduling problems with p-s-d setup times,deterioration effects and job rejection.The goal is to minimize the following four objective functions:(1)the sum of the makespan and the total rejection penalties;(2)the sum of the total completion time and the total rejection penalties;(3)the sum of the total absolute differences in completion times and the total rejection penalties;(4)the sum of the total absolute differences in waiting times and the total rejection penalties.They are transformed into assignment problems to determine which job is accepted and obtain the optimal sequence of accepted jobs.A polynomial time algorithm with complexityO(n~4)is given.2.This paper considers two single machine scheduling problems with deterioration effects,convex resource allocation and a maintenance activity.One problem is to minimize the weighted penalties for the sum of earliness,tardiness,common flow allowance and maximum completion time subject to an upper bound on the total resource cost,the other is to minimize the total resource cost subject to an upper bound on the total penalty cost.Both of the two problems are to determine the optimal sequence of job,the optimal position of the maintenance activity,the optimal common flow allowance and the amount of resource allocation under the slake due date assignment.The two problems both can be formulated as the assignment problems and polynomial time algorithms with complexityO(n~4)are given.3.Single machine scheduling problem with deterioration effects,p-s-d setup times,a deteriorating maintenance activity and slake due window assignment is studied in this paper.The duration time of the deteriorating maintenance activity is a linear function of its waiting time.Under the slake due window assignment,the goal is to determine the deteriorating maintenance,due-window and the optimal job sequence such that the weighted penalties including earliness and tardiness,the number of early and tardy jobs,due-window starting time and size is minimized.The problem can be formulated as the assignment problem and polynomial time algorithm with complexityO(n~6)is given.The above problems are verified by numerical examples.