Preemptive scheduling with two minimax criteria

Two preemptive single-machine bicriteria scheduling problems with release dates and deadlines are considered in this paper. Each criterion is formulated as a maximum cost. In the first problem the cost of both criteria depends on the completion time of the tasks. This problem can be solved by enumerating all the Pareto optimal points with an approach proposed by Hoogeveen for the nonpreemptive problem without release dates. In the second problem, the costs of one criterion are dependent on the completion times of the tasks and the costs of the other criterion are dependent on the start times. This problem is more difficult but an efficient algorithm is proposed for a sub-problem with heads, tails, release dates and deadlines that appears in the job-shop scheduling problem.