Two-machine flow-shop scheduling with rejection

► We study a two-machine flow-shop scheduling problem with rejection. ► We measure the quality of a schedule by two criteria: the makespan and the total rejection cost. ► We show that the problem of minimizing the sum of the two criteria (problem P1) is ordinary NP-hard. ► We provide an FPTAS and two 2-approximation algorithms for solving the P1 problem. ► The bicriteria problem is shown to be ordinary NP-hard and a two-dimensional FPTAS is provided.