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 .