Maximum Commonality Problems: Applications and Analysis

Milind Dawande (), Subodha Kumar (), Vijay Mookerjee () and Chelliah Sriskandarajah ()
Additional contact information
Milind Dawande: School of Management, University of Texas at Dallas, Richardson, Texas 75083
Subodha Kumar: Michael G. Foster School of Business, University of Washington, Seattle, Washington 98195
Vijay Mookerjee: School of Management, University of Texas at Dallas, Richardson, Texas 75083
Chelliah Sriskandarajah: School of Management, University of Texas at Dallas, Richardson, Texas 75083

Management Science, 2008, vol. 54, issue 1, 194-207

Abstract: Recently, an agile software development technique called extreme programming has caught the attention of practitioners and researchers in the software industry. A core practice of extreme programming is pair programming, where two developers work on the same piece of code. We introduce the problem of assigning pairs of developers to modules so as to maximize the commonality--a measure of the extent to which common developers work on related modules--subject to a load-balancing constraint that is motivated by the need to control the completion time of the project. We consider two variants of this problem. In MCAP n , a developer is teamed up with exactly one other developer to form a pair that works together for the entire duration of the project. In MCAP s , we allow a developer to pair with more than one other developer during the project. This "pair-splitting" version of the problem facilitates knowledge dissemination among developers, but can increase the effort needed for a developer to adjust to the work habits of several partners. The difference between the commonality achieved with and without pair splitting crucially depends on the underlying structure of the problem. For trees, we show that the value of the maximum commonality is the same for both MCAP n and MCAP s . Additionally, we obtain polynomial-time algorithms for both of these variants. For general graphs, both problems MCAP n and MCAP s are shown to be strongly NP-complete. We prove that the maximum commonality for MCAP s is at most 3/2 times the maximum commonality of MCAP n . We also provide polynomial-time algorithms and approximation results for a number of special cases of these problems.

Keywords: analysis of algorithms; computational complexity; integer programming; applications; suboptimal algorithms (search for similar items in EconPapers)
Date: 2008
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1070.0766 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:54:y:2008:i:1:p:194-207

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().