Single two-stage flowshop and parallel two-stage flowshops scheduling with optional job rejection

Two-stage flowshop scheduling has been extensively studied in the scheduling community. Unlike traditional objectives, which focus on minimizing job completion time objectives such as makespan or total tardiness, this study addresses the minimization of total job rejection costs while ensuring that the makespan remains within a specified threshold. This problem is motivated by outsourcing practices in certain make-to-order scenarios, where a cost is incurred if the manufacturer opts to reject a job and outsource it instead. For the single two-stage flowshop case, a polynomial time approximation scheme is proposed, utilizing a guessing strategy combined with a linear programming rounding technique. For the parallel two-stage flowshops case, when the number of flowshops is a fixed constant, a bicriteria (1, 1 + ε)-approximation algorithm is introduced, i.e., the total rejection cost does not exceed the minimum possible value, but the schedule is relaxed to possibly exceed the bound on the makespan by a factor of ε, where ε is a given arbitrarily small positive constant. The algorithm is derived from a pseudo-polynomial time dynamic programming algorithm coupled with a trimming technique. When the number of flowshops is part of the input, a bicriteria (1, 3)-approximation algorithm is proposed. The problem formulation and algorithmic results offer production managers greater flexibility in managing job outsourcing decisions.