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

Parallel Machine Scheduling: Processing Rates Dependent on Number of Jobs in Operation

Author

Listed:
  • Moshe Dror

    (Department of Industrial Engineering and Management, Ben Gurion University of the Negev, Beer Sheva, Israel and INRS---Telecommunications, Verdun, Quebec, Canada H3E 1H6)

  • Helman I. Stern

    (Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720)

  • Jan Karel Lenstra

    (Center for Mathematics and Computer Science, Amsterdam, The Netherlands)

Abstract

We treat the class of n job - m machine scheduling problems with job processing times dependent on the number of jobs being simultaneously processed in the system at any point in time. Such systems occur when jobs are assigned to multiple parallel processors driven by a common power source. In situations typical of hydraulic and pneumatic power sources the level of power delivered to each processor is inversely proportional to the number of processors simultaneously at work. Aside from the variable processing rate assumptions, the remaining assumptions on the structure of the system conform to those of the standard identical parallel processor problem without job preemption. Although the standard n job - m machine problem is NP-hard with respect to a makespan measure, this is not the case when our seemingly complicating variable processing rate function, typical of hydraulic power sources, is included. In this case our main results are exceedingly simple. The makespan is found to be independent of the job-machine assignment, and the flowtime is minimized using one out of m processors. When other job processing rate functions or constant switch-over times are considered, then solving the problem becomes increasingly difficult, and the use of multiple processors is recommended. This paper concludes with a description of a real-world problem (scheduling the refueling of navy boats) which motivated this research.

Suggested Citation

  • Moshe Dror & Helman I. Stern & Jan Karel Lenstra, 1987. "Parallel Machine Scheduling: Processing Rates Dependent on Number of Jobs in Operation," Management Science, INFORMS, vol. 33(8), pages 1001-1009, August.
    • Handle: RePEc:inm:ormnsc:v:33:y:1987:i:8:p:1001-1009
    DOI: 10.1287/mnsc.33.8.1001
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.33.8.1001
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.33.8.1001?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. Joanna Józefowska & Mariusz Nowak & Rafał Różycki & Grzegorz Waligóra, 2022. "Survey on Optimization Models for Energy-Efficient Computing Systems," Energies, MDPI, vol. 15(22), pages 1-20, November.
    2. E. Wagneur & C. Sriskandarajah, 1993. "The two‐machine permutation flow shop with state‐dependent processing times," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(5), pages 697-717, August.
    3. Fündeling, C.-U. & Trautmann, N., 2010. "A priority-rule method for project scheduling with work-content constraints," European Journal of Operational Research, Elsevier, vol. 203(3), pages 568-574, June.
    4. Yanıkoğlu, İhsan & Yavuz, Tonguc, 2022. "Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 301(3), pages 875-895.
    5. Gorczyca, Mateusz & Janiak, Adam, 2010. "Resource level minimization in the discrete-continuous scheduling," European Journal of Operational Research, Elsevier, vol. 203(1), pages 32-41, May.
    6. Bahram Alidaee & Haibo Wang & R. Bryan Kethley & Frank Landram, 2019. "A unified view of parallel machine scheduling with interdependent processing rates," Journal of Scheduling, Springer, vol. 22(5), pages 499-515, October.
    7. Jozefowska, Joanna & Weglarz, Jan, 1998. "On a methodology for discrete-continuous scheduling," European Journal of Operational Research, Elsevier, vol. 107(2), pages 338-353, June.

    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:33:y:1987:i:8:p:1001-1009. 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.