A due-window assignment problem with position-dependent processing times

Abstract

We extend a classical single-machine due-window assignment problem to the case of position-dependent processing times. In addition to the standard job scheduling decisions, one has to assign a time interval (due-window), such that jobs completed within this interval are assumed to be on time and not penalized. The cost components are: total earliness, total tardiness and due-window location and size. We introduce an O(n³) solution algorithm, where n is the number of jobs. We also investigate several special cases, and examine numerically the sensitivity of the solution (schedule and due-window) to the different cost parameters.

Keywords:

• scheduling
• due-window
• earliness–tardiness
• position-dependent processing times

Acknowledgements

This paper was supported in part by the Recanati Fund of the School of Business Administration, The Hebrew University, Jerusalem, Israel.