This paper studies the problem of scheduling $n$ jobs on a single machine to minimize total completion time and maximum cost, simultaneously. Each job is associated with a positional deadline that indicates the largest ordinal number of this job in any feasible schedule. The jobs have agreeable release and processing times, meaning that jobs with larger release times also have larger processing times. The agreeability assumption is reasonable since both the single-criterion problems (without positional deadline constraints) of minimizing total completion time and maximum lateness on a single machine with arbitrary release and processing times are strongly NP-hard. An $O(n^3)$-time Pareto optimal algorithm is presented. The previously known algorithms only solve two special cases of the agreeability assumption: either the case of equal release times in $O(n^4)$ time, or the case of equal processing times (without positional deadline constraints) in $O(n^3)$ time.

We consider the problem of scheduling jobs with delivery times and inclusive processing set restrictions on unbounded batch machines to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint. We develop a polynomial time approximation scheme for this strongly NP-hard problem that runs in linear time for any fixed accuracy requirement.

We study the problem of non-preemptively scheduling jobs from two agents on an unbounded serial-batch machine. Agents $A$ and $B$ have $n_A$ and $n_B$ jobs. The machine can process any number of jobs sequentially as a batch, and the processing time of the batch is equal to the total processing time of the jobs in it. Each batch requires a setup time before it is processed. Compatibility means that the jobs from different agents can be processed in a common batch; Otherwise, the jobs from different agents are incompatible. Both the compatible and incompatible models are considered, under both the batch availability and item availability assumptions. Batch availability means that any job in a batch is not available until all the jobs in this batch are completed. Item availability means that a job in a batch becomes available immediately after it is completed processing. The completion time of a job is defined to be the moment when it is available. The goal is to minimize the makespan of agent $A$ and the maximum lateness of agent $B$ simultaneously. For the compatible model with batch availability, an $O(n_A+n_B^2\log n_B)$-time algorithm is presented which improves the existing $O(n_A+n_B^4\log n_B)$-time algorithm. A slight modification of the algorithm solves the incompatible model with batch availability in $O(n_A+n_B^2\log n_B)$ time, which has the same time complexity as the existing algorithm. For the compatible model with item availability, the analysis shows that it is easy and admits an $O(n_A+n_B\log n_B)$-time algorithm. For the incompatible model with item availability, an $O(n_A+n_B\log n_B)$-time algorithm is also obtained which improves the existing $O(n_A+n_B^2)$-time algorithm. The algorithms can generate all Pareto optimal points and find a corresponding Pareto optimal schedule for each Pareto optimal point.

This paper addresses the problem of scheduling $n$ equal-processing-time jobs with release dates non-preemptively on identical machines to optimize two criteria simultaneously or hierarchically. For simultaneous optimization of total completion time (and makespan) and maximum cost, an algorithm is presented which can produce all Pareto-optimal points together with the corresponding schedules. The algorithm is then adapted to solve the hierarchical optimization of two min-max criteria, and the final schedule has a minimum total completion time and minimum makespan among the hierarchical optimal schedules. The two algorithms provided in this paper run in $O(n^3)$ time.