A note: a due-window assignment problem on parallel identical machines

Abstract

We solve a due-window assignment problem on parallel identical machines. In addition to the standard objective of finding the optimal job schedule, in due-window assignment problems one has to assign a time interval during which goods are delivered to customers with no cost. Jobs scheduled prior to or after the due-window are penalized according to their earliness/tardiness value. We assume that jobs have identical processing times, but may have job-dependent earliness and tardiness costs (eg, due to possible different destinations). We show that the problem can be reduced to a non-standard asymmetric assignment problem, and introduce an efficient (O(n⁴)) solution procedure.

Keywords:

• scheduling
• parallel machines
• earliness–tardiness
• due-window
• assignment problem

Acknowledgements

The first author is the Charles Rosen Professor of Management, The School of Business Administration, The Hebrew University. The paper was supported in past by the Recanati Fund of the School of Business Administration, The Hebrew University, Jerusalem, Israel.