Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5128247 | Discrete Optimization | 2017 | 15 Pages |
Abstract
We consider the Pareto-scheduling with bi-criteria on a single machine in which each task has a positional due index. Two bi-criteria problems are considered: (a) Pareto-scheduling with two agents A and B for minimizing the total completion time of A-tasks and a maximum cost of B-tasks with precedence constraints. (b) Pareto-scheduling under precedence constraints for minimizing two maximum costs of tasks. We show in this paper that the two problems are both solvable in polynomial time. The second result also implies that the Pareto-scheduling under precedence constraints for minimizing two agents' maximum costs is solvable in polynomial time.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Yuan Gao, Jinjiang Yuan,