Research On Scheduling Problems With Late Work Criterion

Scheduling problem,which is one of the classical problems in the fields of combinatorial optimization,computer science,as well as management science,deals with the assignment of a set of jobs to a set of machines,under some constraints,and with the goal of optimizing one or more objectives.Among other criteria,late work is the one related with job' s due date,which equals to the late part of a job executed after it.Scheduling with the goal of late work minimazation was proposed in 1984,and has been widely studied more than 30 years.Based on the previous results under this subject,this thesis is devoted to a deeper exploring in this domain,with the methods of exact algorithms,approximation algorithm,as well as meta-heuristic algorithms.The results in the thesis are listed as following.(1)We study the late work minimization problem on identical machines with common due date constraint,i.e.,every job has a common due d.We prove that the problem is NP-hard in strong sense,when the machine number m is a part of input.However,when m is fixed,the problem turns to be weakly NP-hard,since a dynamic programming method in pseudo-polynomial time could be designed.Then,we prove that LPT algorithm has its approximation ratio 10/9.(2)We extend the models above to the non common due date cases.A branch and bound algorithm is designed to solve two-identical machines scheduling problem,with the technolo?gies of solution represention,lower bound,upper bound and dominating rules.Moreover,an enumeration algorithm is proposed to solve the same problem.When the machine number is greater than 2,a genetic algorithm is devoted to this problem.Several numerical experiments are given,to evaluate the performances of these algorithms.(3)The third topic discussed in this thesis is scheduling problem in a flowshop system.We first prove that the problem of scheduling on a three-machines flowshop system with common due date is strongly NP-hard,Then we propose a particle swarm optimization(PSO)algo-rithm to solve the problem with learning effect.The numerical experiments show that the PSO algorithm is an efficient method,both from algorithm-performance and time consumption views.(4)Finally,we consider the semi-online version of the studied problem.The first model we investigated in this part is scheduling on two identical machines with a common due date,when the total processing time and the largest size of jobs are known in advance.We give the tight bound 10/9 for this model.Then,if only the largest size is know.,we prove that the upper bound is(?)-3/4?1.1375,while the lower bound of this model is(?)-3?1.1231.