An improved algorithm for due-window assignment on parallel identical machines with unit-time jobs

• We solve a due-window assignment problem with unit time jobs on parallel identical machines.
• Four cost components are assumed: earliness, tardiness, due-window start time, and due-window size.
• The solution procedure consists of solving 9 assignment problems of size O(n×n)O(n×n).
• The proposed algorithm improves significantly a recent published solution.

We study a due-window assignment problem on parallel identical machines, with unit processing time jobs. The objective function is minimum total cost, consisting of earliness, tardiness, due-window starting time and due-window size. A recent paper (Janiak et al., 2012) introduced a solution algorithm requiring O(n5/m2)O(n5/m2) time, where n is the number of jobs, and m   is the number of machines. We propose a significantly faster procedure, requiring O(n3)O(n3) only.