A QUEUING NETWORK MODEL FOR ANALYZING A CLASS OF BRANCH-AND-BOUND ALGORITHMS ON A MASTER SLAVE ARCHITECTURE

• 成果类型: Article
• 署名作者: BOXMA, OJ; KINDERVATER, GAP
• 署名单位: Tilburg University; Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.39.6.1005
• 发表日期: 1991
• 页码: 1005-1017
• 关键词: COMPUTERS COMPUTER SCIENCE; MASTER SLAVE ARCHITECTURE; programming; ANALYSIS OF PARALLEL BRANCH-AND-BOUND ALGORITHMS; queues; FLUID FLOW APPROXIMATIONS

摘要

Partitioning methods lend themselves very well to implementation on parallel computers. In recent years, branch-and-bound algorithms have been tested on various types of architectures. In this paper, we develop a queueing network model for the analysis of a class of branch-and-bound algorithms on a master-slave architecture. The analysis is based on a fluid flow approximation. Numerical examples illustrate the concepts developed. Finally, related branch-and-bound algorithms are studied using a machine repair queueing model.