Due date assignment scheduling with positional-dependent weights and proportional setup times

Abstract

In this paper, we investigate the single-machine scheduling problem that considers due date assignment and past-sequence-dependent setup times simultaneously. Under common (slack and different) due date assignment, the objective is to find jointly the optimal sequence and optimal due dates to minimize the weighted sum of lateness, number of early and delayed jobs, and due date cost, where the weight only depends on it's position in a sequence (i.e., a position-dependent weight). Optimal properties of the problem are given and then the polynomial time algorithm is proposed to obtain the optimal solution.

Keywords

• scheduling
• positional-dependent weight
• due date assignment
• lateness
• past-sequence-dependent setup times