IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v46y1998i3-supplement-3ps120-s134.html
   My bibliography  Save this article

On the Meaningfulness of Optimal Solutions to Scheduling Problems: Can an Optimal Solution be Nonoptimal?

Author

Listed:
  • N. V. R. Mahadev

    (Northeastern University, Boston, Massachusetts)

  • Aleksandar Pekeč

    (University of Aarhus, Aarhus, Denmark)

  • Fred S. Roberts

    (Rutgers University, New Brunswick, New Jersey)

Abstract

We consider the problem of finding an optimal schedule for jobs on a single machine when there are penalties for both tardy and early arrivals. We point out that if attention is paid to how these penalties are measured, then a change of scale of measurement might lead to the anomalous situation where a schedule is optimal if these parameters are measured in one way, but not if they are measured in a different way that seems equally acceptable. In particular, we note that if the penalties measure utilities or disutilities, or loss of goodwill or customer satisfaction, then these kinds of anomalies can occur, for instance if we change both unit and zero point in scales measuring these penalties. We investigate situations where problems of these sorts arise for four specific penalty functions under a variety of different assumptions. The results of the paper have implications far beyond the specific scheduling problems we consider, and suggest that considerations of scale of measurement should enter into analysis of conclusions of optimality both in scheduling problems and throughout combinatorial optimization.

Suggested Citation

  • N. V. R. Mahadev & Aleksandar Pekeč & Fred S. Roberts, 1998. "On the Meaningfulness of Optimal Solutions to Scheduling Problems: Can an Optimal Solution be Nonoptimal?," Operations Research, INFORMS, vol. 46(3-supplem), pages 120-134, June.
    • Handle: RePEc:inm:oropre:v:46:y:1998:i:3-supplement-3:p:s120-s134
    DOI: 10.1287/opre.46.3.S120
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.46.3.S120
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.46.3.S120?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. Jeffrey B. Sidney, 1977. "Optimal Single-Machine Scheduling with Earliness and Tardiness Penalties," Operations Research, INFORMS, vol. 25(1), pages 62-69, February.
    2. Nicholas G. Hall & Marc E. Posner, 1991. "Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date," Operations Research, INFORMS, vol. 39(5), pages 836-846, October.
    3. Nicholas G. Hall & Wieslaw Kubiak & Suresh P. Sethi, 1991. "Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date," Operations Research, INFORMS, vol. 39(5), pages 847-856, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yong He & Zhiyi Tan, 2002. "Ordinal On-Line Scheduling for Maximizing the Minimum Machine Completion Time," Journal of Combinatorial Optimization, Springer, vol. 6(2), pages 199-206, June.
    2. Leah Epstein, 2023. "Parallel solutions for ordinal scheduling with a small number of machines," Journal of Combinatorial Optimization, Springer, vol. 46(1), pages 1-24, August.

    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. Feng Li & Zhi-Long Chen & Zhi-Long Chen, 2017. "Integrated Production, Inventory and Delivery Problems: Complexity and Algorithms," INFORMS Journal on Computing, INFORMS, vol. 29(2), pages 232-250, May.
    2. Wang, Julong & Liu, Zhixue & Li, Feng, 2024. "Integrated production and transportation scheduling problem under nonlinear cost structures," European Journal of Operational Research, Elsevier, vol. 313(3), pages 883-904.
    3. 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.
    4. 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.
    5. Baker, Kenneth R., 2014. "Minimizing earliness and tardiness costs in stochastic scheduling," European Journal of Operational Research, Elsevier, vol. 236(2), pages 445-452.
    6. X. Cai & F. S. Tu, 1996. "Scheduling jobs with random processing times on a single machine subject to stochastic breakdowns to minimize early‐tardy penalties," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(8), pages 1127-1146, December.
    7. Li, Y. & Ip, W. H. & Wang, D. W., 1998. "Genetic algorithm approach to earliness and tardiness production scheduling and planning problem," International Journal of Production Economics, Elsevier, vol. 54(1), pages 65-76, January.
    8. Philip Kaminsky & Onur Kaya, 2008. "Scheduling and due‐date quotation in a make‐to‐order supply chain," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(5), pages 444-458, August.
    9. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    10. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    11. Ali Kordmostafapour & Javad Rezaeian & Iraj Mahdavi & Mahdi Yar Farjad, 2022. "Scheduling unrelated parallel machine problem with multi-mode processing times and batch delivery cost," OPSEARCH, Springer;Operational Research Society of India, vol. 59(4), pages 1438-1470, December.
    12. Feifeng Zheng & E. Zhang & Yinfeng Xu & Wei-Chiang Hong, 2014. "Competitive analysis for make-to-order scheduling with reliable lead time quotation," Journal of Combinatorial Optimization, Springer, vol. 27(1), pages 182-198, January.
    13. Chung‐Lun Li & Edward C. Sewell & T. C. E. Cheng, 1995. "Scheduling to minimize release‐time resource consumption and tardiness penalties," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(6), pages 949-966, September.
    14. Cai, X. & Lum, V. Y. S. & Chan, J. M. T., 1997. "Scheduling about a common due date with kob-dependent asymmetric earliness and tardiness penalties," European Journal of Operational Research, Elsevier, vol. 98(1), pages 154-168, April.
    15. Yuan, Jinjiang, 1996. "A note on the complexity of single-machine scheduling with a common due date, earliness-tardiness, and batch delivery costs," European Journal of Operational Research, Elsevier, vol. 94(1), pages 203-205, October.
    16. 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.
    17. Mosheiov, Gur & Shadmon, Michal, 2001. "Minmax earliness-tardiness costs with unit processing time jobs," European Journal of Operational Research, Elsevier, vol. 130(3), pages 638-652, May.
    18. Ramon Alvarez-Valdes & Enric Crespo & Jose Tamarit & Fulgencia Villa, 2012. "Minimizing weighted earliness–tardiness on a single machine with a common due date using quadratic models," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 20(3), pages 754-767, October.
    19. Hendel, Yann & Sourd, Francis, 2006. "Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem," European Journal of Operational Research, Elsevier, vol. 173(1), pages 108-119, August.
    20. Byung-Cheon Choi & Myoung-Ju Park, 2018. "Just-In-Time Scheduling with Generalized Due Dates and Identical Due Date Intervals," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(06), pages 1-13, December.

    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:inm:oropre:v:46:y:1998:i:3-supplement-3:p:s120-s134. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.