Skip to main content
SpringerLink
Log in

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

  • Theoretical Paper
  • Published:
Journal of the Operational Research Society

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 3) 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4

Similar content being viewed by others

References

  • Cheng TCE, Ding Q and Lin BMT (2004). A concise survey of scheduling with time-dependent processing times. Eur J Opl Res 152: 1–13.

    Article  Google Scholar 

  • 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 139: 1–25.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Mosheiov G and Oron D (2004). Due-window assignment with unit processing-time jobs. Naval Res Logist 51: 1005–1017.

    Article  Google Scholar 

  • Mosheiov G and Sidney J (2003). Scheduling with general job-dependent learning curves. Eur J Opl Res 147: 665–670.

    Article  Google Scholar 

  • Panwalkar SS, Smith MS and Seidmann A (1982). Common due-date assignment to minimize total penalty for the one machine scheduling problem. Opns Res 30: 391–399.

    Article  Google Scholar 

  • Weng MX and Ventura JA (1994). Scheduling about a large common due-date with tolerance to minimized mean absolute deviation of completion times. Naval Res Logist 41: 843–851.

    Article  Google Scholar 

  • Weng MX and Ventura JA (1996). A note on ‘common due-window scheduling’. Prod Opl Mngt 5: 194–200.

    Article  Google Scholar 

Download references

Acknowledgements

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

Author information

Authors and Affiliations

  1. The Hebrew University, Jerusalem, Israel

    G Mosheiov & A Sarig

Authors
  1. G Mosheiov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A Sarig
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mosheiov, G., Sarig, A. A due-window assignment problem with position-dependent processing times. J Oper Res Soc 59, 997–1003 (2008). https://doi.org/10.1057/palgrave.jors.2602439

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/palgrave.jors.2602439

Keywords

Search

Navigation