The master-slave paradigm in parallel computer and industrial settings

The master-slave paradigm finds important applications in parallel computer scheduling, semiconductor testing, machine scheduling, transportation, maintenance management and other industrial settings. In the master-slave model considered in this paper a set of jobs is to be processed by a system of processors. Each job consists of a preprocessing task, a slave task and a postprocessing task that must be executed in this order. The pre- and post-processing tasks are to be processed by a master processor while the slave task is processed by a slave processor. In this paper, we motivate the master-slave model and develop bounded performance approximation algorithms for the unconstrained makespan minimization problem as well as for multiple master systems.This work was supported in part by the National Science Foundation under grant MIP-9103379 and the Army Research Office under grant DAA H04-95-1-0111.