Bicriteria two-machine flowshop scheduling: approximation algorithms and their limits

We consider bicriteria flowshop scheduling problems with two machines to simultaneously minimize the makespan and the total completion time without any prioritization between the two objectives. An approximation relative to the optimal value of the problem with regard to each objective is adopted, even though a schedule with both objectives reaching their minimum at the same time may not exist. We consider several problems with ordered aspects on processing times such as job ordered and machine ordered. For each problem, we propose a fast \((\rho _1,\rho _2)\)-approximation algorithm, where \(\rho _1\) and \(\rho _2\) indicate the approximation ratios with regard to the makespan and the total completion time, respectively, and we explore the problem’s inapproximability region that cannot be reached by any algorithm.