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

New Bounds for the Identical Parallel Processor Weighted Flow Time Problem

Author

Listed:
  • Scott Webster

    (School of Business, University of Wisconsin-Madison, Madison, Wisconsin 53706)

Abstract

In 1964, Eastman, Even, and Isaacs (EEI) presented a polynomial time lower bound for the NP-hard problem of scheduling n jobs on m available and identical processors to minimize weighted flow time. A general bound, of which the EEI bound is a special case, is proposed. Four new bounds for the identical processor problem are given. All of the new bounds can be applied to problems with variable processor ready times. The EEI bound is limited to problems where all processors are initially available at the same time. Two of the four new bounds are shown to dominate the EEI bound. The two other bounds are found to be effective for a particular problem class. Two polynomial time lower bounds for problems with nonidentical processors are introduced. One bound is applicable to the uniform processor problem, the other bound can be applied to the general processor problem. No bounds have previously been proposed for these problems.

Suggested Citation

  • Scott Webster, 1992. "New Bounds for the Identical Parallel Processor Weighted Flow Time Problem," Management Science, INFORMS, vol. 38(1), pages 124-136, January.
    • Handle: RePEc:inm:ormnsc:v:38:y:1992:i:1:p:124-136
    DOI: 10.1287/mnsc.38.1.124
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.38.1.124
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.38.1.124?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. Zhi-Long Chen & Warren B. Powell, 1999. "Solving Parallel Machine Scheduling Problems by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 78-94, February.
    2. Rabia Nessah & Chengbin Chu, 2010. "Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods," Annals of Operations Research, Springer, vol. 181(1), pages 359-375, December.
    3. Dunstall, Simon & Wirth, Andrew, 2005. "A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines," European Journal of Operational Research, Elsevier, vol. 167(2), pages 283-296, December.
    4. J. M. van den Akker & J. A. Hoogeveen & S. L. van de Velde, 1999. "Parallel Machine Scheduling by Column Generation," Operations Research, INFORMS, vol. 47(6), pages 862-872, December.
    5. Xiangtong Qi, 2005. "A logistics scheduling model: Inventory cost reduction by batching," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 312-320, June.
    6. Arthur Kramer & Anand Subramanian, 2019. "A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems," Journal of Scheduling, Springer, vol. 22(1), pages 21-57, February.
    7. 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.
    8. Webster, S. T., 1996. "A general lower bound for the makespan problem," European Journal of Operational Research, Elsevier, vol. 89(3), pages 516-524, March.
    9. Webster, Scott, 1995. "Weighted flow time bounds for scheduling identical processors," European Journal of Operational Research, Elsevier, vol. 80(1), pages 103-111, January.

    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:38:y:1992:i:1:p:124-136. 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.