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

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.