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 4)) solution procedure.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Gordon V, Proth JM and Chu C (2002). A survey of the state-of-the-art of common due-date assignment and scheduling research . Eur J Opl Res 135: 1–25.
Hall NG and Posner ME (1991). Earliness-tardiness scheduling problems. I: Weighted deviation of completion times about a common due date . Opl Res 39: 836–846.
Janiak A, Kovalyov MY and Marek M (2007). Soft due window assignment and scheduling on parallel machines . IEEE T Syst Man Cyb :A 37: 614–620.
Janiak A and Winczaszek M (2004). A single processor scheduling problem with a common due window assignment. In: Fleuren H, den Hertog D and Kort P (eds), Operations Research Proceedings, pp. 213–220.
Janiak A and Winczaszek M (2006). Common due window assignment in parallel processor scheduling problem with nonlinear penalty functions . Lect Notes Comput Sci 3911: 132–139.
Liman SD, Panwalkar SS and Thongmee S (1996). Determination of common due window location in a single machine scheduling problem . Eur J Opl Res 93: 68–74.
Liman SD, Panwalkar SS and Thongmee S (1998). Common due window size and location determination in a single machine scheduling problem . J Opl Res Soc 49: 1007–1010.
Mosheiov G and Oron D (2004). Due-window assignment with unit processing-time jobs . Nav Res Log 51: 1005–1017.
Mosheiov G and Yovel U (2006). Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs . Eur J Opl Res 172: 528–544.
Weng MX and Ventura JA (1996). A note on ‘common due-window scheduling' . Prod Opl Mngt 5: 194–200.
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.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mosheiov, G., Sarig, A. A note: a due-window assignment problem on parallel identical machines. J Oper Res Soc 62, 238–241 (2011). https://doi.org/10.1057/jors.2009.179
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2009.179