TWO-MACHINE FLOW SHOP SCHEDULING WITH INDIVIDUAL OPERATION'S REJECTION

A two-machine flow shop scheduling problem with rejection is considered in this paper. The objective is to minimize the sum of makespan of accepted operations and total penalty of rejected operations. Each job has two operations that could be rejected, respectively. Operations on the first machine have penalties α1 times of their processing times and operations on the second machine have penalties α2 times of their processing times. A $\frac{4}{3}$-approximation algorithm is presented for the case where min{α1, α2} < 1 and max{α1, α2} ≥ 1. A dynamic programming algorithm is provided for general α1 and α2. A fully polynomial-time approximation scheme (FPTAS) is designed for all NP-hard cases.