Single-machine due-date assignment scheduling with generalized earliness-tardiness penalties including proportional setup times

This paper studies the single-machine due-date assignment problem with past-sequence-dependent setup times (denoted by STpsd). Under common due-date (denoted by CON-DD) assignment, slack due-date (denoted by SLK-DD) and different due-date (denoted by DIF-DD) assignment, the objective function is to minimize the linear weighted sum of earliness-tardiness, number of early and delayed jobs, and due-date cost. Optimal properties of the problem is given and then prove that the problem can be solved in polynomial time. Three extensions to the problem are also offered by assuming position-dependent, time-dependent, position-and-time-dependent processing times.

Automated summary

This paper investigates the single-machine due-date assignment problem with past-sequence-dependent setup times, proposing optimal solutions under different due-date assignment scenarios. The problem is proven to be solvable in polynomial time by minimizing a linear weighted sum. Furthermore, three extensions are provided by considering various dependencies in processing times.