Some Scheduling Problems On Uniform Machines With Rejection

In real life,we often encounter the situation that the processing time of the job depends on the start processing time.The later the job starts processing,the longer the actual processing time.At the same time,workers can gain experience after repeating the same or similar tasks,and the production efficiency will improve over time.Therefore,the later the job is processed,the shorter the processing time.This situation is called learning effect.In addition,due to the limited resources,the decision-maker may choose some jobs to process,job incurs some penalty due to the rejection,namely,rejection penalty.Moreover,machines can not work due to maintenance or failure and other reasons in a certain period of time,namely,non-availability interval.In this paper,some scheduling problems on uniform machines with rejection are discussed.The specific contents are summarized as follows:1.The problem of minimizing the sum of the makespan of the accepted jobs and the total rej ection penalty of the rej ected jobs are studied as follows:(1)The scheduling problem of m uniform machines with deteriorating jobs,learning effect and rejection is discussed.Firstly,the objective function is modified.For this NP-hard problem,the optimal solution can be obtained by arranging the jobs on each machine according to the shortest basic processing time.A fully polynomial time approximation scheme(FPTAS)is proposed,and its time complexity is O(n3m+2L2m+2/?2m+1).(2)The scheduling problem of two uniform machines with deteriorating jobs,rejection and unavailability intervals is discussed.The optimal solution can be obtained by sequencing in non decreasing order of {aj/bj} of the jobs before,after the unavailable interval and another machine.An FPTAS is given,and the time complexity is O(n6L4/?3).(3)The scheduling problem of two uniform machines with rejection and unavailability intervals is discussed.Firstly,the objective function is modified and the property of the optimal solution is given.Then,an FPTAS is proposed and its time complexity is O{n4L4/?3).2.For the problem of minimizing the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs,the model of two uniform machines with deteriorating jobs,rejection and unavailable intervals are discussed.One of the machines has an unavailable interval.For this NP-hard problem,an FPTAS is given according to the property of the optimal solution,and its time complexity is O(n9L6/?5)?...