Scheduling for Minimum Total Loss Using Service Time Distributions

ABSTRACT

An analytic model of a single processor scheduling problem is investigated. The scheduling objective is to minimize the total loss incurred by a finite number of initially available requests when each request has an associated linear loss function. The assumptions of the model are that preemption is allowed with negligible loss of processor time, and that the distribution of actual service times is known for each class of requests. A request is associated with a class by any of its characteristics except its actual service time. A contrived example demonstrates that one reasonable scheduling rule does not always minimize expected total loss. The major results of the paper are the definition of a new scheduling rule based on the known service time distributions, and the proof that expected total loss is always minimized by using this new rule. Brief consideration is given to generalizations of the model in which new requests arrive randomly, and preemption requires a non-negligible amount of processor time.

REFERENCES

• 1: SMITH, W. E. Various optimizers for single stage production. Nay. Res. Logistics Quart. 8, 1 (March 1956), 59-66.
• 2: MCN~UG~TON, R.F. Scheduling with deadlines and loss furtctions. Manag. Sci. 6,1 (Oct. 1959), 1-12.
• 3: GaEENBERGER, M. The priority problem and computer time-sharing. Manag. Sci. 12, 11 (july 1966), 888-906.
• 4: ROTHKOPF, M. Scheduling with random service times. Manag. Sci. i~, 9 (May 1966), 707-713.
• 5: SCHRAGE, L.E. A proof of the optimality of the SRPT discipline. Oper. Res. 16, 3 (May 1968), 687-690.
• 6: SCHRAGE, L.E. Optimal scheduling rules for information processing systems. ICR Quart. Rep. No. 26, U. of Chicago, Chicago, Ill., Aug. 1970.
• 7: CHAZAN, D., KONHEIM, A. G., AND WEISS, B. A note on time-sharing. J. Comb. Theory 5, 4 (Dec. 1968), 344-369.
• 8: KONHEIM, A.G. A note on time-sharing. Rep. No. RC-1804, IBM Corp., Yorktown tteis;hts, New York, April 1967.
• 9: KONHEIM, A. G. A note on time-sharing with preferred customers. Z. Wahrscheinlichkeitslheorie Verw. Geb. 9 (1968), 112-130.
• 10: SEvcItc, K. C. The use of service time distributions in scheduling. Ph.D. diss., Comm. on Information Sciences, U. of Chicago, Sept. 1971.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

General Terms:
Performance, Theory, Verification