SCHEDULING INDEPENDENT TASKS ON ONE OR MORE PROCESSORS,
Abstract
The problem concerns the scheduling m independent, immediately available tasks on n processors. Each task has a service time and a waiting cost rate that is a function of time. There are no feasibility restrictions on the order in which the tasks are to be processed. The problem is related to the job shop scheduling problem and the problem of optimally assigning priorities in a queueing system. It is shown that when the cost rate is equal to the linear waiting costs with continuous discounting rate and there is a single processor, waiting costs are minimized by sequencing the tasks in decreasing order. A dynamic programming algorithm has been developed for a wide class of multiprocessor scheduling problems. Linear waiting costs (with or without discounting), arbitrary processor use costs, and certain other costs are considered. In certain cases, the service time of a task may be a function of the processor that performs it. Several algorithms are presented for scheduling tasks with absolute deadlines on one or more processors. For certain classes of problems, the unprofitability of splitting tasks in time or between processors is proved. Scheduling when service times and cost rates are known only stochastically is discussed. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1964
- Accession Number
- AD0428857
Entities
People
- Michael H. Rothkopf
Organizations
- Massachusetts Institute of Technology