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

Moshe Dror, Helman I. Stern and Jan Karel Lenstra
Additional contact information
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

Management Science, 1987, vol. 33, issue 8, 1001-1009

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.

Keywords: production scheduling; military: logistics; facilities/equipment planning: design (search for similar items in EconPapers)
Date: 1987
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.33.8.1001 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:33:y:1987:i:8:p:1001-1009

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().