This article 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 O(u 4 ), and u is the number of jobs.
Pan et al. (Fri,) studied this question.