Maximizing the weighted number of Just-In-Time jobs in a proportionate flow shop with job rejection

Scheduling in proportionate flow shop environments is a fundamental challenge in manufacturing and service systems, where Just-in-Time performance plays a critical role in reducing inventory and improving responsiveness. This study is motivated by practical constraints such as limited storage capacity between machines and outsourcing costs, which require selective job acceptance and rejection. We first examine the setting with unlimited intermediate storage and then address the more restrictive no-wait environment. In both cases, the objective is to maximize the weighted number of Just-in-Time jobs subject to an upper bound on the total rejection cost. Since these problems are NP-hard even in the single-machine case, we develop pseudo-polynomial dynamic programming algorithms that yield exact solutions. Our proposed methods provide a tractable approach for medium-sized instances. A comprehensive computational study demonstrates that the algorithms consistently deliver high-quality solutions within reasonable computation times. These findings confirm the effectiveness of dynamic programming for Just-in-Time scheduling with job rejection in proportionate flow shops, offering valuable insights for future research on scalable optimization techniques.