A Study On A Type Of Multicriteria Scheduling Problem With Due Date

Scheduling is a kind of important combinational optimization problem.In the classical scheduling it is assumed that the purpose of scheduling is to minimize the value of a one-dimension criterion function which measures the quality of scheduling,and the criterion function is a increase function of completion time of jobs,that is regular criterion.But with the development of society,many enterprises are considering more and more factors,for example,considering servicing quality of products,while considering resticton of inventory.The first,the earliness of completion time will increase the inventory of finished products and cost of inventory;the other,the lateness will affect the servicing quality of jobs.So the multicriterion scheduling problem which considers multiple criterions at a time comes out.Multicriteria scheduling,as a multicriteria decision problem,become more and more important in solving some complex problems in economy,management,engeneering,military and society.The multicriteria scheduling is a important new classes of scheduling problem and has wide application background in realization.In this paper,we consider a type of multicriteria scheduling problem.The object of scheduling is to minimize the value of weighted earliness and tardiness penalty function.In the first chapter of the paper,we look back the study state today of scheduling problem on the basic of introducing scheduling problem;In the second chapter,we tell the knowledge about scheduling problem;In the third chapter,we study the single machine minimum total earliness and tardiness multicriteria scheduling problem with common due date,and design two heuristic algorithm foe solving this problem,we obtain a polynomial algorithm for the special caseαi =βi= 1;In the fourth chapter we study the parallel machine minimum total earliness and tardiness multicriteria scheduling problem with different due date,give a heuristic algorithm and analyses its quality by an example;The fifth chapter gives a conclusion of total earliness and tardiness multicriteria scheduling problem with due date and proposes some explanation and outlook of this type of problems.