Two‐machine flow‐shop scheduling with rejection

We study a scheduling problem with rejection on a set of two machines in a flow‐shop scheduling system. We evaluate the quality of a solution by two criteria: the first is the makespan and the second is the total rejection cost. We show that the problem of minimizing the makespan plus total rejection cost is $\mathcal{NP}\text{‐}\mathrm{hard}$ and for its solution we provide two different approximation algorithms, a pseudo‐polynomial time optimization algorithm and a fully polynomial time approximation scheme (FPTAS). We also study the problem of finding the entire set of Pareto‐optimal points (this problem is $\mathcal{NP}\text{‐}\mathrm{hard}$ due to the $\mathcal{NP}\text{‐}\mathrm{hardness}$ of the same problem variation on a single machine ). We show that this problem can be solved in pseudo‐polynomial time. Moreover, we show how we can provide an FPTAS that, given that there exists a Pareto optimal schedule with a total rejection cost of at most R and a makespan of at most K, finds a solution with a total rejection cost of at most $(1+ϵ)R$ and a makespan value of at most $(1+ϵ)K$ . This is done by defining a set of auxiliary problems and providing an FPTAS algorithm to each one of them.