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

Heuristics for minimizing mean tardiness for m parallel machines

Author

Listed:
  • Johnny C. Ho
  • Yih‐Long Chang

Abstract

The concept of parallel operations has been widely used in manufacturing and data processing. However, not many efficient methods have been proposed to reduce job tardiness. This article proposes an efficient heuristic to minimize the mean tardiness of a set of tasks with known processing times and due dates for single and m parallel machines. For the single‐machine case, the proposed heuristic is compared with the well‐known Wilkerson and Irwin algorithm; for the m parallel machine case, it is compared with an extension of the Wilkerson‐Irwin algorithm. We also introduce a simple dispatching rule, and it is compared with some existing dispatching rules. The comprehensive simulation results show that the proposed heuristic performs better than the Wilkerson‐Irwin algorithm at a significantly reduced computational time.

Suggested Citation

  • Johnny C. Ho & Yih‐Long Chang, 1991. "Heuristics for minimizing mean tardiness for m parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(3), pages 367-381, June.
    • Handle: RePEc:wly:navres:v:38:y:1991:i:3:p:367-381
    DOI: 10.1002/1520-6750(199106)38:33.0.CO;2-I
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(199106)38:33.0.CO;2-I
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(199106)38:33.0.CO;2-I?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. V. Srinivasan, 1971. "A hybrid algorithm for the one machine sequencing problem to minimize total tardiness," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 18(3), pages 317-327, September.
    2. Kenneth R. Baker & James B. Martin, 1974. "An experimental comparison of solution algorithms for the single‐machine tardiness problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 21(1), pages 187-199, March.
    3. Robert McNaughton, 1959. "Scheduling with Deadlines and Loss Functions," Management Science, INFORMS, vol. 6(1), pages 1-12, October.
    4. W. A. Horn, 1974. "Some simple scheduling algorithms," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 21(1), pages 177-185, March.
    5. Michael H. Rothkopf, 1966. "Scheduling Independent Tasks on Parallel Processors," Management Science, INFORMS, vol. 12(5), pages 437-447, January.
    6. Eugene L. Lawler, 1964. "On Scheduling Problems with Deferral Costs," Management Science, INFORMS, vol. 11(2), pages 280-288, November.
    7. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    8. Kenneth R. Baker & Alan G. Merten, 1973. "Scheduling with parallel processors and linear delay costs," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 20(4), pages 793-804, December.
    9. James G. Root, 1965. "Scheduling with Deadlines and Loss Functions on k Parallel Machines," Management Science, INFORMS, vol. 11(3), pages 460-475, January.
    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. Christos Koulamas, 1997. "Decomposition and hybrid simulated annealing heuristics for the parallel‐machine total tardiness problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(1), pages 109-125, February.
    2. Daniel Schubert & André Scholz & Gerhard Wäscher, 2018. "Integrated order picking and vehicle routing with due dates," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1109-1139, October.

    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. 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.
    2. Daniel Kowalczyk & Roel Leus, 2018. "A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 768-782, November.
    3. Christos Koulamas, 1997. "Decomposition and hybrid simulated annealing heuristics for the parallel‐machine total tardiness problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(1), pages 109-125, February.
    4. Akiyoshi Shioura & Natalia V. Shakhlevich & Vitaly A. Strusevich, 2017. "Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 724-736, November.
    5. Christian L. Cesar & Peter G. Jessel, 1992. "Real‐time task scheduling with overheads considered," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 247-264, March.
    6. Lenstra, J. K. & Rinnooy Kan, A. H. G., 1980. "An Introduction To Multiprocessor Scheduling," Econometric Institute Archives 272258, Erasmus University Rotterdam.
    7. Akiyoshi Shioura & Natalia V. Shakhlevich & Vitaly A. Strusevich, 2020. "Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost," Journal of Global Optimization, Springer, vol. 76(3), pages 471-490, March.
    8. Biskup, Dirk & Herrmann, Jan & Gupta, Jatinder N.D., 2008. "Scheduling identical parallel machines to minimize total tardiness," International Journal of Production Economics, Elsevier, vol. 115(1), pages 134-142, September.
    9. Schouten, Jop, 2022. "Cooperation, allocation and strategy in interactive decision-making," Other publications TiSEM d5d41448-8033-4f6b-8ec0-c, Tilburg University, School of Economics and Management.
    10. Robbert Fokkink & Thomas Lidbetter & László A. Végh, 2019. "On Submodular Search and Machine Scheduling," Management Science, INFORMS, vol. 44(4), pages 1431-1449, November.
    11. Hongmin Li & Woonghee T. Huh & Matheus C. Sampaio & Naiping Keng, 2021. "Planning Production and Equipment Qualification under High Process Flexibility," Production and Operations Management, Production and Operations Management Society, vol. 30(10), pages 3369-3390, October.
    12. Mehdi Ghiyasvand, 2015. "Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs," Annals of Operations Research, Springer, vol. 229(1), pages 397-408, June.
    13. Szmerekovsky, Joseph G., 2007. "Single machine scheduling under market uncertainty," European Journal of Operational Research, Elsevier, vol. 177(1), pages 163-175, February.
    14. Schouten, Jop & Saavedra-Nieves, Alejandro & Fiestras-Janeiro, G., 2020. "Sequencing Situations and Games with Non-Linear Cost Functions," Other publications TiSEM 3e1db5c9-0f77-4f91-a075-c, Tilburg University, School of Economics and Management.
    15. Yalaoui, Farouk & Chu, Chengbin, 2002. "Parallel machine scheduling to minimize total tardiness," International Journal of Production Economics, Elsevier, vol. 76(3), pages 265-279, April.
    16. Joseph Y.‐T. Leung & Michael Pinedo, 2004. "A note on scheduling parallel machines subject to breakdown and repair," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(1), pages 60-71, February.
    17. Schouten, Jop & Saavedra-Nieves, Alejandro & Fiestras-Janeiro, G., 2020. "Sequencing Situations and Games with Non-Linear Cost Functions," Discussion Paper 2020-006, Tilburg University, Center for Economic Research.
    18. Schouten, Jop & Saavedra-Nieves, Alejandro & Fiestras-Janeiro, M. Gloria, 2021. "Sequencing situations and games with non-linear cost functions under optimal order consistency," European Journal of Operational Research, Elsevier, vol. 294(2), pages 734-745.
    19. Chen, Jeng-Fung & Wu, Tai-Hsi, 2006. "Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints," Omega, Elsevier, vol. 34(1), pages 81-89, January.
    20. Rubing Chen & Jinjiang Yuan & C.T. Ng & T.C.E. Cheng, 2019. "Single‐machine scheduling with deadlines to minimize the total weighted late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(7), pages 582-595, October.

    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:38:y:1991:i:3:p:367-381. 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.