A parallel multiperiod assignment algorithm

The multiperiod assignment problem (MAST), describes the problem of assigning m activities (jobs) to n persons (m = n is not required) over T discrete time periods at a minimum cost. MAST is known to be NP hard. MAST has been formulated and solved as an integer, multicommodity, network flow problem by specialized branch-and-bound algorithms, and by a dual ascent approximation procedure on serial processor.

This dissertation describes the development, implementation, and evaluation of a parallel, multiperiod assignment algorithm (PMAST). A dynamic, asynchronous parallel algorithm is presented that executes a branch-and-bound procedure to solve the multiperiod assignment problem (MAST) on a Parallel Virtual Machine (PVM) platform, where several processes work independently on various subproblems generated during the branch-and-bound procedure. Computational results and statistical analyses show that PMAST achieves linear, and sometimes, superlinear speedups, both absolute and relative. PMAST also achieves near perfect load balancing among the processes (same as the number of processors).

This research has been motivated, in part, by the need to obtain faster and cost effective solutions to multiperiod assignment problems, which have wide ranging applications in the real-world, and partly, to develop a fairly general, parallel, branch-and-bound algorithm that can be applied successfully to related, near-network problems.