IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v49y2002i4p422-431.html
   My bibliography  Save this article

A dual criteria sequencing problem with earliness and tardiness penalties

Author

Listed:
  • Joseph Y.‐T. Leung

Abstract

We consider the problem of sequencing n jobs on a single machine, with each job having a processing time and a common due date. The common due date is assumed to be so large that all jobs can complete by the due date. It is known that there is an O(n log n)‐time algorithm for finding a schedule with minimum total earliness and tardiness. In this article, we consider finding a schedule with dual criteria. The primary goal is to minimize the total earliness and tardiness. The secondary goals are to minimize: (1) the maximum earliness and tardiness; (2) the sum of the maximum of the squares of earliness and tardiness; (3) the sum of the squares of earliness and tardiness. For the first two criteria, we show that the problems are NP‐hard and we give a fully polynomial time approximation scheme for both of them. For the last two criteria, we show that the ratio of the worst schedule versus the best schedule is no more than ${3\over 2}$. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 422–431, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10020

Suggested Citation

  • Joseph Y.‐T. Leung, 2002. "A dual criteria sequencing problem with earliness and tardiness penalties," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(4), pages 422-431, June.
    • Handle: RePEc:wly:navres:v:49:y:2002:i:4:p:422-431
    DOI: 10.1002/nav.10020
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.10020
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.10020?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. P. S. Sundararaghavan & Mesbah U. Ahmed, 1984. "Minimizing the sum of absolute lateness in single‐machine and multimachine scheduling," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 31(2), pages 325-333, June.
    2. Prabuddha De & Jay B. Ghosh & Charles E. Wells, 1989. "Note---A Note on the Minimization of Mean Squared Deviation of Completion Times About a Common Due Date," Management Science, INFORMS, vol. 35(9), pages 1143-1147, September.
    3. John J. Kanet, 1981. "Minimizing the average deviation of job completion times about a common due date," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 28(4), pages 643-651, December.
    4. Sankaran Lakshminarayan & Ram Lakshmanan & Robert L. Papineau & Rene Rochette, 1978. "Technical Note—Optimal Single-Machine Scheduling with Earliness and Tardiness Penalties," Operations Research, INFORMS, vol. 26(6), pages 1079-1082, December.
    5. Gupta, Sushil K. & Sen, Tapan, 1983. "Minimizing a quadratic function of job lateness on a single machine," Engineering Costs and Production Economics, Elsevier, vol. 7(3), pages 187-194, September.
    6. Uttarayan Bagchi & Robert S. Sullivan & Yih-Long Chang, 1987. "Minimizing Mean Squared Deviation of Completion Times About a Common Due Date," Management Science, INFORMS, vol. 33(7), pages 894-906, July.
    7. Kenneth R. Baker & Gary D. Scudder, 1990. "Sequencing with Earliness and Tardiness Penalties: A Review," Operations Research, INFORMS, vol. 38(1), pages 22-36, February.
    8. Jeffrey B. Sidney, 1977. "Optimal Single-Machine Scheduling with Earliness and Tardiness Penalties," Operations Research, INFORMS, vol. 25(1), pages 62-69, February.
    9. Hamilton Emmons, 1987. "Scheduling to a common due date on parallel uniform processors," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(6), pages 803-810, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sridharan, V. & Zhou, Z., 1996. "A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems," European Journal of Operational Research, Elsevier, vol. 94(2), pages 292-301, October.
    2. Gordon, Valery & Proth, Jean-Marie & Chu, Chengbin, 2002. "A survey of the state-of-the-art of common due date assignment and scheduling research," European Journal of Operational Research, Elsevier, vol. 139(1), pages 1-25, May.
    3. Yeong‐Dae Kim & Candace Arai Yano, 1994. "Minimizing mean tardiness and earliness in single‐machine scheduling problems with unequal due dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(7), pages 913-933, December.
    4. Srirangacharyulu, B. & Srinivasan, G., 2013. "An exact algorithm to minimize mean squared deviation of job completion times about a common due date," European Journal of Operational Research, Elsevier, vol. 231(3), pages 547-556.
    5. Enrique Gerstl & Gur Mosheiov, 2014. "Single machine just‐in‐time scheduling problems with two competing agents," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(1), pages 1-16, February.
    6. Chung‐Lun Li & T. C. E. Cheng, 1994. "The parallel machine min‐max weighted absolute lateness scheduling problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(1), pages 33-46, February.
    7. Bernard Dickman & Yonah Wilamowsky & Sheldon Epstein, 2001. "Multiple common due dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(4), pages 293-298, June.
    8. Uttarayan Bagchi & Yih‐Long Chang & Robert S. Sullivan, 1987. "Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(5), pages 739-751, October.
    9. John J. Kanet & V. Sridharan, 2000. "Scheduling with Inserted Idle Time: Problem Taxonomy and Literature Review," Operations Research, INFORMS, vol. 48(1), pages 99-110, February.
    10. J. Steve Davis & John J. Kanet, 1993. "Single‐machine scheduling with early and tardy completion costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(1), pages 85-101, February.
    11. Ventura, Jose A. & Radhakrishnan, Sanjay, 2003. "Single machine scheduling with symmetric earliness and tardiness penalties," European Journal of Operational Research, Elsevier, vol. 144(3), pages 598-612, February.
    12. Kerem Bülbül & Safia Kedad-Sidhoum & Halil Şen, 2019. "Single-machine common due date total earliness/tardiness scheduling with machine unavailability," Journal of Scheduling, Springer, vol. 22(5), pages 543-565, October.
    13. Michael C. Ferris & Milan Vlach, 1992. "Scheduling with earliness and tardiness penalties," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 229-245, March.
    14. G A Álvarez-Pérez & J L González-Velarde & J W Fowler, 2009. "Crossdocking— Just in Time scheduling: an alternative solution approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(4), pages 554-564, April.
    15. Adamopoulos, G. I. & Pappis, C. P., 1996. "Scheduling jobs with different, job-dependent earliness and tardiness penalties using the SLK method," European Journal of Operational Research, Elsevier, vol. 88(2), pages 336-344, January.
    16. Weng, Xiaohua & Ventura, Jose A., 1996. "Scheduling about a given common due date to minimize mean squared deviation of completion times," European Journal of Operational Research, Elsevier, vol. 88(2), pages 328-335, January.
    17. Seo, Jong Hwa & Kim, Chae-Bogk & Lee, Dong Hoon, 2001. "Minimizing mean squared deviation of completion times with maximum tardiness constraint," European Journal of Operational Research, Elsevier, vol. 129(1), pages 95-104, February.
    18. Ng, C. T. & Cai, X. & Cheng, T. C. E., 1996. "A tight lower bound for the completion time variance problem," European Journal of Operational Research, Elsevier, vol. 92(1), pages 211-213, July.
    19. Lemos, R.F. & Ronconi, D.P., 2015. "Heuristics for the stochastic single-machine problem with E/T costs," International Journal of Production Economics, Elsevier, vol. 168(C), pages 131-142.
    20. Y. P. Aneja & S. N. Kabadi & A. Nagar, 1998. "Minimizing weighted mean absolute deviation of flow times in single machine systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(3), pages 297-311, April.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:49:y:2002:i:4:p:422-431. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.