Allocation of tasks to specialized processors: A planning approach. (English) Zbl 0970.90042
Summary: This paper addresses the problem of scheduling randomly arriving tasks of different types at a diversified service system. Servers at such a system differ in that each may specialize in one task type, but can also perform others perhaps less rapidly and adequately than does a specialist. We consider the issue of how much redirection of tasks from specialists to non-specialists may be desirable in such a system and propose a static model in which tasks are randomly assigned to servers. Two scheduling strategies for individual servers are also considered: one in which each server performs the tasks assigned to him or her in order of their arrival and the second in which each server schedules his or her workload optimally. The problems for finding the best random assignment probabilities are formulated as mathematical programs. Results from a numerical example provide information that is both informative and useful in decision-making.
Software:
GAMSReferences:
| [1] | Berman, O.; Chiu, S. S.; Larson, R. C.; Odoni, A. R.; Batta, R., Location of mobile units in a stochastic environment, (Mirchandani, P. B.; Francis, R. L., Discrete Location Theory (1990), Wiley: Wiley New York), 503-549 · Zbl 0738.90043 |
| [2] | Brooke, A., Kendrick, D., Meeraus, A., 1992. GAMS: A User’s Guide, Release 2.25, The Scientific Press, South San Francisco, CA; Brooke, A., Kendrick, D., Meeraus, A., 1992. GAMS: A User’s Guide, Release 2.25, The Scientific Press, South San Francisco, CA |
| [3] | Eager, D. L.; Lazowska, E. D.; Zahorjan, J., Adaptive load sharing in homogeneous distributed systems, IEEE Transactions on Software Engineering, 12, 662-675 (1986) |
| [4] | Eager, D. L.; Lazowska, E. D.; Zahorjan, J., A comparison of receiver-initiated and sender-initiated adaptive load sharing, Performance Evaluation, 6, 53-68 (1986) |
| [5] | Fife, D. W., Scheduling with random arrivals and linear loss functions, Management Science, 11, 3, 429-437 (1965) · Zbl 0136.14706 |
| [6] | Gaver, D. P.; Morrison, J. A.; Silveira, R., Service-adaptive multitype repairman problems, SIAM Journal on Applied Mathematics, 53, 2, 459-470 (1993) · Zbl 0779.90033 |
| [7] | Gelenbe, E.; Mitrani, I., Analysis and Synthesis of Computer Systems (1980), Academic Press: Academic Press London · Zbl 0484.68026 |
| [8] | Green, L., A queuing system with general-use and limited-use servers, Operations Research, 33, 168-182 (1985) · Zbl 0587.60092 |
| [9] | Kleinrock, L., 1976. Queueing Systems, Vol. II, Wiley, New York; Kleinrock, L., 1976. Queueing Systems, Vol. II, Wiley, New York · Zbl 0361.60082 |
| [10] | Mehrotra, V., 1997. Thank you for calling. How may I assist you? Department Seminar, Operations Research Department, Naval Postgraduate School, Monterey, CA, May 28; Mehrotra, V., 1997. Thank you for calling. How may I assist you? Department Seminar, Operations Research Department, Naval Postgraduate School, Monterey, CA, May 28 |
| [11] | Ross, K. W.; Yao, D. D., Optimal load balancing and scheduling in a distributed computer system, Journal of the Association for Computing Machinery, 38, 3, 676-690 (1991) · Zbl 0799.68031 |
| [12] | Shanthikumar, J. G.; Yao, D. D., Multi-class queuing systems: polymatroidal structure and optimal scheduling control, Operations Research., 40, 2, S293-S299 (1992) · Zbl 0764.90036 |
| [13] | Stanford, D. A.; Grassmann, W. K., The bilingual server model: a queueing model featuring fully and partially qualified servers, Information Systems and Operational Research, 31, 4, 261-277 (1993) · Zbl 0799.90056 |
| [14] | Zhou, S., A trace-driven simulation study of dynamic load balancing, IEEE Transactions on Software Engineering, 14, 1327-1341 (1988) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
