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

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4037586
Language Label Description Also known as
default for all languages
No label defined
    English
    Parallel Machine Scheduling: Processing Rates Dependent on Number of Jobs in Operation
    scientific article; zbMATH DE number 4037586

      Statements

      Parallel Machine Scheduling: Processing Rates Dependent on Number of Jobs in Operation (English)
      0 references
      0 references
      0 references
      0 references
      1987
      0 references
      logistics
      0 references
      n job - m machine scheduling
      0 references
      multiple parallel processors
      0 references
      common power source
      0 references
      makespan
      0 references
      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.
      0 references

      Identifiers