Research On Single Machine Scheduling Problem With Early Work

The total early work scheduling problem originates from a distributed computing environment,in which continuously operating servers migrate data results from one computing terminal to another computing terminal.If the results arrive at the server before the receiver is available,the server will have to write these large data sets to its hard disk instead of directly transmitting them to Receiver.Obviously,if the receiver is available,you can avoid the data writing process as an intermediate process.Therefore,the goal is to minimize the server's writing process,which becomes when transferring large data sets that must be written to the hard disk Very important.In such a system,only the earlier completion of the work will be punished,and the penalty is proportional to the processing time.Usually when studying the late work,the workpiece will be punished according to the duration of the completion of part of the workpiece after its construction period.Minimize the late work and maximize the early work on parallel identical machines.When considering the optimal solution,these two criteria are equivalent,But when considering approximate solutions,their properties are different.And the research in this paper,the total early work of a single machine will be penalized according to a job is a duration of the parts of the job completed prior to its due-date.The following conclusions will be considered:1)The scheduling problem with the total weighted early work.The early work of a job is a duration of the parts of the job completed prior to its due-date.Analyzes the complexity of the total weighted early work problem with preemptive case,and proposes an Interruption Scheduling Algorithm.The problem without preemptive case is illustrated to be NP-hard by designing a quasi-polynomial dynamic programming algorithm,and data experiments are performed to verify the effectiveness of the algorithm.2)Two-agent scheduling problem with the total weighted early work.The first agent has the same due-date,and the objective function is to minimize the total weighted early work.The objective function of the second agent is the maximum regular function,in special cases,the maximum completion time.The goal is find a scheduling so that when the second agent objective is feasible,the value of the first agent objective function is the smallest.The backpack problem proves that the problem is NP-hard in the general sense.A quasi-polynomial time algorithm for the two-agent single-machine scheduling problem related to the total weighted early work is given.3)The scheduling problem with the total early work in Generalized due dates(abbreviation GDD).It is proved that the problem of the total early work is polynomial solvable;the problem of the total early work with GDD is then extended to allow job rejection,and an upper bound on the total rejection cost is assumed.The dynamic programming algorithm is given;then the objective function is the sum of the total early work and the rejection cost.The partition problem is used to prove that it is hard in the general sense,and the dynamic programming algorithm is given,and the time complexity is analyzed.For a given unavailable interval,the 2 partition shows that minimizing the total early work problem is hard in the general sense,and the dynamic programming algorithm is given.