Maximizing the Total Weight of Just‐In‐Time Jobs in A Two‐Stage Flexible Flow Shop With Dedicated Machines

ABSTRACT

We study a two‐stage flexible flow shop scheduling problem aimed at maximizing the total weight of just‐in‐time jobs, defined as those that complete exactly on their due dates. Two machine configurations are examined: (i) a single common bottleneck machine at stage 1 and parallel dedicated machines at stage 2; (ii) parallel dedicated machines at stage 1 and a single common bottleneck machine at stage 2, where denotes the number of parallel dedicated machines. For the first configuration, we propose a pseudo‐polynomial‐time dynamic programming algorithm and a fully polynomial‐time approximation scheme when is fixed. For the second configuration, we establish that the problem is strongly ‐hard for arbitrary , even when all jobs have unit weight, and show that it remains ordinarily ‐hard for under the same condition. We then design a pseudo‐polynomial‐time algorithm for fixed .