  We consider the two-parallel machines scheduling problem, with the aim of
minimizing the maximum lateness and the makespan. Formally, the problem is
defined as follows. We have to schedule a set J of n jobs on two identical
machines. Each job i in J has a processing time p_i and a delivery time q_i.
Each machine can only perform one job at a given time. The machines are
available at time t=0 and each of them can process at most one job at a given
time. The problem is to find a sequence of jobs, with the objective of
minimizing the maximum lateness L_max and the makespan C_max. With no loss of
generality, we consider that all data are integers and that jobs are indexed in
non-increasing order of their delivery times: q_1 >= q_2 >= ... >= q_n. This
paper proposes an exact algorithm (based on a dynamic programming) to generate
the complete Pareto Frontier in a pseudo-polynomial time. Then, we present an
FPTAS (Fully Polynomial Time Approximation Scheme) to generate an approximate
Pareto Frontier, based on the conversion of the dynamic programming. The
proposed FPTAS is strongly polynomial. Some numerical experiments are provided
in order to compare the two proposed approaches.
