TY - GEN

T1 - A parallel multiperiod assignment algorithm

AU - Gupta, Babita

AU - Aronson, Jay E.

N1 - 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.

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

UR - https://www.semanticscholar.org/paper/A-parallel-multiperiod-assignment-algorithm-Gupta-Aronson/5c6fa855ada787f0217f1da4abe6adbd9da32315

M3 - Other contribution

ER -