A parallel algorithm for multiple objective linear programs

This paper presents an ADBASE-based parallel algorithm for solving multiple objective linear programs (MOLPs). Job balance, speedup and scalability are of primary interest in evaluating efficiency of the new algorithm. The scalability of a parallel algorithm is a measure of its capacity to increase performance with respect to the number of processors used. Implementation results on Intel iPSC/2 and Paragon multiprocessors show that the algorithm significantly speeds up the process of solving MOLPs, which is understood as generating all or some efficient extreme points and unbounded efficient edges. The algorithm is shown to be scalable and gives better results for large problems. Motivation and justification for solving large MOLPs are also included.