IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v25y1979i12p1208-1216.html
   My bibliography  Save this article

Evaluation of a Heuristic for Scheduling Independent Jobs on Parallel Identical Processors

Author

Listed:
  • Ali Dogramaci

    (Columbia University)

  • Julius Surkis

    (Rutgers University)

Abstract

In this paper we consider the problem of scheduling "n" independent fades on "m" parallel processors. Each job consists of a single operation with a specific processing time and due date. The processors are identical and the operation of the system is non-preemptive. The objective is to schedule the jobs in such a way that the total tardiness of the n jobs is as small as possible. For the case of a single processor with n jobs, there exists algorithms which provide optimal solutions. On the other hand currently available optimal scheduling algorithms for multiple processors can handle only small problems. Therefore, practitioners are forced to use heuristic methods to schedule their jobs on multiple processors. This raises questions of the following nature: "Are we scheduling our jobs reasonably well? Are there other schedules with which our total tardiness can be lowered substantially? How far off might the heuristic solution be, from the optimal solution?" The study reported in this paper focuses on a heuristic which can handle reasonably large problems, and yet can be simply and economically implemented. Experiments are conducted by establishing lower bounds for the optimal total tardiness of randomly generated scheduling problems. These lower bounds are then compared with the total tardiness obtained from the heuristic. It is found that the heuristic under study provides solutions which are quite close to the optimal ones. The experiments include 560 randomly generated problems that range from "loose" to "tight" in due dates, with varying numbers of jobs and processors. A nonparametric statistical analysis is presented to generalize the results.

Suggested Citation

  • Ali Dogramaci & Julius Surkis, 1979. "Evaluation of a Heuristic for Scheduling Independent Jobs on Parallel Identical Processors," Management Science, INFORMS, vol. 25(12), pages 1208-1216, December.
    • Handle: RePEc:inm:ormnsc:v:25:y:1979:i:12:p:1208-1216
    DOI: 10.1287/mnsc.25.12.1208
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.25.12.1208
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.25.12.1208?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
    ---><---

    Citations

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


    Cited by:

    1. 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.
    2. S-O Shim & Y-D Kim, 2007. "Minimizing total tardiness in an unrelated parallel-machine scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 346-354, March.
    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. Shim, Sang-Oh & Kim, Yeong-Dae, 2007. "Scheduling on parallel identical machines to minimize total tardiness," European Journal of Operational Research, Elsevier, vol. 177(1), pages 135-146, February.
    5. 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.
    6. 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.
    7. Guinet, Alain, 2001. "Multi-site planning: A transshipment problem," International Journal of Production Economics, Elsevier, vol. 74(1-3), pages 21-32, December.
    8. Weng, Michael X. & Lu, John & Ren, Haiying, 2001. "Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective," International Journal of Production Economics, Elsevier, vol. 70(3), pages 215-226, April.
    9. Azizoglu, Meral & Kirca, Omer, 1998. "Tardiness minimization on parallel machines," International Journal of Production Economics, Elsevier, vol. 55(2), pages 163-168, July.

    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:ormnsc:v:25:y:1979:i:12:p:1208-1216. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.