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

Scheduling of parallel processors: A posterior bound on LPT sequencing and a two‐step algorithm

Author

Listed:
  • James D. Blocher
  • Suresh Chand

Abstract

This article considers the problem of scheduling parallel processors to minimize the makespan. The article makes two key contributions: (1) It develops a new lower bound on the makespan for an optimal schedule, and (2) it proposes an efficient two‐step algorithm to find schedules of any desired accuracy, or percent above optimal. In addition, a posterior bound on LPT (longest processing time) sequencing is developed in the article. It is proved that this bound dominates the previously reported bounds on LPT sequencing.

Suggested Citation

  • James D. Blocher & Suresh Chand, 1991. "Scheduling of parallel processors: A posterior bound on LPT sequencing and a two‐step algorithm," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(2), pages 273-287, April.
    • Handle: RePEc:wly:navres:v:38:y:1991:i:2:p:273-287
    DOI: 10.1002/1520-6750(199104)38:23.0.CO;2-A
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(199104)38:23.0.CO;2-A
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(199104)38:23.0.CO;2-A?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. Blazewicz, J. & Finke, G. & Haupt, R. & Schmidt, G., 1988. "New trends in machine scheduling," European Journal of Operational Research, Elsevier, vol. 37(3), pages 303-317, December.
    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. Johnny C. Ho & Ivar Massabò & Giuseppe Paletta & Alex J. Ruiz-Torres, 2019. "A note on posterior tight worst-case bounds for longest processing time schedules," 4OR, Springer, vol. 17(1), pages 97-107, March.
    2. James D. Blocher & Dilip Chhajed, 1996. "The customer order lead‐time problem on parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(5), pages 629-654, August.
    3. Johnny C. Ho & Johnny S. Wong, 1995. "Makespan minimization for m parallel identical processors," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(6), pages 935-948, September.

    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. An, Youjun & Chen, Xiaohui & Hu, Jiawen & Zhang, Lin & Li, Yinghe & Jiang, Junwei, 2022. "Joint optimization of preventive maintenance and production rescheduling with new machine insertion and processing speed selection," Reliability Engineering and System Safety, Elsevier, vol. 220(C).
    2. Konak, Abdullah & Kulturel-Konak, Sadan & Azizoglu, Meral, 2008. "Minimizing the number of tool switching instants in Flexible Manufacturing Systems," International Journal of Production Economics, Elsevier, vol. 116(2), pages 298-307, December.
    3. Crama, Yves, 1997. "Combinatorial optimization models for production scheduling in automated manufacturing systems," European Journal of Operational Research, Elsevier, vol. 99(1), pages 136-153, May.
    4. Liu, Jiyin & MacCarthy, B. L., 1997. "A global MILP model for FMS scheduling," European Journal of Operational Research, Elsevier, vol. 100(3), pages 441-453, August.
    5. Yingling, Jon C. & Goh, Chon-Huat & Ganguli, Rajive, 1999. "Analysis of the twisting department at Superior Cable Corporation: A case study," European Journal of Operational Research, Elsevier, vol. 115(1), pages 19-35, May.
    6. Shewchuk, John P. & Chang, T. C., 1995. "Resource-constrained job scheduling with recyclable resources," European Journal of Operational Research, Elsevier, vol. 81(2), pages 364-375, March.
    7. Ecker, K. H. & Gupta, J. N. D., 2005. "Scheduling tasks on a flexible manufacturing machine to minimize tool change delays," European Journal of Operational Research, Elsevier, vol. 164(3), pages 627-638, August.
    8. Olivier Guyon & Pierre Lemaire & Éric Pinson & David Rivreau, 2014. "Solving an integrated job-shop problem with human resource constraints," Annals of Operations Research, Springer, vol. 213(1), pages 147-171, February.

    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:2:p:273-287. 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.