Dynamic Programming for Proportionate Flow-Shop Scheduling with Due-Date Assignment

This paper examines proportionate flow-shop scheduling with general earliness/tardiness costs under two due-date assignment models: the common and slack models. The objective is to determine the optimal job sequence and due dates to minimize a total penalty function that includes earliness and tardiness penalties, the number of early and delayed jobs, and the due-date assignment cost. Several optimal structural properties are derived, and two polynomial-time dynamic programming (DP) algorithms are proposed to solve the problems, with a time complexity of [Formula: see text], and [Formula: see text] is the number of jobs.