Two-Machine Flow Shop and Open Shop Scheduling Problems under a Knapsack Constraint

This paper investigates two-machine flow shop and open shop scheduling problems under a knapsack constraint. In these problems, a set of jobs is available at time zero. Each job can either be accepted and processed on both machines, or rejected. A rejected job incurs a rejection penalty and occupies a certain rejection size. The objective is to minimize the makespan of the accepted jobs plus the total rejection penalty of the rejected jobs, subject to the constraint that the total rejection size of the rejected jobs does not exceed a given upper bound. For both the two-machine flow shop and the open shop settings, we develop pseudo-polynomial-time dynamic programming algorithms that yield exact solutions, as well as 3-approximation algorithms. Furthermore, based on these exact dynamic programming algorithms and the 3-approximation algorithms, we design fully polynomial-time approximation schemes (FPTASs) for these two problems.