Study On Several Multicriteria Scheduling Problems

Scheduling is to complete the tasks that need to be completed with certain resources.The strategy of scheduling is to make one criterion or multicriteria reach the ideal or optimal value Generally,there are some constraints to complete a specific scheduling.For example,in the batch-scheduling model,a common constraint is that batch capacity is unbounded or bounded In recent years,multicriteria scheduling is a rapidly developing modern scheduling model,which has a large application background.In our life,many practical problems can be transformed into multicriteria scheduling problems by establishing appropriate models,so the research on multicriteria scheduling problems has great practical significanceThe research content of this paper is as follows1.We consider the hierarchical optimization scheduling problem in respect to two maximum cost functions on a parallel-batching machine with the unbounded batch capacityBy analyzing the properties of the problem,we design an O(n4)-time algorithm2.We consider the hierarchical optimization scheduling problem in respect to two maximum cost functions on a serial-batching machine with the unbounded batch capacityFor the above problem,we give an O(n4)-time algorithm3.We consider the hierarchical optimization scheduling problem in respect to two maximum cost functions on a serial-batching machine with the bounded batch capacityFor the above problem,we give an O(n4)-time algorithm4.We consider the simultaneous optimization scheduling problem in respect to the maximum cost and the makespan on a serial-batching machine with the bounded batch capacity.It is known that there is an O(n4)-time algorithm for the problem.First,we point out that the time bound of the algorithm should be O(n4 logn).And we propose an improved O(n4)-time algorithm for this problem5.We consider the simultaneous optimization scheduling problem in respect to the maximum lateness and the makespan on a serial-batching machine with the bounded batch capacity.It is known that there is an O(n4)-time algorithm for the problem.First,we point out that the time bound of the algorithm should be O(n4 logn).And we propose an improved O(n3logn)-time algorithm for this problem.